本文共 1133 字，大约阅读时间需要 3 分钟。

原题链接：

紫书上说的很清楚，如果输出恒为0或1，直接输出任意常数序列即可。如果是x或非x，全0序列和全1序列的结果相反，那么从100…0到111…1之间必定存在某个1…00…0使得结果和全1序列相等而1…10…0结果和全0序列相等，那么这最后一个1的位置就是x的位置，答案即1…1x…0。x一定可以是只存在1个的。

很奇怪的是bool那行必须开这么大的数组，不然会TLE。

#include
   
    using namespace std;const int maxm=4e5+5;int d,n,m,a[maxm];bool x[maxm],out[maxm],res[2],vis[maxm];int dfs(int rt){   	if(rt==m)memset(vis,false,sizeof(vis));	if(rt<0)return x[-rt];	if(vis[rt])return out[rt];	int lson=a[2*rt-1],rson=a[2*rt];	int x1=dfs(lson);	int x2=dfs(rson);	vis[rt]=true;	return out[rt]=!(x1&x2);}bool check(int num){   	memset(x+1,true,sizeof(int)*num);	memset(x+1+num,false,sizeof(int)*(n-num));	int tres=dfs(m);	return tres==res[0];}int main(void){   	// freopen("in.txt","r",stdin);	scanf("%d",&d);	while(d--){   		scanf("%d%d",&n,&m);		for(int j=1;j<=m;j++)			scanf("%d%d",&a[2*j-1],&a[2*j]);		memset(x,true,sizeof(x));		res[1]=dfs(m);		memset(x,false,sizeof(x));		res[0]=dfs(m);		if(res[0]==res[1]){   			for(int i=1;i<=n;i++)printf("0");			printf("\n");		}else{   			int L=1,R=n,mid=(L+R)>>1;			while(L
    
     >1;			}			int anspos=L-1;			while(check(anspos))anspos++;			for(int i=1;i