codeforces round #704题解_cf round 704

codeforces round #704题解

A. three swimmers
题目大意：有三个人游泳，他们到达岸边的时间分别是a，b，c的倍数，同时，你会在第p秒到达岸边，请问你到达岸边后最少过多长时间会遇到某个游泳的人？
解析：分两种情况，如果q可以被a，b，c整除，结果是0，如果不能整除，计算边界情况，语言无法表达。。。。。看代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		long long int p,a[3];
		cin>>p>>a[0]>>a[1]>>a[2];
		long long int ans=1e18;
		for( int i=0;i<3;i++){
			long long  int temp=p/a[i]*a[i];
			if(p%a[i]==0){
				ans=0;
				break;
			}
			else{
				ans=min(temp+a[i]-p,ans);
			}
		}
		cout<<ans<<endl;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

B. Card Deck
题目大意：
解析：
贪心算法

#include<bits/stdc++.h>
using namespace std;
int a[100100];
int pos[100100];//储存数字的位置 
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			pos[a[i]]=i;
		} 
		int p=n+1;
		for( int i=n;i>=1;i--){
			if(pos[i]<p){
				for( int j=pos[i];j<p;j++){
					cout<<a[j]<<" ";
				}
				p=pos[i];
			}
		}
	}
}

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

C. Maximum width
题目大意：
现在有两个字符串，第一个字符串包含第二个字符串中的全部字符，求两个相邻字符之间的最大距离
解析：贪心算法，从正向和负向分别进行匹配，然后找差的最大值

#include<bits/stdc++.h>
using namespace std;
string a,b;
int pos1[200010];
int pos2[200010];
int main(){
	int la,lb;
	cin>>la>>lb;
	cin>>a>>b;
	int j=0;
	for( int i=0;i<la;i++){
		if(a[i]==b[j]){
			pos1[j]=i;
			j++;
		}
		if(j>=lb) break;
	}
	j=lb-1;
	for( int i=la-1;i>=0;i--){
		if(a[i]==b[j]){
			pos2[j]=i;
			j--;
		}
		if(j==-1) break;
	}
	int ans=0;
	for( int i=0;i<lb-1;i++){
		ans=max(ans,pos2[i+1]-pos1[i]);
	}
	cout<<ans<<endl;
}

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

D. Genius‘s Gambit
题目大意：
给定三个数a，b和k，要求找到两个数x和y，这两个数的二进制形式都包含a个0和b个1；如果将两个数相减，则x-y=z的二进制数含有k个1。请问是否存在这样的x和y？
题目解析：
先假设b=2的情况，然后在这个情况的基础上把0改为1；注意讨论特殊情况

#include<bits/stdc++.h>
using namespace std;
int rem[200100];
int main(){
	int a,b,k;
	cin>>a>>b>>k;//a is the number of zeros ;b is the number of ones
	//最多凑出a+b-2个1 
	if(k>a+b-2&&k!=0){
		cout<<"No"<<endl;
		return 0; 
	}
	if(b==1&&k!=0||a==0&&k!=0) {
		cout<<"No"<<endl;
		return 0;
	}
	if(k==0){
		cout<<"yes"<<endl;
		for( int i=1;i<=b;i++) cout<<1;
		for( int i=1;i<=a;i++) cout<<0;
		cout<<endl;
		for( int i=1;i<=b;i++) cout<<1;
		for( int i=1;i<=a;i++) cout<<0;
		cout<<endl;
		return 0;
	}
	else {
		cout<<"Yes"<<endl;
		cout<<11;
		int temp=b-2;
		for( int i=1;i<=k-1;i++){
			if(temp>0) {
				cout<<1;
				temp--;
			}
			else cout<<0;
		}
		cout<<0;
		for( int i=1;i<=a+b-k-2;i++){
			if(temp>0){
				cout<<1;
				temp--;
			}
			else cout<<0;
			
		}
		cout<<endl;
		cout<<10;
		temp=b-2;
		for( int i=1;i<=k-1;i++){
			if(temp>0){
				cout<<1;
				temp--;
			}
			else cout<<0;
		}
		cout<<1;
		for( int i=1;i<=a+b-k-2;i++){
			if(temp>0){
				cout<<1;
				temp--;
			}
			else cout<<0;
		}
		cout<<endl;
	}
}

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

E.Almost Fault-Tolerant Database