「JZOJ4807」破解 - 并查集

题目大意

    历经千辛万苦，ddddddpppppp终于找到了IBN5100。
    dp事先了解到SERN共有$T$个密码，每个密码是一个长度为$N$的$01$串，他要利用IBN5100的特殊功能破解SERN的密码。
    初始时，IBN5100中的串每个位置都是$0$。
    这台特殊的IBN5100还提供了$M$个区间$[L_i,R_i]$，每次操作是从给定区间中选择其中一个区间$[L_i,R_i]$,将当前$01$串$[L_i,R_i]$的位置上的数字全部取反。
    dp可以执行上述操作任意次。为了破解出密码，dp想知道这个$01$串最多有多少种可能。
    由于答案可能很大，所以你只需要告诉dp模$10^9+7$后的答案即可。
    注意：每次破解都是独立的。

---

题目分析

又是区间取反，按照套路对区间进行异或差分。
$a[i]=a[i]\,xor\,a[i+1]$
将区间取反问题转化为端点取反操作。

考虑，若两个端点已经执行过取反操作，若再次取反，其方案必定已经计算过，故若需要执行的端点已经取反，则答案无变化。
否则，就有取反与不取反的两种选择，故$ans*=2$。

用并查集判断操作是否执行。

---

代码

代码风格有一定变化呢，因为换了NetBeans做编译器。
刚学会了并查集的黑科技呢。

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const LL Get_Int() {
	LL num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}

const int maxn=10000005;
const LL mod=1e9+7;
int t,n,m,father[maxn];
LL ans=1;

int Get_Father(int x) {
	if(father[x]<0)return x;
	return father[x]=Get_Father(father[x]);
}

bool merge(int x,int y) {
	int fx=Get_Father(x),fy=Get_Father(y);
	if(fx!=fy) {
		if(father[fx]>father[fy])swap(fx,fy);
		father[fx]+=father[fy];
		father[fy]=fx;
		return true;
	} else return false;
}

vector<int>used;

int main() {
	t=Get_Int();
	memset(father,-1,sizeof(father));
	while(t--) {
		ans=1;
		n=Get_Int();
		m=Get_Int();
		used.clear();
		for(int i=1; i<=m; i++) {
			int x=Get_Int()-1,y=Get_Int();
			used.push_back(x);
			used.push_back(y);
			if(merge(x,y))ans=ans*2%mod;
		}
		for(int x:used)father[x]=-1;
		printf("%lld\n",ans);
	}
	return 0;
}