自动搬运

查看原文

来自洛谷，原作者为

	cwfxlh 会赢的！

搬运于2025-08-24 23:11:55，当前版本为作者最后更新于2025-06-21 15:03:50，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P11992 [JOIST 2025] 电路 2 / Circuit 2

可能没有黑啊，感觉不太难。

先考虑没有次数限制，胡一个简单的做法。

我们尝试从上往下确定符号。考虑怎么区分一个节点是 $\texttt{AND}$ 还是 $\texttt{OR}$，显然可以通过输入 $01$ 来确认。如果是 $\texttt{AND}$，输出就是 $0$，否则是 $1$。但是发现，如果返回值的位置不是根节点，是无法读取返回值的。考虑怎么通过确定的元件来把这个值保留地传到根节点。如果接下来一个元件是 $\texttt{OR}$，在这个元件的另一侧传入 $0$。否则将这个返回值取反，在另一侧传入 $1$，同时最终的值取个反。

上面操作涉及到一个问题：怎么做到在传入固定的值。这是简单的，将子树内所有输入全部改为 $0$ 或全部改为 $1$。

这样就做到了线性。确认好的点构成了一个包含根的连通块，每次加入一个儿子，可以确定这个儿子的编号。

考虑能不能更高效一点。我们每次取若干个点，判断其中有没有 $\texttt{OR}$，然后这样就可以二分了。发现，这些点由于不知道符号，所以它们是不适合作为传递关键信息的节点的。

尝试一点简单的结构：取若干条链，并且这些链的链头的祖先链与其他链都不相交。这样的话，对于每条链，我们尝试在链头给出返回值。具体做法如下：在链尾输入 $0$，然后在所有链的另一侧输入 $1$，这样如果里面有 $\texttt{OR}$，那么就会返回 $1$，否则返回 $0$。

剩下的任务就是通过一些确定的符号将这些点的信息合并传到根部。考虑树形 DP 求转移方法，$dp_{i,j}$ 表示子树 $i$ 内的询问点是否有 $\texttt{OR}$ 时，返回的值是多少，要求 $dp_{i,0}$ 与 $dp_{i,1}$ 能够区分。通过做一些反转操作，容易发现这样是必然可以合并的。

于是我们实现了询问。考虑具体该问哪些点，尝试这样做：每次在一个点集里二分第一个 $\texttt{OR}$。令当前确定符号的连通块为 $S$，考虑所有挂在 $S$ 上的链，选若干条长链出来，将这些长链拼在一起二分。但是这样二分的次数太多，设计一个阈值 $B$，每次最多选 B 个点二分。于是询问次数为 $O(R\log B+\frac{n-C}{B}+\sqrt{C})$。

上面询问次数的分析如下：$R\log B$ 指每次二分出一个 $\texttt{OR}$ 所需的次数，剩余的情况就是指询问的所有点都没问题。考虑询问的时候有多少次没问满，令这些没问满的大小和为 $C$，那么问满的次数就是 $\frac{n-C}{B}$，没问满的那些，根据长链的性质，大小一定严格递减，所以询问次数不超过 $\sqrt{C}$。

上面那个式子在 $C$ 取 $O(B^2)$ 大小的时候取到最大，不过那个界没有卡特别满，所以不需要特别精细的分析，我的代码里 $B$ 取了 60 就过了，最多的问了 920 次左右，比较充裕。询问一次时间复杂度是 $O(n)$ 的。

代码：

#include<bits/stdc++.h>
using namespace std;
std::string solve(int NN, int RR, std::vector<int> U, std::vector<int> V);
int query(std::string s);
int n,R,ans[20003],fa[20003],k1,k2,k3,k4,k5,k6,k7,k8,k9,mxdep[20003],qrymk[20003],rev[20003],lft,rgt,mid;
int stk[20003],tots,dp[20003][2],dep[20003];
vector<int>son[20003];
void dfs(int now){
	mxdep[now]=now;
	for(auto i:son[now]){
		if(i>=n)continue;
		dfs(i);
		if(dep[mxdep[i]]>dep[mxdep[now]])mxdep[now]=mxdep[i];
		if(ans[now]!=-1&&ans[i]==-1){
			int u=tots;
			for(int j=mxdep[i];;j=fa[j]){
				stk[++tots]=j;
				if(j==i)break;
			}
			reverse(stk+u+1,stk+tots+1);
		}
	}
	if(ans[now]==-1&&now==0){
		int u=tots;
		for(int j=mxdep[now];;j=fa[j]){
			stk[++tots]=j;
			if(j==now)break;
		}
		reverse(stk+u+1,stk+tots+1);
	}
	return;
}
void mdf(int pos){
	dp[pos][0]^=1;dp[pos][1]^=1;rev[pos]^=1;
	return;
}
void dfs2(int now){
	if(now>=n){
		dp[now][0]=dp[now][1]=0;
		return;
	}
	int u=son[now][0],v=son[now][1];
	dfs2(u);dfs2(v);
	if(qrymk[now]){
		if(dp[v][0]==dp[v][1])swap(u,v);
		if(dp[u][0]==0)mdf(u);
		if(dp[v][0]==1)mdf(v);
		dp[now][0]=0;
		dp[now][1]=1;
	}
	else{
		if(dp[v][0]==dp[v][1])swap(u,v);
		if(dp[u][0]==dp[u][1]&&dp[v][0]==dp[v][1]){
			if(dp[u][0]==0)mdf(u);
			if(dp[v][0]==0)mdf(v);
			dp[now][0]=dp[now][1]=1;
			return;
		}
		if(dp[u][0]==dp[u][1]){
			if(ans[now]==0){if(dp[u][0]==0)mdf(u);}
			else if(dp[u][0]==1)mdf(u);
			dp[now][0]=dp[v][0];dp[now][1]=dp[v][1];
		}
		else{
			if(ans[now]==0){
				if(dp[u][0]==0)mdf(u);
				if(dp[v][0]==0)mdf(v);
				dp[now][0]=1;dp[now][1]=0;
			}
			else{
				if(dp[u][0]==1)mdf(u);
				if(dp[v][0]==1)mdf(v);
				dp[now][0]=0;dp[now][1]=1;
			}
		}
	}
	return;
}
int Query(int pos){
	for(int i=0;i<=n*2;i++)rev[i]=qrymk[i]=0;
	for(int i=1;i<=pos;i++)qrymk[stk[i]]=1;
	dfs2(0);
	string qs="";
	for(int i=0;i<=n*2;i++)qs+=(char)('0'+rev[i]);
	return (query(qs)==dp[0][1]);
}
string solve(int NN,int RR,vector<int> U,vector<int> V) {
	n=NN;R=RR;
	dep[0]=1;
	for(int i=0;i<n;i++){
		son[i].emplace_back(U[i]);
		son[i].emplace_back(V[i]);
		dep[U[i]]=dep[V[i]]=dep[i]+1;
		fa[U[i]]=fa[V[i]]=i;
	}
	for(int i=0;i<n;i++)ans[i]=-1;
	while(1){
		k1=1;
		for(int i=0;i<n;i++)if(ans[i]==-1)k1=0;
		if(k1)break;
		tots=0;
		dfs(0);
		tots=min(tots,60);
		if(!Query(tots)){
			for(int i=1;i<=tots;i++)ans[stk[i]]=0;
			continue;
		}
		lft=1;rgt=tots;
		while(lft<rgt){
			mid=((lft+rgt)/2);
			if(Query(mid))rgt=mid;
			else lft=mid+1;
		}
		for(int i=1;i<lft;i++)ans[stk[i]]=0;
		ans[stk[lft]]=1;
	}
	string ret="";
	for(int i=0;i<n;i++){
		if(ans[i])ret+='|';
		else ret+='&';
	}
    return ret;
}