0%

Codeforces Round #598 (Div. 3)

发表于 Valine：
本文字数： 4.5k 阅读时长 ≈ 7 分钟

Codeforces Round #598 (Div. 3)

A. Payment Without Change

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
int q;
ll a,n,b,s; 
int main(){
	scanf("%d",&q);
	while(q--){
		scanf("%lld%lld%lld%lld",&a,&b,&n,&s);
		bool flag=1;
		if(a*n+b<s) {
			flag=0;
		}
		else{
			if(s%n>b){
				flag=0;
			}
		}
		if(flag) puts("YES");
		else puts("NO");
	}
	return 0;
}

B. Minimize the Permutation

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e5+5;
const long N = 200000; 
int q;
int n; 
int a[105];
int main(){
	scanf("%d",&q);
	while(q--){
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
		}
		int pos=0;
		int last=0;
		while(last<n){
			int min=1000000;
			for(int i=pos+1;i<=n;i++){
				if(min>a[i]){
					min=a[i];
					pos=i;
				}
			}
			for(int i=pos;i>last;i--){
				if(a[i-1]>a[i]){
					swap(a[i-1],a[i]);
				}
			}
			last=pos;		
		}
		for(int i=1;i<=n;i++){
			printf("%d%c",a[i],i==n ? '\n':' ');
		}
	}
	return 0;
}

C. Platforms Jumping

参考：blog

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e6+5;
const long N = 200000; 
int n,m,d;
int c[1005];
int ans[1005];
int main(){
	scanf("%d%d%d",&n,&m,&d);
	int max_len=0;
	for(int i=1;i<=m;i++){
		scanf("%d",&c[i]);
		max_len+=c[i];
	}
	if((max_len+d*(m+1)-m)<n+1){
		puts("NO");
		return 0;
	}
	puts("YES");
	int pos=0;
	for(int i=1;i<=m;i++){
		if(pos+d+max_len<=n) pos+=d;
		else pos=n+1-max_len;
		for(int j=pos;j<=pos+c[i]-1;j++){
			ans[j]=i;
		}
		pos+=c[i]-1;
		max_len-=c[i];
	}
	for(int i=1;i<=n;i++){
		printf("%d%c",ans[i], i==n ? '\n':' ');
	}	
	return 0;
}

D. Binary String Minimizing

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=1e6+5;
const long N = 200000; 
int q;
ll n,k;
int a[MAX_N];
int main(){
	scanf("%d",&q);
	while(q--){
		scanf("%lld%lld",&n,&k);
		char c;
		int len=0;
		for(int i=1;i<=n;i++){
			scanf(" %c",&c);
			if(c=='0'){
				a[++len]=i;
			}
		}
		for(int i=1;i<=len&&k;i++){
			if(k>=(a[i]-i)){
				k=k-(a[i]-i);
				a[i]=i;
			}
			else{
				a[i]=a[i]-k;
				k=0;
				break;
			}
		}
		int cnt=1;
		for(int i=1;i<=n;i++){
			if(i==a[cnt]&&cnt<=len) {
				printf("0");
				cnt++;
			}
			else printf("1");
		}
		printf("\n");
	}
	return 0;
}

E. Yet Another Division Into Teams

参考:blog

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=2e5+5;
const int INF=0x3f3f3f3f;
pair<int,int > a[MAX_N];
int dp[MAX_N],p[MAX_N];
int ans[MAX_N];
int root,cnt;
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i].first);
		a[i].second=i;
	} 
	sort(a+1,a+1+n);
	memset(dp,INF,sizeof(dp));
	dp[1]=0;
	for(int i=1;i<=n;i++){
		for(int j=2;j<=4&&i+j<=n;j++){
			int temp=a[i+j].first-a[i].first;
			if(dp[i+j+1]>dp[i]+temp){
				dp[i+j+1]=dp[i]+temp;
				p[i+j+1]=i;
			}
		}
	}
	root=n+1; cnt=1;
	while(root!=1){
		for(int i=root-1;i>=p[root];i--){
			ans[a[i].second]=cnt;
		}
		cnt++;
		root=p[root];
	}
	printf("%d %d\n",dp[n+1],cnt-1);
	for(int i=1;i<=n;i++){
		printf("%d%c",ans[i],i==n ? '\n' :' ');
	}
	return 0;
}

F. Equalizing Two Strings

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N=2e5+5;
const long N = 200000; 
 
int q;
int n;
char s[MAX_N];
int s_vis[30]; 
char t[MAX_N];
int t_vis[30]; 
int main(){
	scanf("%d",&q);
	while(q--){
		memset(s_vis,0,sizeof(s_vis));
		memset(t_vis,0,sizeof(t_vis));
		scanf("%d",&n);
		scanf("%s",s);
		scanf("%s",t);
	
		bool flag=0;
		for(int i=0;i<n;i++){
			s_vis[s[i]-'a']++;
			t_vis[t[i]-'a']++;
		}
		bool flag1=0;
		for(int i=0;i<26;i++){
			if(s_vis[i]!=t_vis[i])	{
				flag1=1;
				break;
			}
		}
		if(flag1) {
			puts("NO");
			continue;
		}
		for(int i=0;i<26;i++){
			if(s_vis[i]>=2||t_vis[i]>=2){
				flag=1;
				break;
			}
		}
		if(flag){
			puts("YES");
			continue;
		}
		else{
			int num1=0;
			int num2=0;
			for(int i=0;i<n-1;i++){
				for(int j=i+1;j<n;j++){
					if(s[i]>s[j]){
						num1++;
					}
					if(t[i]>t[j]){
						num2++;
					}
				}
			}
			if((num1&1)==(num2&1))puts("YES");
			else puts("NO");
		}
	}
	return 0;
}

-------------本文结束感谢您的阅读-------------