Codeforces Round 827 (Div. 4)
Dashboard - Codeforces Round 827 (Div. 4) - Codeforces
A Sum
简单题
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;
}
B Increasing
用个桶存一下看看有没有重复的元素,有一定不行
void solve() {
int n;
cin >> n;
map<int, int> mp;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
mp[x]++;
}
for (auto [x, y]: mp) {
if (y > 1) {
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
C Stripes
判断每一行和每一列有没有8个B或R的就行
char g[N][N];
void solve() {
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
cin >> g[i][j];
}
}
for (int i = 0; i < 8; i++) {
int cnt = 0;
for (int j = 0; j < 8; j++) {
if (g[i][j] == 'R')cnt++;
}
if (cnt == 8) {
cout << 'R' << endl;
return;
}
}
for (int i = 0; i < 8; i++) {
int cnt = 0;
for (int j = 0; j < 8; j++) {
if (g[j][i] == 'B')cnt++;
}
if (cnt == 8) {
cout << 'B' << endl;
return;
}
}
}
D Coprime
vp的时候二逼了,想复杂了,重复的数没有意义,用map村每个元素坐标的最大值就行,再\(O(\)\(x^{2}\)\()\)直接暴力的判断一下就可以了
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void solve() {
int n;
cin >> n;
vector<int> a(n);
unordered_map<int, int> mp;
for (int i = 0; i < n; i++) {
cin >> a[i];
mp[a[i]] = max(i, mp[a[i]]);
}
int ans = 0;
for (auto [x, y]: mp) {
for (auto [i, j]: mp) {
if (gcd(x, i) == 1)ans = max(ans, y + 1 + j + 1);
}
}
if (ans == 0)ans = -1;
cout << ans << endl;
}
E Scuza
题意:有q此询问,每次给出可以走上多高的楼梯,问最多可以走到多高的距离
思路:我们可以先把每个楼梯进行求前缀和,再进行前缀最大值处理,用每次给的值去再前缀最大的数组里二分,找到第一个大于的值,前一个位置的前缀和就是答案
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n + 1), s(n + 1);
for (int i = 1; i <= n; i++)cin >> a[i], s[i] = s[i - 1] + a[i];
for (int i = 2; i <= n; i++)a[i] = max(a[i], a[i - 1]);
while (q--) {
int k;
cin >> k;
if (k >= a[n])cout << s[n] << ' ';
else if (k < a[1])cout << 0 << ' ';
else {
int pos = upper_bound(a.begin() + 1, a.end(), k) - (a.begin() + 1);
cout << s[pos] << ' ';
}
}
cout << endl;
}
F Smaller
题意:给你两个字符串\(S\)和\(T\)初始值都为a,每次会对其中一个字符串进行扩展,意思就是再原先的字符串上加给的字符串,问两个重新排列\(S\)和\(T\),能否是\(S\)的字典序小于\(T\)
思路:用两个map记录两个字符串出现的字母种类和数量,只要\(T\)的最大字母不为a就可以,否则如果\(S\)的a的数量小于\(T\)的数量并且两个的最大字母都是a可以,否则不行,,如果\(S\)的a的数量大于等于\(T\)的数量不可以
void solve() {
string s = "a", t = "a";
map<char, int> mps, mpt;
mps['a']++;
mpt['a']++;
int q;
cin >> q;
while (q--) {
int n, k;
string str;
cin >> n >> k >> str;
for (auto i: str) {
if (n == 1)mps[i] += k;
if (n == 2)mpt[i] += k;
}
char opt = 'a';
char ops = 'a';
for (auto [x, y]: mpt)opt = max(opt, x);
for (auto [x, y]: mps)ops = max(ops, x);
if (opt == 'a') {
if (ops != 'a')cout << "NO" << endl;
else {
if (mps['a'] < mpt['a'])cout << "YES" << endl;
else cout << "NO" << endl;
}
} else cout << "YES" << endl;
}
}
G Orray
题意:给你一组数,让你把他们重新排列以后是的前缀或数组的字典序最大
思路:要让字典序最大,所以我们尽可能让前面的数变大,在二进制下面我们就是让数的每一位尽可能都变成1,那我们最多会操作31次,int的最大二进制位数是31位,所以我们暴力的去找31次再数组里还没有用用过的值和目前的值或起来的最大值就行了,剩下的数随便输出没有关系
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<bool> vis(n + 1, false);
for (int i = 0; i < n; i++) cin >> a[i];
int ans = 0;
for (int i = 0; i < 31; i++) {
int res = ans;
int idx=-1;
for (int j = 0; j < n; j++) {
if (vis[j])continue;
if ((a[j] | ans) > res) {
res = (ans | a[j]);
idx = j;
}
}
if(idx==-1)break;
vis[idx] = true;
ans |= a[idx];
cout << a[idx] << ' ';
}
for (int i = 0; i < n; i++)if (!vis[i])cout << a[i] << ' ';
cout << endl;
}