发布于 

Codeforces Round 606 (Div. 2, based on Technocup 2020 Elimination Round 4)

OI

感觉这场 Div.2 有点水啊, 为什么我这个 AFO 的选手都能过 5 道题...

A. Happy Birthday, Polycarp!

签到题, 不多说.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int main() {
int tcnt = read();
for (int T = 1; T <= tcnt; T++) {
int n = read();
int t = n;
int dig = 0;
while (t > 0) {
dig++;
t /= 10;
}
int ans = 9 * (dig - 1);
int64 x = 0;
for (int i = 1; i <= dig; i++) {
x *= 10;
x += 1;
}
for (int i = 1; i <= 9; i++) {
if (x * i <= n) ans++;
}
cout << ans << endl;
}
}

B. Make Them Odd

每次贪心处理当前最大的偶数, 优先队列模拟即可.

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
int main() {
int tcnt = read();
for (int T = 1; T <= tcnt; T++) {
int n = read();
priority_queue<int> q;
for (int i = 1; i <= n; i++) {
int x = read();
if (!(x & 1)) q.push(x);
}
int ans = 0;
int c = 0;
while (!q.empty()) {
int u = q.top();
q.pop();
if (u != c) {
c = u;
ans++;
}
if ((u >> 1) & 1) continue;
q.push(u >> 1);
}
write(ans);
putchar('\n');
}
}

C. As Simple as One and Two

不难发现, 对于 one, 删掉 n 总是可行的; 对于 two, 删掉 w 总是可行的; 但是对于 twone 的情况, 最优解是删掉 o

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
int main() {
int tcnt = read();
for (int T = 1; T <= tcnt; T++) {
scanf("%s", s + 1);
int n = strlen(s + 1);
for (int i = 1; i <= n; i++) {
vis[i] = false;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
if (s[i] == 't' && s[i + 1] == 'w' && s[i + 2] == 'o' &&
s[i + 3] == 'n' && s[i + 4] == 'e') {
vis[i + 2] = true;
ans++;
} else if (s[i] == 't' && s[i + 1] == 'w' && s[i + 2] == 'o') {
vis[i + 1] = true;
ans++;
} else if (s[i] == 'o' && s[i + 1] == 'n' && s[i + 2] == 'e') {
vis[i + 1] = true;
ans++;
}
}
write(ans);
putchar('\n');
for (int i = 1; i <= n; i++) {
if (vis[i]) {
write(i);
putchar(' ');
}
}
putchar('\n');
}
}

D. Let's Play the Words?

0011 的不用反转, 只用反转 0110 使得两者数量只差 1 个就总是可行的; 对于能不能翻转直接用 unordered_set 维护. 注意同时包含 0011 并且没有 0110 是无解的, 特判输出(在这里挂了一次).

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
50
51
52
53
int main() {
int tcnt = read();
for (int T = 1; T <= tcnt; T++) {
vector<pair<int, string>> s01, s10;
int c00 = 0, c11 = 0;
int n = read();
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
if (s.front() == '0') {
if (s.back() == '0')
c00++;
else
s01.push_back(make_pair(i, s));
} else {
if (s.back() == '0')
s10.push_back(make_pair(i, s));
else
c11++;
}
}
if (c00 > 0 && c11 > 0 && s01.size() + s10.size() == 0) {
puts("-1");
continue;
}
int d = abs((int)s01.size() - (int)s10.size()) / 2;
if (s01.size() > s10.size()) swap(s01, s10);
unordered_set<string> s;
vector<int> ans;
for (auto i : s01) {
s.insert(i.second);
}
for (auto i : s10) {
if (ans.size() >= d) break;
string rev(i.second.rbegin(), i.second.rend());
if (s.count(rev) == 0) {
ans.push_back(i.first);
s.insert(rev);
}
}
if (ans.size() < d) {
puts("-1");
} else {
write(ans.size());
putchar('\n');
for (auto i : ans) {
write(i);
putchar(' ');
}
putchar('\n');
}
}
}

E. Two Fairs

从两个点分别做一次 DFS 就可以了, 满足要求的点对一定有一个只有 A 能 DFS 到, 另一个只有 B 能 DFS 到, 详情见代码.

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;

typedef long long int64;

const int MAXN = 200010;
const int INF = 0x3f3f3f3f;

class lfs {
public:
lfs(int N) {
n = N;
head = new int[n + 2];
memset(head, -1, (sizeof n) * (n + 2));
ecnt = 0;
}
void adde(int from, int to, int w) {
edge cur;
cur.to = to;
cur.w = w;
cur.next = head[from];
head[from] = ecnt++;
e.push_back(cur);
}
void addde(int a, int b, int w) {
adde(a, b, w);
adde(b, a, w);
}

int64 solve(int a, int b) {
vis1 = new bool[n + 2];
memset(vis1, false, (sizeof false) * (n + 2));
vis2 = new bool[n + 2];
memset(vis2, false, (sizeof false) * (n + 2));
this->a = a;
this->b = b;
dfs(a, 0, vis1);
dfs(b, 0, vis2);
int64 cnt1 = 0, cnt2 = 0;
for (int i = 1; i <= n; i++) {
if (vis1[i] && !vis2[i]) cnt1++;
else if (!vis1[i] && vis2[i]) cnt2++;
}
return (cnt1 - 1) * (cnt2 - 1);
}

~lfs() {
delete[] head;
delete[] vis1;
delete[] vis2;
}

protected:
struct edge {
int to, next, w;
};
vector<edge> e;
int* head;
int ecnt;
int n;
int a, b;
bool* vis1;
bool* vis2;
void dfs(int u, int fa, bool* vis) {
vis[u] = true;
for (int i = head[u]; i != -1; i = e[i].next) {
int v = e[i].to;
if (v != fa && v != a && v != b) {
if (!vis[v]) dfs(v, u, vis);
}
}
}
};

可惜 15 号白天的两场 Div.2 都没时间打了, 不过下个星期六还有一次国人场.