Codeforces Round #827 (Div. 4)
Codeforces Round #827 (Div. 4)
https://codeforces.com/contest/1742
人傻逼了,C题卡了半天心态直接炸掉,第二天起来过了FG,麻
A. Sum
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| #include <bits/stdc++.h>
using namespace std;
void solve () { int a, b, c; cin >> a >> b >> c; if (a == b + c || b == a + c || c == a + b) puts ("YES"); else puts ("NO"); }
int main () { int t; cin >> t; while (t --) solve (); }
|
B. Increasing
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| #include <bits/stdc++.h>
using namespace std; const int N = 105; int n;
void solve () { set <int> s; cin >> n; for (int i = 1; i <= n; i++) { int x; cin >> x; s.insert (x); } if (s.size() == n) puts ("YES"); else puts ("NO"); }
int main () { int t; cin >> t; while (t --) solve (); }
|
C. Stripes
注意行是R,列是B
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; char a[10][10];
void solve () { for (int i = 1; i <= 8; i++) { string s; cin >> s; for (int j = 1; j <= 8; j++) { a[i][j] = s[j-1]; } } for (int i = 1, j; i <= 8; i++) { for (j = 1; j <= 8; j++) { if (a[i][j] != 'R') break; } if (j == 9) { cout << 'R' << endl; return ; } }
for (int j = 1, i; j <= 8; j++) { for (i = 1; i <= 8; i++) { if (a[i][j] != 'B') break; } if (i == 9) { cout << 'B' << endl; return ; } } }
int main () { int t; cin >> t; while (t --) solve (); }
|
D. Coprime
因为ai最大只有1000,所以对于每个ai可以查找所有与其互质的数的出现下标。gcd要预处理,不然会T
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> #define ll long long
using namespace std; typedef pair<int, int> pii; const int N = 2e5 + 5; int n, a[N], pos[1005]; int gcd[1005][1005];
void pre () { for (int i = 1; i <= 1000; i++) { for (int j = 1; j <= 1000; j++) { if (__gcd (i, j) == 1) gcd[i][j] = true; } } }
void solve () { cin >> n; memset (pos, 0, sizeof pos); for (int i = 1; i <= n; i++) cin >> a[i], pos[a[i]] = i; ll ans = -1; for (int i = 1; i <= n; i++) { for (int j = 1; j <= 1000; j++) { if (!pos[j] || (!gcd[j][a[i]] && !gcd[a[i]][j])) continue; ans = max (1ll*pos[j] + i, ans); } } cout << ans << endl; }
int main () { pre (); int t; cin >> t; while (t --) solve (); }
|
E. Scuza
二分 + 前缀和
小trick: 对于非单调的原序列a,可以处理出一个maxn数组,记录截至目前的最大值,使其变为单调,就可以二分了。
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
| #include <bits/stdc++.h> #define int long long
using namespace std; const int N = 2e5 + 5; int n, m, a[N], b[N], sum[N];
void solve () { cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; sum[i] = sum[i-1] + a[i]; b[i] = max (b[i-1], a[i]); }
while (m --) { int x; cin >> x; int pos = upper_bound (b + 1, b + n + 1, x) - b; cout << sum[pos - 1] << ' '; } cout << endl; }
signed main () { int t; cin >> t; while (t --) solve (); }
|
F. Smaller
因为rearrange是打乱顺序,全部重排,为了使得s尽可能小,我们一定会把’a’放在最前面;为了使得t尽可能大,我们一定会把t中最大的字符放在前面。
那么思路就出来了,对于每次新增,只需记录新加入了多少个字符(这是为了二者全为a的时候比较长度)。
情况可划分为:
- t中存在一个比’a’大的字符,则 YES,因为s第一个一定是a,而t得第一个不是。
- t中不存在比’a’大的字符,即t全为’a’,s中存在比’a’大的字符,则 NO,不管怎么排都有 s > t。
- t和s中都不存在比’a’大的字符,即s,t全为’a’,则统计二者长度,更长的字典序更大。
- 其余情况均为 YES。
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
| #include <bits/stdc++.h> #define int long long
using namespace std;
void solve () { int m; cin >> m; bool fb = false, fa = false; int cnts = 0, cntt = 0; while (m --) { int op, k; string s; cin >> op >> k >> s; if (op == 1) { cnts += s.size () * k; if (!fa && !fb) { for (int i = 0; i < s.size (); i++) { if (s[i] > 'a') { fa = true; break; } } } } else { cntt += s.size () * k; if (!fb) { for (int i = 0; i < s.size (); i++) { if (s[i] > 'a') { fb = true; break; } } } } if (fb) puts ("YES"); else { if (fa || cnts >= cntt) puts ("NO"); else puts ("YES"); } } }
signed main () { int t; cin >> t; while (t --) solve (); }
|
G. Orray
暴力
第一个肯定是最大的,接着就枚举能够使得or和变大的即可
如果maxn不更新了,就表示已经找到最大的了。
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
| #include <bits/stdc++.h>
using namespace std; const int N = 2e5 + 5; int a[N], n; bool used[N];
void solve () { cin >> n; for (int i = 1; i <= n; i++) cin >> a[i], used[i] = false; sort (a + 1, a + n + 1, greater <int> ());
int sum = a[1]; cout << a[1] << ' '; used[1] = true;
while (1) { int maxn = -1, pos = 0; for (int i = 1; i <= n; i++) { if (used[i]) continue; int dx = (a[i] | sum) - sum; if (dx > maxn) maxn = dx, pos = i; } if (maxn <= 0) break; used[pos] = true, sum |= a[pos]; cout << a[pos] << ' '; }
for (int i = 1; i <= n; i++) { if (!used[i]) cout << a[i] << ' '; } cout << endl; }
signed main () { int t; cin >> t; while (t --) solve (); }
|
我是大傻逼呜