【过题记录】 7.17

Parity Game

算法：并查集(带权并查集||扩展域并查集)

简要分析：

一、带权并查集
不难发现，奇偶性的关系就等同于异或
因此我们可以让并查集的边权为1/0表示当前是偶数个1还是奇数个1
做一遍带权并查集即可。
对于每一个问题，如果两个数在同一集合内，说明可以确定关系，判断异或和是否为想要的答案即可。
如果不是，就合并。(注意合并思路)
注意到n很大，但是m很小，可以先将询问输入，而后离散化。

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+100;
int a[N],cnt;
struct Node{
	int l,r,v;
}q[N];
int n,Q;
int fa[N],d[N];

int getfa(int x){
	if (x == fa[x]) return fa[x];
	int rt = getfa(fa[x]);
	d[x]^=d[fa[x]];
	fa[x] = rt;
	return fa[x];
}

int main(){
	scanf("%d %d",&n,&Q);
	for (int i = 1; i <= Q; i++){
		string s1;
		cin>>q[i].l>>q[i].r>>s1;
		if (s1 == "odd") q[i].v = 1;
		else q[i].v = 0;
		a[++cnt] = q[i].l-1; a[++cnt] = q[i].r;
	}
	sort(a+1,a+cnt+1);
	cnt = unique(a+1,a+cnt+1)-a-1;
	for (int i = 1; i <= cnt; i++) fa[i] = i;
	for (int i = 1; i <= Q; i++){
		int x = lower_bound(a+1,a+cnt+1,q[i].l-1)-a;
		int y = lower_bound(a+1,a+cnt+1,q[i].r)-a;
		int X = getfa(x) , Y = getfa(y);
		if (X == Y){
			if (d[x]^d[y]!=q[i].v){
				cout<<i-1<<endl; return 0;
			}
			continue;
		}
		d[X] = q[i].v^d[x]^d[y];
		fa[X] = Y;
	}
	cout<<Q<<endl;
	return 0;
}

二、扩展域并查集
将一个点拆成两个点
$x_1表示x的同义词域$
$x_2表示x的反义词域$
分别进行并查集操作即可

#include<bits/stdc++.h>
using namespace std;

const int N = 3e5+100;
map < string , int > M;
int fa[N],d[N];
int n,q,m;

int getfa(int x){
	return x == fa[x]?fa[x]:fa[x] = getfa(fa[x]);
} 

int main(){
	int cnt = 0;
	cin>>n>>m>>q;
	for (int i = 1; i <= n; i++){
		string s; cin>>s;
		M[s] = ++cnt;
	}
	for (int i = 1; i <= 2*n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++){
		int op; string s1,s2; cin>>op>>s1>>s2;
		int x = M[s1]; int xx = x+n;
		int y = M[s2]; int yy = y+n;
		op--;
		int X1 = getfa(x) , Y1 = getfa(y); 
		int X2 = getfa(xx) , Y2 = getfa(yy);
		if (op == 0){
			if (X1 == Y2){
				cout<<"NO"<<endl;
				continue;
			}
			cout<<"YES"<<endl;
			fa[X1] = Y1; fa[X2] = Y2;
		}else{
			if (X1 == Y1){
				cout<<"NO"<<endl;
				continue;
			}
			cout<<"YES"<<endl;
			fa[X1] = Y2; fa[X2] = Y1;
		}
	}
	for (int i = 1; i <= q; i++){
		string s1,s2; cin>>s1>>s2;
		int x = M[s1] , y = M[s2];
		int xx = x+n , yy =  y+n;
		int X1 = getfa(x) , X2 = getfa(xx);
		int Y1 = getfa(y) , Y2 = getfa(yy);
		if (X1 == Y1) cout<<1<<endl;
		else if (X1 == Y2) cout<<2<<endl;
		else cout<<3<<endl;
	}
	return 0;
}

Mahmoud and a Dictionary

算法：并查集

简要分析：

与刚刚那题类似，同样可以用带权并查集或者扩展域并查集

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+100;
map < string , int > M;
int fa[N],d[N];
int n,q,m;

int getfa(int x){
	if (x == fa[x]) return x;
	int rt = getfa(fa[x]);
	d[x]^=d[fa[x]];
	return fa[x] = rt;
}

int main(){
	int cnt = 0;
	cin>>n>>m>>q;
	for (int i = 1; i <= n; i++){
		string s; cin>>s;
		M[s] = ++cnt;
	}
	for (int i = 1; i <= n; i++) fa[i] = i;
	for (int i = 1; i <= m; i++){
		int op; string s1,s2;
		cin>>op>>s1>>s2;
		int x = M[s1],y = M[s2];
		int X = getfa(x) , Y = getfa(y);
		if (X == Y){
			int now = d[x]^d[y];
			if (now == (op-1)) cout<<"YES"<<endl;
			else cout<<"NO"<<endl;
			continue;
		}
		cout<<"YES"<<endl;
		op--;
		d[X] = op^d[x]^d[y];
		fa[X] = Y;
	}
	for (int i = 1; i <= q; i++){
		string s1,s2; cin>>s1>>s2;
		int x = M[s1] , y = M[s2];
		int X = getfa(x) , Y = getfa(y);
		if (X == Y){
			int now = d[x]^d[y];
			if (now == 1) cout<<2<<endl;
			else cout<<1<<endl;
		}
		else cout<<3<<endl;
	}
	return 0;
}

，