自动搬运

查看原文

来自洛谷，原作者为

	DaiRuiChen007 白鸟白鸟 不要回头望 你要替我飞去那地方 一去那地方 那是你我共同故乡

搬运于2025-08-24 22:59:03，当前版本为作者最后更新于2024-09-14 16:04:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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