这类题着重于抓住充分条件进行构造。
解决这道题，就得抓住题目中最为特殊的条件：\(s_c\leq {n_c}^2\)。我们不难找出一种关于它的充分条件：\(\max_{u\in S_c}d_u\leq n_c\)。
尝试在此充分条件下设计构造方法：不妨按照 \(d_u\) 进行排序，之后从大到小考虑每个未染色的 \(u\)。我们逐个对 \(u\) 的所有邻节点进行询问。具体的，会有以下情况：
-
\(u\) 的邻节点是染过色的
把 \(u\) 以及之前询问到的未染色邻节点染上 \(v\) 的颜色，并结束对 \(u\) 的操作。
-
\(u\) 的邻节点未染色
无事发生。
时间复杂度 \(O(n)\)。
点击查看代码
#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e5 + 10;
int n, u, col, d[N], c[N], id[N];
vector<int> v;
bool cmp(const int &i, const int &j){return d[i] > d[j];}
void solve(){
cin >> n, col = 0;
FL(i, 1, n) cin >> d[id[i] = i], c[i] = 0;
sort(id + 1, id + n + 1, cmp);
FL(i, 1, n) if(!c[id[i]]){
vector<int>().swap(v), u = id[i];
FL(j, 1, d[id[i]]){
cout << "? " << id[i] << endl;
cin >> u; if(c[u]) break;
v.emplace_back(u);
}
c[id[i]] = c[u]? c[u] : ++col;
for(const int &x: v) c[x] = c[id[i]];
}
cout << "! ";
FL(i, 1, n) cout << c[i] << " ";
cout << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T; cin >> T;
while(T--) solve();
return 0;
}