Codeforces Round #668 (Div. 1)
/ / 阅读耗时 21 分钟 Codeforces Round #668 (Div. 1)。开打div1，既然是div1，就把题解写明白点吧。
A. Balanced Bitstring
要满足题目给定的条件，我们只需要做到下面两点：
- 第一段$k$长度的字段中，$0$和$1$的数量相等。
- $i$和$i+k$位总是相同的。
用归纳法很容易证明它的正确性。
于是，我们可以找出应该相等的位置，然后进行调整，最后判一下第一段能不能使得$0$和$1$数目相等即可。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
using namespace std;
const int N = 500000 + 5;
typedef long long ll;
char op[N];
int n, k;
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%s", &n, &k, op + 1);
int n0 = 0, n1 = 0;
for (int i = 1; i <= k; i++) {
char now = 0;
for (int j = i; j <= n; j += k) {
if (op[j] == '0' || op[j] == '1') {
if (now != 0 && now != op[j]) {
printf("NO\n");
goto tag;
}
if (now == 0) now = op[j];
}
}
for (int j = i; j <= n; j += k) {
if (now != 0) op[j] = now;
}
}
for (int i = 1; i <= k; i++) {
if (op[i] == '0') ++n0;
if (op[i] == '1') ++n1;
}
if (n0 > k / 2 || n1 > k / 2) {
printf("NO\n");
goto tag;
}
printf("YES\n");
tag:;
}
return 0;
}
B. Tree Tag
这个问题需要分情况讨论。
如果$db\leq 2da$，这说明$Bob$无法跳出$Alice$的包围圈，只能被步步逼近，最后必输。
否则，$Bob$便可以跳出$Alice$的包围圈，如果可以做到反复横跳，就必胜。接下来的情况，需要按直径讨论。
如果树的直径不大于$2da$，此时，$Alice$只需要跳到树的直径的中点上，就可以覆盖树的所有节点，此时$Alice$必胜。
否则，就一定有$Alice$无法覆盖到的点，只要有无法覆盖的点，由于$db>2da$，$Bob$就有能力跳过去，进而反复横跳。此时$Bob$必胜。
需要特判一开始$Bob$就在$Alice$包围圈中的情况。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
using namespace std;
const int N = 100000 + 5;
typedef long long ll;
struct Edge
{
int next, to;
} edge[N << 1];
int head[N], cnt = 1, n, a, b, da, db, dp[N], D, gr[N][20], dep[N];
inline void add(int x, int y)
{
edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
void DFS(int x, int fa)
{
dp[x] = 0;
for (int i = head[x]; i; i = edge[i].next) {
if (edge[i].to == fa) continue;
dep[edge[i].to] = dep[x] + 1, gr[edge[i].to][0] = x;
for (int j = 1; j < 20; j++) gr[edge[i].to][j] = gr[gr[edge[i].to][j - 1]][j - 1];
DFS(edge[i].to, x);
D = max(D, dp[x] + dp[edge[i].to] + 1), dp[x] = max(dp[edge[i].to] + 1, dp[x]);
}
}
inline int LCA(int x, int y)
{
if (dep[x] < dep[y]) swap(x, y);
for (int i = 19; i >= 0; i--) {
if (dep[gr[x][i]] >= dep[y]) x = gr[x][i];
}
if (x == y) return x;
for (int i = 19; i >= 0; i--) {
if (gr[x][i] != gr[y][i]) x = gr[x][i], y = gr[y][i];
}
return gr[x][0];
}
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d%d%d%d%d", &n, &a, &b, &da, &db), cnt = 1, D = 0;
for (int i = 1; i <= n; i++) head[i] = 0;
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
dep[1] = 1, DFS(1, 0);
int dis = dep[a] + dep[b] - 2 * dep[LCA(a, b)];
// cout << D << endl;
if (db > 2 * da && D >= 2 * da + 1 && dis > da) {
printf("Bob\n");
} else {
printf("Alice\n");
}
}
return 0;
}
C. Fixed Point Removal
首先处理$b_i=i-a_i$，这样得到的$b_i$即这个数前面还需要删掉几个数，它才能被删。若$b_i<0$，则永远不能删除。
第一次我们只能删除$b_i=0$的数，然后它们的删除会导致之后的某些数也能被删除，引发连锁反应。注意到如果我们总是贪心地先删除能删的最后一个数，就能够得到最优解，此时凡是理论上能删除的数总是能删除。也就是说，只要这个数理论上能被删除，就存在一种方案将它删掉。
如果不修改，我们可以使用$dp$在$O(n)$复杂度下求解，但是一旦修改就有连锁反应，很难降下来复杂度。
此时需要发现题目中隐藏的性质。可以发现这个数能不能被删只和它前面的数有关，我们设置$lim(i)$表示当保留第$lim(i)$位及其之后的数时，$i$位总是能被删除。对于查询$(x,y)$，形式化地说即为：
- $i$位可删等价于$x<lim(i)$。
考虑如何求$lim(i)$。很明显前面被去除（指查询中的$x$）的数越多，这一位越不容易被删，也就是满足单调性。于是我们二分这个位置$mid$，然后考察$mid$到$i-1$中，能被删的有多少，也就是满足$lim\geq mid$的有多少，如果不小于$b_i$，则$i$位是可删除的。这样我们可以根据前面的$lim$推出后面的，其中求$lim$不小于$mid$的数的数量可以使用树状数组，总复杂度为$O(nlog^2n)$，使用树状数组配合倍增可以做到$O(nlogn)$。代码中给出的是$O(nlog^2n)$版本。
求出$lim$之后，问题转化为求一段区间中，$lim$不小于$x$的数有多少个，可以使用主席树在线求，当然也可以离线。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
using namespace std;
const int N = 500000 + 5;
typedef long long ll;
int tr[N], n, lim[N], op[N], q, root[N], V[N * 20], L[N * 20], R[N * 20], cnt;
inline void add(int x)
{
for (int i = x; i <= n; i += i & -i) ++tr[i];
}
inline int sum(int x)
{
int s = 0;
for (int i = x; i >= 1; i -= i & -i) s += tr[i];
return s;
}
int add(int pre, int v, int l = 1, int r = n)
{
int t = ++cnt, mid = (l + r) >> 1;
V[t] = V[pre] + 1, L[t] = L[pre], R[t] = R[pre];
if (l == r) return t;
if (v <= mid) {
L[t] = add(L[pre], v, l, mid);
} else {
R[t] = add(R[pre], v, mid + 1, r);
}
return t;
}
int query(int t1, int t2, int v, int l = 1, int r = n)
{
if (l >= v) return V[t2] - V[t1];
int mid = (l + r) >> 1;
if (v > mid) return query(R[t1], R[t2], v, mid + 1, r);
return query(L[t1], L[t2], v, l, mid) + query(R[t1], R[t2], mid + 1, mid + 1, r);
}
int main()
{
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", op + i), op[i] = i - op[i];
for (int i = 1; i <= n; i++) {
if (op[i] < 0) {
lim[i] = n + 1;
continue;
}
int l = 1, r = i + 1, mid;
while (l < r) { //[,)
if (r == l + 1) break;
mid = (l + r) >> 1;
if (sum(n) - sum(mid - 1) >= op[i])
l = mid;
else
r = mid;
}
lim[i] = l;
if (sum(n) - sum(l - 1) < op[i]) lim[i] = n + 1;
add(lim[i]);
}
for (int i = 1; i <= n; i++) root[i] = (lim[i] == n + 1) ? root[i - 1] : add(root[i - 1], lim[i]);
// for (int i = 1; i <= n; i++) cout << lim[i] << " ";
// cout << endl;
while (q--) {
int x, y;
scanf("%d%d", &x, &y);
printf("%d\n", query(root[x], root[n - y], x + 1));
}
return 0;
}
D. Game of Pairs
当$n$是偶数时，我们选择$First$。
构造$(i,n+i)$这$n$对数。对于每一对，无论选哪一个模$n$都是$i$，这样最后答案模$n$就是$\sum_{i=1}^ni=\frac{n(n+1)}{2}$。若答案为$2n$的倍数，其模$n$为$0$，即：
但是由于$n$是偶数，使得$\frac{n+1}{2}$不是整数，上式不成立，矛盾，于是答案必不可能是$2n$的倍数。
当$n$是奇数时，我们选择$Second$。
首先证明一个性质：
【性质】如果我们能找到一种方案使得和是$n$的倍数，就能找到一种方案使得和是$2n$的倍数。
注意到所有数的和为：
若和$s$是$n$的倍数，那么$s$模$2n$要么是$0$，要么是$n$。对于前者，已经找到了答案，对于后者，我们选没选的那一部分，就能得到答案，于是性质成立。
考虑分组$(i,n+i)$，如果我们能取每一个组中的数各一个，那么它们模$n$就是$\frac{n(n+1)}{2}$，由于$n$是奇数，于是$\frac{n(n+1)}{2}\equiv 0\pmod n$，即满足和为$n$的倍数这个条件。
对于任意给定的情况，上文的选数方案一定是可行的。我们先找到模$n$为$k$的一个数，选出这个数，舍弃与它同组的另一个，若另一个模$n$为$s$，则找另一个模$n$为$s$的数，递归进行，直到出现重复，即一个循环。经过若干个这样的循环后，就可以选出模$n$为$0$到$n-1$的数各一个。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
using namespace std;
const int N = 500000 + 5;
typedef long long ll;
vector<int> vec[N];
int where[N << 1], n, ans[N], vis[N];
int other(int x)
{
return x > n ? x - n : x + n;
}
inline void solve(int x, int d)
{
if (vis[x]) return;
int p = vec[x][vec[x][0] == d];
ans[x] = d, vis[x] = 1;
solve(where[other(p)], other(p));
}
int main()
{
scanf("%d", &n);
if (n % 2 == 0) {
printf("First\n");
fflush(stdout);
for (int i = 1; i <= 2 * n; i++) printf("%d ", i % n == 0 ? n : i % n);
fflush(stdout);
return 0;
}
printf("Second\n");
fflush(stdout);
for (int i = 1, x; i <= 2 * n; i++) scanf("%d", &x), vec[x].push_back(i), where[i] = x;
for (int i = 1; i <= n; i++) {
if (!vis[i]) solve(i, vec[i][0]);
}
int sum = 0;
for (int i = 1; i <= n; i++) sum = (sum + ans[i]) % (2 * n);
if (sum == n) {
for (int i = 1; i <= n; i++) ans[i] = vec[i][vec[i][0] == ans[i]];
}
for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
fflush(stdout);
return 0;
}
E. Bricks
有一个题叫泥泞的牧场，和这个题较类似。不过本题中要求点不能重复覆盖，增加了难度。
先把所有的黑色点覆盖上一个$1\times 1$的砖块，然后考虑合并相邻的两个，这样合并的越多，答案越优。
但是，合并的时候必须满足题目给定的条件，要满足这个条件，不能出现$L$型的砖块。
我们把黑砖边界看成点。对于一个$1\times 1$的砖，如果它的一对邻接边也与两个黑点相邻，那么这两个边界连边。表示它们不能同时删除，现在问题转化为求这个图的最大独立集。
可以证明这个图是一个二分图，它的最大独立集就是点数与最大匹配数的差，而最大匹配数可以用匈牙利算法或者网络流解决。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
78
using namespace std;
const int N = 300000 + 5;
typedef long long ll;
struct Edge
{
int next, to;
} edge[N << 1];
char op[205][205];
int n, m, head[N], cnt = 1, ans, id[205][205][2], ID, c[N], to[N], vis[N], VIS; //0=up,1=left
inline int getId(int x, int y, int p)
{
if (id[x][y][p]) return id[x][y][p];
return id[x][y][p] = ++ID;
}
inline void add(int x, int y)
{
edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
edge[cnt].next = head[y], edge[cnt].to = x, head[y] = cnt++;
}
void DFS(int x)
{
for (int i = head[x]; i; i = edge[i].next) {
if (c[edge[i].to] == -1) c[edge[i].to] = c[x] ^ 1, DFS(edge[i].to);
}
}
int f(int x)
{
for (int i = head[x]; i; i = edge[i].next) {
if (vis[edge[i].to] == VIS) continue;
vis[edge[i].to] = VIS;
if (to[edge[i].to] == 0 || f(to[edge[i].to])) {
to[edge[i].to] = x;
return 1;
}
}
return 0;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) scanf("%s", op[i] + 1);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) ans += op[i][j] == '#';
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (op[i][j] == '.') continue;
if (j > 1 && op[i][j - 1] == '#') getId(i, j, 1);
if (i > 1 && op[i - 1][j] == '#') getId(i, j, 0);
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (op[i][j] == '.') continue;
if (j > 1 && op[i][j - 1] == '#') {
if (i > 1 && op[i - 1][j] == '#') add(getId(i, j, 0), getId(i, j, 1));
if (i < n && op[i + 1][j] == '#') add(getId(i, j, 1), getId(i + 1, j, 0));
}
if (j < m && op[i][j + 1] == '#') {
if (i > 1 && op[i - 1][j] == '#') add(getId(i, j, 0), getId(i, j + 1, 1));
if (i < n && op[i + 1][j] == '#') add(getId(i, j + 1, 1), getId(i + 1, j, 0));
}
}
}
for (int i = 1; i <= ID; i++) c[i] = -1;
for (int i = 1; i <= ID; i++) {
if (c[i] == -1) c[i] = 0, DFS(i);
}
int maxAns = 0;
for (int i = 1; i <= ID; i++) {
if (c[i]) continue;
VIS = i, maxAns += f(i);
}
maxAns = ID - maxAns;
printf("%d", ans - maxAns);
return 0;
}