Codeforces Round #651 (Div. 2)。因为前四个题太水,就不写题解了。

E. Binary Subsequence Rotation

        容易发现一开始就相同的部分不用处理,只处理不同的部分。将两个串不同的成分拿出来,那么它们是取反的关系。由于旋转操作不会改变$0$和$1$的数量,于是它们各自的$0$和$1$数量必须相等,否则无解。
        然后问题就是如何对于这个串,找出最小的旋转次数,可以直接贪心。
        我们定义四个量:$f(x,y)$,其中$x,y$取$0$或$1$,表示当前以$x$开始,以$y$结束的链有多少条。可以发现形如$f(0,1)$和$f(1,0)$的串都可以对应到一个旋转操作上。遍历串,对于一个$0$或$1$,我们总是贪心地将它放到合理的链后面(即尽可能延长向已有的链,而不是开一个新的链)。由于$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
43
44
45
46
47
48
49
50
51
#include <bits/stdc++.h>
#define N 1000005
using namespace std;
int n, sum0[N], sum1[N], dp[2][2], ct;
char s1[N], s2[N], ps[N];

int main()
{
scanf("%d%s%s", &n, s1 + 1, s2 + 1);
for (int i = 1; i <= n; i++) {
if (s1[i] != s2[i]) ps[++ct] = s1[i];
}
n = ct;
int n0 = 0, n1 = 0;
for (int i = 1; i <= n; i++) {
if (ps[i] == '0') {
++n0;
} else {
++n1;
}
}
if (n0 != n1) {
printf("-1");
return 0;
}
for (int i = n; i >= 1; i--) {
sum0[i] = sum0[i + 1] + (ps[i] == '0');
sum1[i] = sum1[i + 1] + (ps[i] == '1');
}
for (int i = 1; i <= n; i++) {
if (ps[i] == '0') {
if (dp[1][1]) {
--dp[1][1], ++dp[1][0];
} else if (dp[0][1]) {
--dp[0][1], ++dp[0][0];
} else {
++dp[0][0];
}
} else {
if (dp[0][0]) {
--dp[0][0], ++dp[0][1];
} else if (dp[1][0]) {
--dp[1][0], ++dp[1][1];
} else {
++dp[1][1];
}
}
}
printf("%d", dp[0][1] + dp[1][0]);
return 0;
}

F. The Hidden Pair

        交互题。
        可以发现,距离和最小的点必然在两个特殊点的路径上。首先来一遍全部点的查询,可以得到这两个特殊点的距离,并且找到一个在它们路径上的点。
        接下来,以这个点为根进行$DFS$,按深度划分所有点。然后二分深度,就可以找到两个特殊点中的一个。
        当我们找到一个特殊点后,以其为根,再来一遍$DFS$,查询对应深度的点,就能找到另一个特殊点。
        以上操作二分需要$10$次查询,还有两次额外查询,最多需要$12$次,其实可以再压缩一次。
        若距离和为$d$,我们可以将二分区间定义为$[\lfloor\frac {d}{2}\rfloor,d]$,这是因为不可能两个特殊点到该点的距离都小于$\lfloor\frac {d}{2}\rfloor$,这样又可以减少一次查询,最多为$11$次。

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
79
80
#include <bits/stdc++.h>
using namespace std;
struct Edge
{
int next, to;
} edge[2005];
int head[1005], cnt, n, D;
vector<int> dep[1005];
inline void add(int x, int y)
{
edge[cnt].next = head[x], edge[cnt].to = y, head[x] = cnt++;
}
inline vector<int> query(vector<int> w)
{
if (w.empty()) {
vector<int> s;
s.push_back(-1);
return s;
}
printf("? %d", w.size());
for (int i : w) printf(" %d", i);
printf("\n");
fflush(stdout);
int a, b;
vector<int> ans;
scanf("%d%d", &a, &b);
ans.push_back(a), ans.push_back(b);
return ans;
}

void DFS(int x, int f, int d)
{
dep[d].push_back(x);
for (int i = head[x]; i; i = edge[i].next) {
if (edge[i].to == f) continue;
DFS(edge[i].to, x, d + 1);
}
}
inline int solve(int x)
{
int now = x;
for (int j = 0; j <= 1000; j++) dep[j].clear();
DFS(x, 0, 0);
vector<int> tmp;
int l = (D >> 1) - 1, r = D + 1, mid;
while (l < r) { //[,)
if (r == l + 1) break;
mid = (l + r) >> 1;
tmp = query(dep[mid]);
if (tmp[0] != -1 && tmp[1] == D)
l = mid, now = tmp[0];
else
r = mid;
}
return now;
}
char opt[15];
int main()
{
int T;
scanf("%d", &T);
while (T--) {
scanf("%d", &n);
for (int i = 1; i <= 1000; i++) head[i] = 0;
cnt = 1;
for (int i = 1, x, y; i < n; i++) scanf("%d%d", &x, &y), add(x, y), add(y, x);
vector<int> tmp;
for (int i = 1; i <= n; i++) tmp.push_back(i);
tmp = query(tmp), D = tmp[1];
int a = solve(tmp[0]);
for (int j = 0; j <= 1000; j++) dep[j].clear();
DFS(a, 0, 0);
tmp = query(dep[D]);
printf("! %d %d\n", a, tmp[0]);
fflush(stdout);
scanf("%s", opt);
if (opt[0] == 'I') return 0;
}
return 0;
}