0%

Codeforces Round 827 (Div. 4)

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;
}
//cout << i << ' ' << j << endl;
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;
}
//cout << i << ' ' << j << endl;
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]; //只存max
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 ();
//test ();
int t;
cin >> t;
while (t --) solve ();
}


//预处理1-1000互素

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 << "pos=" << pos << endl;
cout << sum[pos - 1] << ' ';
}
cout << endl;
}

signed main () {
int t;
cin >> t;
while (t --) solve ();
}

//如果a[i]>= x就可以加入

F. Smaller

因为rearrange是打乱顺序,全部重排,为了使得s尽可能小,我们一定会把’a’放在最前面;为了使得t尽可能大,我们一定会把t中最大的字符放在前面。
那么思路就出来了,对于每次新增,只需记录新加入了多少个字符(这是为了二者全为a的时候比较长度)。
情况可划分为:

  1. t中存在一个比’a’大的字符,则 YES,因为s第一个一定是a,而t得第一个不是。
  2. t中不存在比’a’大的字符,即t全为’a’,s中存在比’a’大的字符,则 NO,不管怎么排都有 s > t。
  3. t和s中都不存在比’a’大的字符,即s,t全为’a’,则统计二者长度,更长的字典序更大。
  4. 其余情况均为 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 ();
}

我是大傻逼呜