Codeforces Round #827 (Div. 4)(A~G)

A.Sum

 1 void solve() {
 2     int a[3];
 3     for (int i = 0; i < 3; i ++) cin >> a[i];
 4     sort(a, a + 3);
 5     if (a[2] == a[1] + a[0]) cout << "YES" << endl;
 6     else cout << "NO" << endl;
 7 }
 8 
 9 int main() {
10     ios::sync_with_stdio(false);
11     cin.tie(nullptr);
12 
13     int t; cin >> t;
14     while (t --) solve();
15     return 0;
16 }

B.Increasing

 1 bool solve() {
 2     int n; cin >> n;
 3     for (int i = 1; i <= n; i ++) cin >> a[i];
 4     sort(a + 1, a + n + 1);
 5 
 6     for (int i = 1; i < n; i ++)
 7         if (a[i] >= a[i + 1])
 8             return false;
 9 
10     return true;
11 }
12 
13 int main() {
14     ios::sync_with_stdio(false);
15     cin.tie(nullptr);
16 
17     int t; cin >> t;
18     while (t --) {
19         if (solve()) cout << "YES" << endl;
20         else cout << "NO" << endl;
21     }
22     return 0;
23 }

C.Stripes
暴力判断，题目说R只能横，B只能竖，仔细研究可以发现最后一个被涂的竖或横一定是全是一种颜色，不会被覆盖任何一格。

 1 void solve() {
 2     for (int i = 1; i <= 8; i ++) scanf("%s", g[i] + 1);
 3 
 4     char ans = 'B';
 5     for (int i = 1; i <= 8; i ++) {
 6         bool flag = true;
 7         char c = 'R';
 8         for (int j = 1; j <= 8; j ++) 
 9             if (g[i][j] != c) {
10                 flag = false;
11                 break;
12             }
13 
14         if (flag) {
15             ans = c;
16             break;
17         }
18     }
19     cout << ans << endl;
20 }

D.Coprime

(1)首先第一个思路肯定是暴力用两重循环判断如果最大公约数为1则为共素然后取最大值就行了，但是注意 n 最大值为 2e5,这样做时间复杂度为 O(n^2)，会TLE，所以不可取

(2)发现 ai 的范围为 1 ~ 1000， 虽然有 2e5 的数，但是他们的范围只有 1000， 所以可以先把这1000范围内的数的下标给存起来，然后两重循环枚举这 1000 个数，取下标之和最大值就行了

 1 const int N = 1e3 + 5;
 2 
 3 int idx[N];
 4 
 5 int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
 6 
 7 void solve() {
 8     memset(idx, -1, sizeof idx);
 9     int n; cin >> n;
10     for (int i = 1; i <= n; i ++) {
11         int x; cin >> x;
12         idx[x] = i;
13     }
14 
15     int ans = 0;
16     for (int i = 1; i <= 1000; i ++)
17         for (int j = 1; j <= 1000; j ++) {
18             int a = idx[i], b = idx[j];
19             if (~a && ~b && gcd(i, j) == 1) ans = max(ans, a + b);
20         }
21     
22     if (!ans) ans = -1;
23     cout << ans << endl;
24 }

第 19 行 ~a 的意思为 a != -1, 因为负数在存储中为补码，-1 的补码为 全1， ~为取反符号，所有数取反之后只有 -1 为 0， y总在基础课或者提高课中讲解过。

E.Scuza

题意:给你一个数组表示楼梯，a[i] 表示第 i 个楼梯和第 i − 1 个楼梯相差多高，给你一堆人，每个人有他的腿长 ki，当楼梯差比他的腿长大时，它就无法翻过，问你每个人最多能爬多高。

思路:首先给出 p 个人，这 p 个人中腿长的人爬的高度一定是大于等于腿短的人的高度，这时候就可以想到双指针算法，但是题目要求按顺序输出每个人爬的最大高度，所以要存一下每个人答案的索引

注意数据会爆 int, 要开 long long

pair<int,int> 排序是首先按第一元素，第一元素相同再按第二元素，sort 默认从小到大排序。

32行 " \n"[i == q] 的意思是 若满足 i == q 则输出双引号中的第一个字符（空格），否则输出第二个字符（换行）

 1 #define endl '\n'
 2 #define fx first
 3 #define fy second
 4 #define LL long long
 5 #define ph push_back
 6 #define INF 0x3f3f3f3f
 7 #define PII pair<int,int>
 8 
 9 const int N = 2e5 + 5;
10 
11 int n, q;
12 int a[N];
13 PII b[N];
14 LL s[N], ans[N];
15 
16 void solve() {
17     cin >> n >> q;
18     for (int i = 1; i <= n; i ++) cin >> a[i], s[i] = s[i - 1] + a[i];
19     for (int i = 1; i <= q; i ++) {
20         int x; cin >> x;
21         b[i] = {x, i};
22     }
23     
24     sort(b + 1, b + q + 1);
25 
26     for (int i = 1, j = 1; i <= q; i ++) {
27         int x = b[i].first, y = b[i].second;
28         while (a[j] <= x && j <= n) j ++;
29         ans[y] = s[j - 1];
30     }
31 
32     for (int i = 1; i <= q; i ++) cout << ans[i] << " \n"[i == q];
33 }

F.Smaller

首先 s 字符串 有 'a'， 那么 t 字符串一旦有 大于 'a' 的字符就一定可以，若 t 中 只有 'a' 字符且 s 中只有 ’a' 字符且长度小于等于 t 字符长度也可以，否则就不行

数据会爆 int 开 long long

 1 void solve() {
 2     int op; cin >> op;
 3 
 4     char s = 'a', t = 'a';
 5     LL cnts = 1, cntt = 1;
 6     bool flag = true;
 7 
 8     while (op --) {
 9         int d, k; cin >> d >> k;
10         string temp; cin >> temp;
11 
12         if (d == 1) {
13             for (int i = 0; i < temp.size(); i ++) {
14                 if (temp[i] == s) cnts += k;
15                 else flag = false;
16             }
17         }
18         else {
19             for (int i = 0; i < temp.size(); i ++) {
20                 if (temp[i] > t) {
21                     t = temp[i];
22                     cntt = k;
23                 }
24                 else if (temp[i] == t) cntt += k;
25             }
26         }
27 
28         if (s < t) cout << "YES" << endl;
29         else {
30             if (flag && cnts < cntt) cout << "YES" << endl;
31             else cout << "NO" << endl;
32         }
33     }
34 }

G. Orray

题意：求前缀或数组字典序最大值

思路：这样的复杂度看起来是 O(n^2),会TLE，但是其实细想的话数据最大值为1e9，在二进制下最多31位为1，当所有位都或运算为1后，再或运算所有数都没有用了，值并不改变，所以maxv == ans就break了，时间复杂度并不高，不会TLE

 1 const int N = 2e5 + 5;
 2 
 3 int n;
 4 int a[N];
 5 bool st[N];
 6 
 7 void solve() {
 8     cin >> n;
 9     memset(st, 0, sizeof st);
10 
11     int ans = 0, pos;
12     for (int i = 1; i <= n; i ++) {
13         cin >> a[i];
14         if (a[i] > ans) ans = a[i], pos = i;
15     }
16 
17     st[pos] = true;
18     cout << ans << ' ';
19     while (1) {
20         int maxv = -1;
21 
22         for (int i = 1; i <= n; i ++) {
23             if (st[i]) continue;
24             if ((ans | a[i]) > maxv) {
25                 maxv = ans | a[i];
26                 pos = i;
27             }
28         }
29         if (maxv == ans || maxv == -1) break;
30 
31         ans = maxv, st[pos] = true;
32         cout << a[pos] << ' ';
33     }
34     for (int i = 1; i <= n; i ++)
35         if (!st[i]) 
36             cout << a[i] << ' ';
37     cout << endl; 
38 }