CF1738F

zac2010 · 2023-09-22 10:45:34 · 题解

这类题着重于抓住充分条件进行构造。

解决这道题，就得抓住题目中最为特殊的条件：s_c\leq {n_c}^2。我们不难找出一种关于它的充分条件：\max_{u\in S_c}d_u\leq n_c。

尝试在此充分条件下设计构造方法：不妨按照 d_u 进行排序，之后从大到小考虑每个未染色的 u。我们逐个对 u 的所有邻节点进行询问。具体的，会有以下情况：

1. 把 $u$ 以及之前询问到的未染色邻节点染上 $v$ 的颜色，并结束对 $u$ 的操作。
2. 无事发生。

时间复杂度 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;
}