P10546 题解

· · 题解

Problem Link

题目大意

交互器有 n 个点 n-1 条边的有向图，将图视为无向图后是一棵树。

你可以进行如下操作，每次可以翻转若干条边，你会知道这种情况下每个点 u 能被多少个点到达，记为 f_u。

请在 50 次操作内还原整张图，即确定每条边的起点和终点。

数据范围：n\le 10^4。

思路分析

记询问次数 Q=50。

对于树上问题，考虑从叶子出发逐步剥离每个点。

我们要先求出叶子，注意到如果某个叶子 u 到父亲的边是从 u 出发的，那么此时该点 f_u=1。

假如每条边都随机，那么有 \dfrac 12 的概率这个叶子的 f_u=1。

考虑一个经典的技巧，我们对每条边，随机选择 \dfrac Q2 次询问翻转，满足任意两条边的翻转情况都不相同或无交。

那么对于一个叶子结点 u，恰有 \dfrac Q2 次询问中这个点 f_u=1。

对于一个非叶子节点，他的两条出边至少有一个时刻不同向，那么这个点满足 f_u=1 的的询问轮数一定严格 <\dfrac Q2。

那么这样就能每次求出一个叶子结点 u，然后考虑确定 u 到其父亲 v 的边，以及其父亲的编号。

确定 u\to v 的边是简单的，只需要求一条边的翻转状态和这个点 f_u=1 的状态相等即可。

然后考虑找父亲，注意到 f_u>1 时一定有 f_u=f_{v}+1，那么如果一个点在 f_u>1 时总满足 f_u=f_v+1，那么 v 很大概率是 u 的父亲。

考虑什么时候会将一个错误的 w 判断为 u 的父亲，注意到如果某种情况下 f_v=f_w，那么当 v/w 中的一条出边被翻转后，一定有 f_v\ne f_w。

那么我们知道所有情况中 f_v=f_w 的情况出现一定能对应到至少一种 f_v\ne f_w 的情况，因此总概率一定 \le \dfrac 12。

因此判断错误的概率为 2^{-Q/2}，完全可以接受，并且对于每个错误的点，期望查询 \mathcal O(1) 轮的结果就能发现错误。

时间复杂度 \mathcal O(n^2)。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int Q=50,MAXN=10005;
const ll A=(1ll<<Q)-1;
mt19937 rnd(time(0));
ll gen() {
    vector <int> p;
    for(int i=0;i<Q;++i) p.push_back(i);
    shuffle(p.begin(),p.end(),rnd);
    ll z=0;
    for(int i=0;i<Q/2;++i) z|=1ll<<p[i];
    return z;
}
int n,f[Q+5][MAXN],w[Q+5][MAXN],c[MAXN],U[MAXN],V[MAXN];
ll S[MAXN];
bool del[MAXN];
unordered_map <ll,int> E;
signed main() {
    cin>>n;
    for(int i=1;i<n;++i) {
        ll x=gen();
        while(E.count(x)) x=gen();
        S[i]=x,E[x]=i,E[A^x]=-i;
    }
    for(int i=0;i<Q;++i) {
        cout<<"? ";
        for(int u=1;u<n;++u) cout<<(S[u]>>i&1);
        cout<<endl;
        for(int u=1;u<=n;++u) cin>>f[i][u],w[i][u]=1,c[u]+=(f[i][u]==1);
    }
    for(int o=1;o<n;++o) {
        int x=0,y=0;
        for(int u=1;u<=n;++u) if(!del[u]&&c[u]==Q/2) { x=u; break; }
        ll I=0; del[x]=true;
        for(int i=0;i<Q;++i) if(f[i][x]>w[i][x]) I|=1ll<<i;
        for(int u=1;u<=n;++u) if(!del[u]) {
            bool flg=1;
            for(int i=0;i<Q;++i) if((I>>i&1)&&f[i][x]-w[i][x]!=f[i][u]) {
                flg=0; break;
            }
            if(!flg) continue;
            y=u; break;
        }
        for(int i=0;i<Q;++i) if(!(I>>i&1)) w[i][y]+=w[i][x],c[y]+=(w[i][y]==f[i][y]);
        int z=E[I];
        if(z>0) U[z]=x,V[z]=y;
        else U[-z]=y,V[-z]=x;
    }
    cout<<"! ";
    for(int i=1;i<n;++i) cout<<U[i]<<" "<<V[i]<<" ";
    cout<<endl;
    return 0;
}