Codeforces Round 827 (Div. 4) A - G 题解

Codeforces Round 827 (Div. 4) A - G 题解

A. Sum（800 分难度）

思路： $if-else$ 判断即可
参考代码：

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int a, b, c;
	cin >> a >> b >> c;
	if(a + b == c || a + c == b || b + c == a){
		cout << "YES" << endl;
	} else cout << "NO" << endl;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0; 
} 

B. Increasing（800 分难度）

思路： $sort$ 之后 $for$ 循环判断即可。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N]; 
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	sort(a + 1, a + 1 + n);
	for(int i = 2; i <= n; i ++){
		if(a[i] == a[i - 1]){
			cout << "NO" << endl;
			return ;
		}
	}
	cout << "YES" << endl;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0; 
} 

C. Stripes （900 分难度）

思路： 判断行是否有 $8$ 个 $R$ 或者列是否有 $8$ 个 $B$。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 10;
char s[N][N]; 
void solve(){
	for(int i = 1; i <= 8; i ++){
		for(int j = 1; j <= 8; j ++){
			cin >> s[i][j];
		}
	}
	for(int i = 1; i <= 8; i ++){
		int ans = 0;
		for(int j = 1; j <= 8; j ++){
			if(s[i][j] == 'R'){
				ans ++;
			}
		}
		if(ans == 8){
			cout << "R" << endl;
			return ;
		}
	}
	for(int j = 1; j <= 8; j ++){
		int ans = 0;
		for(int i = 1; i <= 8; i ++){
			if(s[i][j] == 'B'){
				ans ++; 
			}
		}
		if(ans == 8){
			cout << "B" << endl;
			return ;
		}
	}
	return ;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0; 
} 

D. Coprime（1100 分难度）

思路： $n$ 虽然很大，但是数组 $a$ 中元素的值域很小，可以考虑存储出现过数的最右端的下标，然后通过暴力枚举值域，也就是 $1000\ast 1000$ 的复杂度来解决。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int idx[N]; 
void solve(){
	int n;
	cin >> n;
	memset(idx, 0, sizeof idx); // 0 的话就是没有出现过
	for(int i = 1; i <= n; i ++){
		int x;
		cin >> x;
		idx[x] = i;
	} 
	int ma = -1;
	for(int i = 1; i <= 1000; i ++){
		for(int j = 1; j <= 1000; j ++){
			if(__gcd(i, j) == 1 && idx[i] && idx[j]){
				ma = max(ma, idx[i] + idx[j]);	
			}
		}
	}
	cout << ma << endl;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0; 
} 

E. Scuza（1200 分难度）

思路： 首先考虑对于每个询问，如何快速的求出前面所有能走到的高度总和，可以考虑使用前缀和。然后思考对于每个步长，如何快速定位到终止的位置，可以考虑前缀和维护前缀最大值，然后使用二分查找来实现。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N], s1[N]; // s1 来存前缀最大值 
long long s2[N]; // 前缀和 
void solve(){
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
		s2[i] = s2[i - 1] + a[i];
		s1[i] = max(s1[i - 1], a[i]);
	} 
	while(q --){
		int x;
		cin >> x;
		int idx = upper_bound(s1 + 1, s1 + 1 + n, x) - s1 - 1; // 找到第一个大于步长的阶梯，然后 -1 就是能到达的最后位置
		cout << s2[idx] << ' ';
	} 
	cout << endl;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0; 
} 

F. Smaller（1500 分难度）

思路： 首先思考一下复杂度，如果直接暴力拼接字符串然后让两个字符串进行比较时间复杂度会非常大，因为 $k$ 最大为 $1e5$，$s$ 最长为 $5e5$，可以考虑用一个长度为 $26$ 的数组统计每个数出现的次数，那么复杂度就可以从 $O(n\ast k)$ 降到 $O(n)$。然后思考怎样去找到至少一种排序使得字符串 $s$ 字典序可以小于 $t$，通过贪心思想可以发现，将 $s$ 字符串中的字符从小到大放好，将 $t$ 字符串中的字符从大到小放好，然后去比较即可，又因为我们使用数组存储每个字符出现的个数，那么判断下两者数组中字符的情况便可以了。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 30;
long long sum1[N], sum2[N]; // 开 int 会爆
void solve(){
	int n;
	cin >> n;
	memset(sum1, 0, sizeof sum1); // 清空 
	memset(sum2, 0, sizeof sum2);
	sum1[0] = sum2[0] = 1; 
	for(int i = 1; i <= n; i ++){
		int d, k;
		string s;
		cin >> d >> k >> s;
		for(int i = 0; i < s.size(); i ++){ // 新增字符 
			if(d == 1){
				sum1[s[i] - 'a'] += k;
			}else{
				sum2[s[i] - 'a'] += k;
			}
		} 
		int l = 0, r = 25; // 0 表示 a, 25 表示 z 
		while(sum2[r] == 0) r --;
		if(l < r){  
			cout << "YES" << endl;
		}else{
			bool ok = true;
			for(int j = 1; j <= 25; j ++){ // a??? 和 aaaa...a 比较 
				if(sum1[j]) ok = false;
			}
			if(ok == false){
				cout << "NO" << endl;
				continue;
			}
			if(sum1[0] < sum2[0]){ // aaa..aa 和 aaa..aa 比较 
				cout << "YES" << endl;
			}else cout << "NO" << endl;
		}
	} 
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0; 
} 

G. Orray（1500 分难度）

思路： 考虑贪心，每一次从剩余所有没选的元素中选取可以使得 前缀或 最大的那一个元素，最多只需要操作 $30$ 次即可。证明如下：如果每次选择的数字都可以使得 前缀或 变大，那么意味着至少有一个二进制下的 $0$ 变成了 $1$，那么最多进行 $30$ 次操作，前缀或 就不可能再变大了，因为所有的二进制位全部变成了 $1$。如果不是每次都可以使得 前缀或 变大，例如在第 $15$ 次操作之后前缀和没有变化，那么前缀或就永远无法进行变化了，因为我们第 $15$ 次选的就是能将前缀或变最大的元素，但是前缀或并没有变化。时间复杂度为 $O(30\ast n)$。
参考代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N]; 
bool st[N]; 
void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= n; i ++){
		cin >> a[i]; 
		st[i] = 0;
	} 
	int pre_or = 0;
	for(int i = 1; i <= min(30, n); i ++){
		int idx = -1;
		int res = pre_or; 
		for(int j = 1; j <= n; j ++){
			if(st[j]) continue; // 用过的数就跳过 
			if(idx == -1){
				res = (pre_or | a[j]);
				idx = j;
			}else{
				if((pre_or | a[j]) > res){
					res = (pre_or | a[j]);
					idx = j; 
				}
			}
		}
		st[idx] = 1;
		pre_or = res;
		cout << a[idx] << ' ' ;
	}
	for(int i = 1; i <= n; i ++){
		if(!st[i]) cout << a[i] << ' ';
	}
	cout << endl;
}
int main(){
	int t;
	cin >> t;
	while(t --){
		solve();
	}
	return 0; 
}