Solution:

本题是比较有意思的，我讲一种较好理解的证明方法。

对于每一个染色的连通块的点集 SS，需要满足以下条件：

∑u:Sdeg(u)≤nS2\sum_{u:S}deg(u) \leq n_S^2

对于每一个操作，我们寻找度数最大的没有被染色的点 uu，依次询问 uu 的临边，如果 uu 的相邻点 vv 被染色了，那么把 uu 和 vv 染成同一种颜色，否则把 uu 和其所有临边染成一种新的颜色。

这种贪心的策略需要证明两种问题：

  • 总的询问次数 ≤n\leq n；
  • 需要满足的上述条件。

· 对于每次询问的度数 deg(i)deg(i) ，

Code:

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
// By 0x0F
#include <bits/stdc++.h>
using namespace std;
//#define int long long
inline int read() {
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while (ch >= '0' && ch <= '9') {x = x * 10 + ch - 48; ch = getchar();}
    return x * f;
}
int deg[1010], col[1010], tot;
void solve() {
    int n = read();
    for (int i = 1; i <= n; i++) deg[i] = read();
    while (1) {
        int maxd = 0, ind = 0;
        for (int i = 1; i <= n; i++)
            if (deg[i] >= maxd && !col[i]) maxd = deg[i], ind = i;
        if (ind == 0) {
            printf("! ");
            for (int i = 1; i <= n; i++) printf("%d ", col[i]);
            printf("\n"); fflush(stdout);
            for (int i = 1; i <= n; i++) col[i] = 0;
            tot = 0;
            break;
        }
        vector<int> vec; int cl = 0;
        vec.push_back(ind);
        for (int i = 1; i <= deg[ind]; i++) {
            printf("? %d\n", ind); fflush(stdout);
            int j = read(); vec.push_back(j);
            if (col[j] && !cl) {cl = col[j]; break;}
        }
        if (!cl) cl = ++tot;
        for (int i:vec) col[i] = cl;
    }
}
int main() {
    int t = read();
    while (t--) solve();
    return 0;
}