coderforces E - AND-MEX Walk

很好的题

[

观察样例发现只有0，1，2

大胆猜测是不是也只会有0，1，2

如果不是的话说明某条路径上出现过0，1，2，且是以2，1，0的情况出现的

但是2的末尾是0，和1&不可能得到1，所以假设不成立

]

然后考虑什么时候有0

有0的充分必要条件是对于二进制的每一位，都有一个地方出现一个0

相反的，就是二进制的每一位，至少有一位全是1

对于二进制的每一位建图，如果该边在这位上为1就连接两点

因为我们只考虑连通性所以用并查集维护就可以，开31个并查集:)

然后考虑什么时候有1

有1就是有0但是没有1(?)

要知道前缀和&有个性质——非严格递减

脑补一下前缀和的趋势应该是[一排大于1的数]...[0，0，0，0，0]

这说明在前j位(j>0,下标从0开始)至少有一排全为1[这样能保证前面有的数>1]

那第0位呐？一定要走到边权末位是0的某条边，才能让0出现

为什么0一定会出现？前面已经判掉了没有0的情况了，所以二进制每一位都不会全是1。

做法就把判0的图拿来用，对于j位(1~31)，预处理一个虚点处理“走到边权末位是0的某条边”

这样就能保证[一排大于1的数]...[0，0，0，0，0]

ps,二进制建图还蛮有意思的

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
struct DSU{
	int fa[maxn];
	DSU(){
		for(int i=1;i<maxn;i++) fa[i]=i;
	}// 默认构造 
	int find(int x){
		if(fa[x]!=x) return fa[x]=find(fa[x]);
		else return x;
	}
	void merge(int x,int y){
		int fx=find(x),fy=find(y);
		fa[fx]=fy;
	}
	bool query(int x,int y){
		if(find(x)==find(y)) return true;
		else return false;
	}
}x[35],y[35];
bool mark[maxn];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int a,b;long long w;
		cin>>a>>b>>w;
		for(int j=0;j<=31;j++){
			if(w>>j&1){
				x[j].merge(a,b);
			}
			if(w%2==0){
				mark[a]=mark[b]=true;
			}
		}
	}
	for(int j=0;j<=31;j++){
		y[j].fa[n+1]=n+1;
		y[j]=x[j];
		for(int i=1;i<=n;i++)
		 if(mark[i]) y[j].merge(n+1,i);
	}
	int q;
	cin>>q;
	for(int tc=1;tc<=q;tc++){
		bool over=false;
		int a,b;cin>>a>>b;
		for(int j=0;j<=31;j++){
			if(x[j].query(a,b)==true){
				cout<<0<<endl;
				over=true;
				break;
			}
		}
		if(over) continue;
		for(int j=1;j<=31;j++){
			if(y[j].query(a,n+1)){
				cout<<1<<endl;
				over=true;
				break;
			}
		}
		if(!over){
			cout<<2<<endl;
		}
	}
}