Codeforces Round #704 (Div. 2)全部题解_codeforces round #704 (div. 2)的题解

题目链接：https://codeforc.es/contest/1492

---

A. Three swimmers

数学
题目大意为3个游泳者会在0,a,2a,…,0,b,2b,…,0,c,2c,…的时间点达到岸边，问在p时间点开始至少需等候多久能遇到游泳者。
若p能被a或b或c整除，则等候时间为0，否则为min(a-p%a,b-p%b,b-p%b)。

#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
ll _,p,a,b,c; 
void work(){
	scanf("%lld%lld%lld%lld",&p,&a,&b,&c);
	if(p%a==0||p%b==0||p%c==0) printf("0\n");
	else printf("%lld\n",min(a-p%a,min(b-p%b,c-p%c)));
}
int main(){
	scanf("%lld",&_);
	while(_--){
		work();
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

B. Card Deck

贪心，数学
题目大意为给定一个排列，每次可以将末尾k个数取出并按照原顺序拼接另一个数列，例如1 2 3 4，每次取出2个，得到3 4 1 2。要求使得拼接成的另一个排列中所有a[i]*n^n-i的值最大。
题意翻译过来就是用上述方式拼接使得拼接所产生的排列字典序最大。
因为要求字典序最大，所以每一步的策略即为将前面未选取的数中的最大值放置在最前面，维护一个当前前n项中的最大值t，从当前位置开始向前遍历，若遍历到t则停止，从t的位置开始将后一段遍历到的数压入vector中，并将路径上的所有数做上标记，遍历完t之后的数字后判断t的值能否继续缩小，最后按序输出vector中的排列即可。

#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
ll _,n,a[100010],pos[100010];
bool vis[100010];
void work(){
	vector<ll> app;
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		pos[a[i]]=i;
		vis[i]=false;
	}
	ll t=n;
	for(ll i=n;i>=1;i--){
		if(a[i]==t){
			for(ll j=i;!vis[a[j]]&&j<=n;j++){
				vis[a[j]]=true;
				app.push_back(a[j]);
			}
		}
		while(vis[t]&&t>=1) t--;
	}
	for(ll i=0;i<n;i++) printf("%lld ",app[i]);
	printf("\n");
}
int main(){
	scanf("%lld",&_);
	while(_--){
		work();
	}
	return 0;
}
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

C. Maximum width

贪心
题目大意为给定两个字符串s与t，要求求出s中等于t的子序列中相邻字母在s中的位置间的最大距离。
遍历一遍s，按顺序储存每个字母出现的下标，正向遍历一遍t，求出t的每个字母在s中出现的坐标的最小值，再反向遍历一遍t，求出当前情况下能将当前字母移到最靠右的位置，再计算移动之后该字母坐标与前一个字母坐标的差值，结果取最大。

#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
ll pos[33][2000010],cnt[33];
ll _,n,m,ans,app[200010];
string s,t;
ll searchmaxn(ll i,ll t){
	ll l=1,r=cnt[i],ans=0;
	while(l<=r){
		ll mid=l+r>>1;
		if(pos[i][mid]<t){
			l=mid+1;
			ans=mid;
		}
		else r=mid-1;
	}
	return pos[i][ans];
}
ll searchminn(ll i,ll t){
	ll l=1,r=cnt[i],ans=0;
	while(l<=r){
		ll mid=l+r>>1;
		if(pos[i][mid]>t){
			r=mid-1;
			ans=mid;
		}
		else l=mid+1;
	}
	return pos[i][ans];
}
int main(){
	scanf("%lld%lld",&n,&m);
	cin>>s>>t;
	for(ll i=1;i<=n;i++) pos[s[i-1]-'a'+1][++cnt[s[i-1]-'a'+1]]=i;
	app[1]=pos[t[0]-'a'+1][1];
	for(ll i=2;i<=m;i++){
		app[i]=searchminn(t[i-1]-'a'+1,app[i-1]);
	}
	app[m]=pos[t[m-1]-'a'+1][cnt[t[m-1]-'a'+1]];
	ans=max(ans,app[m]-app[m-1]);
	for(ll i=m-1;i>=2;i--){
		app[i]=searchmaxn(t[i-1]-'a'+1,app[i+1]);
		ans=max(ans,app[i]-app[i-1]);
	}
	printf("%lld",ans);
	return 0;
}
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

D. Genius’s Gambit

数学
题目大意为给定数a，b，k，要求求出两个数x，y，使得x与y在二进制下的0的个数为a，1的个数为b，且x-y在二进制下1的个数为k。
考虑两个二进制数(1000)₂与(0001)₂，则(1000)₂-(0001)₂=(0111)₂，结果中1的个数为两个数中1所在的位置坐标之差对于所给的数，我们可以构造出形如(111…10000)₂与(111…00001)₂的数，减去之后最多能得到的1的个数为a，那么如果所给的k>a，我们可以把高位的1成对地向低位移动来构造出0，例如数(1000000)₂与(0000001)₂相减所产生(0111111)₂，数(1011000)₂与(0011001)₂相减所产生的也是(0111111)₂，最终我们可以构造出形如(111…000…1…111…000…0)₂与(111…000…0…111…000…1)₂的数，最多两数相减能得到的k为a+b-2。注意特判k=0，b=1，a=0的情况。

#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
int a,b,n,k,s1[200010],s2[200010];
int main(){
	scanf("%d%d%d",&a,&b,&k);
	if(!k){
		printf("Yes\n");
		for(int i=1;i<=b;i++) printf("1");
		for(int i=1;i<=a;i++) printf("0");
		printf("\n");
		for(int i=1;i<=b;i++) printf("1");
		for(int i=1;i<=a;i++) printf("0");
		return 0;
	}
	else if((b==1||a==0)&&k) printf("No");
	else if(k>a+b-2) printf("No");
	else{
		printf("Yes\n");
		if(b==1){
			printf("1");
			for(int i=1;i<=a;i++) printf("0");
			printf("\n");
			printf("1");
			for(int i=1;i<=a;i++) printf("0");
			return 0;
		}
		n=a+b;
		s1[1]=s2[1]=1;
		s1[a+b-k]=1;
		s2[a+b]=1;
		b-=2;
		for(int i=n-k+1;i<=n-k+(k-a);i++) s1[i]=s2[i]=1,b--;
		for(int i=2;i<=b+1;i++) s1[i]=s2[i]=1;
		for(int i=1;i<=n;i++) printf("%d",s1[i]); 
		printf("\n");
		for(int i=1;i<=n;i++) printf("%d",s2[i]);
	}
	return 0;
}
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

E. Almost Fault-Tolerant Database

贪心，dfs
题目大意为给定n个长度为m的数列，要求找出一个数列，使得该数列与这n个数列中每个数列的不同数字个数小于等于2。
假定目标数列即为第一个数列，从第2个数列开始依次比较，若其他数列与第一个数列相异数字数小于等于2，则直接跳过，若相异数字数大于等于5，则无论怎么修改第一个数列中的数字，都无法使得这两个数列满足条件，直接输出"No"结束。若查询到第i个数列与第一个数列相异数字数=3或=4，则可以通过修改第i个数列或者第1个数列中的1或2个数字来使得这两个数列满足条件，将相异位置做上标记，枚举所有可能的修改情况（例如有3个位置相异，用01代表修改与不修改，可能的情况为000,001,…111），保留2个位置的数作为待修改位，用0标记，然后将修改后第一个数列的值复制给b数组，然后从1开始将b数组与每个数列匹配一遍，若除了0所在位之外，其他位置数所产生的差异数大于等于3，则不满足，直接退出，若其他位置数所产生的差异数加上数列b中0的个数小于等于2，则无论待修改位改成什么情况都符合，直接跳过判断下一个，否则枚举所有要修改的待修改位，若修改之后数列b与当前所判断数列相异的位置数小于等于2，则修改并查询下一个数列，若n个数列都与数列b满足，则输出b
并结束程序。若枚举完所有情况后仍不能找到解则在搜索结束后直接输出"No"。最后如果正常跳出循环，则说明第一个数列与其余各个数列都满足条件，直接输出第一个数列即可。

#include<bits/stdc++.h>
#define ll long long
#define next next_
#define y1 yy
using namespace std;
vector<vector<int>> a;
int n,m,b[250010];
void ok(int t){
	if(t==n+1){
		printf("Yes\n");
		for(int i=1;i<=m;i++) if(!b[i]) printf("1 ");
		else printf("%d ",b[i]);
		exit(0);
	}
	else{
		vector<int> pos;
		int num=0;
		for(int i=1;i<=m;i++) if(!b[i]) pos.push_back(i);
		else if(b[i]!=a[t][i]) num++;
		if(num>=3) return;
		if(num+pos.size()<=2){
			ok(t+1);
			return;
		}
		else{
			int k=(int)pos.size();
			for(int i=0;i<(1<<k);i++){
				int sum=num;
				for(int j=0;j<k;j++){
					if((i>>j)&1) b[pos[j]]=a[t][pos[j]];
					else sum++;
				}
				if(sum<=2) ok(t+1);
				for(int j=0;j<k;j++) b[pos[j]]=0;
			}
		}
	}
}
void work(int p,int q){
	vector<int> pos;
	for(int i=1;i<=m;i++) if(a[p][i]!=a[q][i]) pos.push_back(i);
	int k=(int)pos.size();
	for(int i=0;i<(1<<k);i++){
		vector<int> c;
		for(int j=0;j<k;j++) if((i>>j)&1) c.push_back(pos[j]);
		if(c.size()!=2) continue;
		else{
			for(int j=1;j<=m;j++) if(j==c[0]||j==c[1]) b[j]=0;
			else b[j]=a[p][j];
		}
		ok(1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	a=vector<vector<int>>(n+10,vector<int>(m+10,0));
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			scanf("%d",&a[i][j]);
	for(int i=2;i<=n;i++){
		vector<int> pos;
		for(int j=1;j<=m;j++) if(a[1][j]!=a[i][j]) pos.push_back(j);
		if(pos.size()<=2) continue;
		else if(pos.size()>=5) return printf("No"),0;
		else{
			work(1,i);
			printf("No");
			return 0;
		}
	}
	printf("Yes\n");
	for(int i=1;i<=m;i++) printf("%d ",a[1][i]);
	return 0;
}
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74