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;
}