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 ();
}
|
我是大傻逼呜