Codeforces Round #668 (Div. 1)

        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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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
#include <bits/stdc++.h>
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;
}

0%