The 19th Zhejiang Provincial Collegiate Programming Contest

Code / xCPC
字数统计: 2k   |   阅读时长≈ 10 分钟

A. JB Loves Math

a=5，b=3

a=5，b=2

a=2，b=6

a=2，b=5

a=2，b=8

容易总结规律

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void solves(){
	int a,b;cin>>a>>b;
	if(a==b){
		cout<<0<<endl; return ;
	}
	if(a>b){
		if((a-b)&1){
			cout<<2<<endl;
		} else{
			cout<<1<<endl;
		}
	} else{
		if((b-a)&1){
			cout<<1<<endl;
		} else{
			int len=b-a;
			len/=2;
			if(len&1){
				cout<<2<<endl;
			} else{
				cout<<3<<endl;
			}
		}
	}
}

B. JB Loves Comma

1
2
3
4
5
6
7
8
9
10
void solves(){
	string s;cin>>s;
	cout<<s[0]<<s[1];
	for(int i=2;i<s.size();i++){
		cout<<s[i];
		if(s[i-2]=='c'&&s[i-1]=='j'&&s[i]=='b'){
			cout<<',';
		}
	}
}

C. JB Wants to Earn Big Money

1
2
3
4
5
6
7
8
9
10
11
12
13
void solves(){
	int n,m,s;cin>>n>>m>>s;
	int ans=0;
	for(int i=0;i<n;i++){
		int x;cin>>x;
		if(x>=s)ans++;
	}
	for(int i=0;i<m;i++){
		int x;cin>>x;
		if(x<=s)ans++;
	}
	cout<<ans<<endl;
}

G. Easy Glide

考虑起点为第一个点，2~n+1个点为滑行点，第n+2个点为终点，建图跑一遍dij。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
double g[N][N];
double v1,v2;
double dijkstra(int n){
	vector<double>dist(n+7,inf);
	vector<int>st(n+7,false);
	dist[1]=0;
	for(int i=0;i<n;i++){
		int t=-1;
		for(int j=1;j<=n;j++)
			if(!st[j]&&(t==-1||dist[t]>dist[j]))
				t=j;
		st[t]=true;
		for(int j=1;j<=n;j++)
			dist[j]=min(dist[j],dist[t]+g[t][j]);
	}
	return dist[n];
}
struct point{
	double x,y;
}a[N],b,e;
double dis(point a,point b){
	return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void solves(){
	int n;cin>>n;
	for(int i=2;i<=n+1;i++){
		cin>>a[i].x>>a[i].y;
	}
	cin>>b.x>>b.y>>e.x>>e.y>>v1>>v2;
	double res=v2*3;
	for(int i=2;i<=n+1;i++){
		double len=dis(a[i],b);
		g[1][i]=len/v1;
		len=dis(a[i],e);
		if(res>=len){
			g[n+2][i]=g[i][n+2]=len/v2;
		} else{
			g[n+2][i]=g[i][n+2]=3+(len-res)/v1;
		}
		for(int j=2;j<=n+1;j++){
			if(i==j) continue;
			double len=dis(a[i],a[j]);
			if(res>=len){
				g[i][j]=g[j][i]=len/v2;
			} else{
				g[i][j]=g[j][i]=3+(len-res)/v1;
			}
		}
	}
	g[1][n+2]=g[n+2][1]=dis(b,e)/v1;
	cout<<fixed<<setprecision(8)<<dijkstra(n+2)<<endl;
}

I. Barbecue

我知道是马拉车但是我没学过^ ^，只能玄学优化卡过去

首先注意到，数据最大可达到1e9但是只给了1.5s。但是容易发现，会达到1e9的数据都是专门构造的特殊数据，所以只需要考虑以下两个情况。

1.容易发现当字符串的所有字符都相同时，它的任意子串一定是回文串。例如aaaaaaa的任意子串都是回文串。我们然后把相同的连续区间进行预处理然后判掉这种情况。加了这个处理后tle on test 22。

2.考虑一个回文串的对称子串也是回文串，所以我们在check完一个回文串后顺便把它所有的回文子串也一起标记。比如说，potatop是回文串，那么在check(potatop)的时候顺便把otato，tat，a一并标记为回文。标记完后顺利AC（800ms+）。

其实加上这些优化后复杂度可以压到很低很低了，毕竟能让人tle的数据都是人为构造的两种特殊数据：要么是反复判断一个回文串的对称子串，要么是反复check一个全部字符都相同的子串。

把这两种情况特判掉就好，优雅过题无需算法////

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
string s;
int vis[N],ck[N];
bool check(int l,int r){
	int x=l,y=r;
	for(;l<=r;){
		if(s[l]!=s[r]) return false;
		l++,r--;
	}
	for(;x<=y;){
		ck[x]=y;
		x++,y--;
	}
	return true;
} 
void solves(){
	int n,q;
	cin>>n>>q;
	cin>>s;
	int cnt=1;
	for(int i=1;i<n;i++){
		if(s[i]==s[i-1]){
			vis[i-1]=vis[i]=cnt;
		} else{
			cnt++;
			vis[i]=cnt;
		}
	}
	while(q--){
		int l,r;cin>>l>>r;
		if(vis[l-1]==vis[r-1]||r-1==ck[l-1]||check(l-1,r-1)){
			cout<<"Budada"<<endl;
		} else{
			if((r-l+1)&1){
				cout<<"Putata"<<endl;
			} else{
				cout<<"Budada"<<endl;
			}
		}
	}
}

J. Frog

可能我的构造有洞但是我不知道

假设起点和终点弧度差为θ\theta，θ∈[0,π]\theta \in[0,\pi]。

1.当走两步可达时，θ∈[0,π2]\theta\in[0,\frac{\pi}{2}]，如下图绿色区域。

1

容易得到α=θ2\alpha=\frac{\theta}{2}，且极径AG=ρ=2cos(α)AG=\rho=2cos(\alpha)

2.当走三步可达，θ∈[π2,π2+arccos(34)]\theta\in[\frac{\pi}{2},\frac{\pi}{2}+arccos({\frac{3}{4}})]，如下图绿色区域。其中，π2+arccos(34)\frac{\pi}{2}+arccos({\frac{3}{4}})转换为角度后约为131°。

2

容易得到A1C=A1B1=2A_1C=A_1B_1=\sqrt{2}，余弦定理得到∠CA1B1∠CA_1B_1的余弦值为34\frac{3}{4}

不妨记∠CA1B∠CA_1B为β\beta，那么∠起点A1B1∠起点A_1B_1也为β\beta。容易得到∠CA1B1=arccos(1−18cos(β)2)∠CA_1B_1=arccos(1-\frac{1}{8cos(\beta)^2})。即有

θ=2β+arccos(1−18cos(β)2)\theta=2\beta+arccos(1-\frac{1}{8cos(\beta)^2})

容易证明β\beta关于θ\theta在该定义域内具有单调性。对于给定的θ\theta，考虑使用二分进行求解β\beta。得到β\beta后容易算出点CC、B1B_1的坐标。

3.其余部分如下图绿色区域

3

可以使∠GA1起点=∠IA1C=π4∠GA_1起点=∠IA_1C=\frac{\pi}{4}，其余部分容易计算。

L. Candy Machine

一开始根本看不懂题目在说啥，看样例猜题意然后一通乱wa

容易发现，子集里面甜度小的糖果更多，只会拉低平均值，尽可能取更多甜度小的糖果对于答案而言是更优的。

即对于一个升序序列，子集的左端点固定在最小的值，枚举每个右端点更新答案。考虑选择二分更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
ll a[N],qian[N];
int check(int l,int r,int x){
	while(l<r){
		int mid=(l+r)>>1;
		if(a[mid]>=x)
			r=mid;
		else
			l=mid+1;
	}
	return l;
}
void solves(){
	int n;cin>>n;
	int ans=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	sort(a+1,a+1+n);
	for(int i=1;i<=n;i++){
		qian[i]=qian[i-1]+a[i];
	}
	for(int i=1;i<=n;i++){
		int avr=qian[i]/i;
		int idx=check(1,i,avr+1);
		if(a[idx]==avr) continue;
		ans=max(ans,i-idx+1);
	}
	cout<<ans<<endl;
}

M. BpbBppbpBB

这个题直接让我回忆起前两个月被711. 不同岛屿的数量 II - 力扣（LeetCode）支配的恐惧，思维定势一直往力扣711靠，甚至大力枚举十种旋转情况写出了屎一样的代码^ ^

hax赛中给出的思路：设a为黑格点的数量，得到146s+100c=a。设b为白圆圈数量，得到2s+c=b。容易解得c和s。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
char a[N][N];
vector<string>s={
	"######",
	"##..##",
	"#....#",
	"#....#",
	"##..##",
	"######",
};
bool check(int x,int y){
	for(int i=0;i<s.size();i++){
		for(int j=0;j<s.back().size();j++){
			if(s[i][j]!=a[i+x][j+y]){
				return false;
			}
		}
	}
	return true;
}
void solves(){
	int n,m;
	cin>>n>>m;
	int aa=0,b=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>a[i][j];
			if(a[i][j]=='#') b++;
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(s.back().size()<=m-j+1&&s.size()<=n-i+1){
				if(check(i,j)) aa++;
			}
		}
	}
	cout<<(100*aa-b)/54<<" "<<aa-2*((100*aa-b)/54)<<endl;
}
打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022-2023 JingyiQu
  • 访问人数: | 浏览次数:

如果这篇博客帮助到你，可以请我喝一杯咖啡~

支付宝
微信