自动搬运

查看原文

来自洛谷，原作者为

	houzhiyuan 花谢花飞花满天，红消香断有谁怜？

搬运于2025-08-24 22:15:47，当前版本为作者最后更新于2020-03-14 21:36:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

Parity Game

这题需要用到：种类并查集（也叫扩展域），离散化。

不了解并查集的请移步

关于本题主要做法

由于数列中只有 $0$ 或 $1$，那么使先开一个 $s$ 数组表示前缀和，那么：

$s[j]-s[i-1]$ 是奇数时，则 $[i..j]$ 区间中的 $1$ 的个数为奇数，反之，为偶数。

区间的关系是已知的，而 $s$ 是未知的，那么就可以用区间的条件来限定前缀和，如果出现奇偶性的矛盾，就可以直接输出。

关于种类并查集

扩展域，顾名思义，就是将原来并查集扩大，已达到储存每个元素的多个关系。

如本题就要记录与自己相同的和与自己不同的，就将 $f$ 数组开大到原来的两倍，用 $f[i]$ 表示与自己奇偶性相同的集合，用 $f[i+n]$ 表示与 $i$ 奇偶性不同的元素集合。

代码实现：

合并相同的元素：

if(getfather(x)==getfather(y)){//x和y不同，矛盾
	cout<<i-1;
	return 0;
}
else{
	hebing(x,y);
	hebing(x+n,y+n);//与x不同的集合也和y不同
}

合并不同的元素：

if(getfather(x)==getfather(y)){//x和y相同，矛盾
	cout<<i-1;
	return 0;
}
else{
	hebing(x+n,y);
	hebing(x,y+n);//与x不同的集合和y相同，与y不同的集合和x相同
}

关于离散化

这是一个比较基础的算法。

当数据范围特别大时且真正用到的数有比较少的时候，就可以用当前元素排序后在数组中的编号来代替原来的元素。

首先需要认识两个 STL 函数（c 党的福利）。

unique：将数组去重，并返回去重后最后一个元素的地址。

lower_bound：对一个有序的序列，二分查找第一个大于等于当前值的元素的地址。

当然还要用 sort。

具体代码实现：

for(int i=1;i<=n;i++){
   cin>>a[i];
   b[i]=a[i];
}
sort(b+1,b+n+1);
l=unique(b+1,b+n+1)-b-1;//l表示去重后剩下的元素个数
for(int i=1;i<=n;i++){
   cout<<lower_bound(b+1,b+l+1,a[i])-b;//查找序号并输出
}

下面给出AC代码：

#include<bits/stdc++.h>
using namespace std;
struct hzy{
	int x,y,z;
}a[200001];
int f[200001],n,m,b[200001],l;
int zuxian(int k){//并查集函数，注意路径压缩
	return f[k]==k?k:f[k]=zuxian(f[k]);
}
void hebing(int x,int y){//合并函数
	int x1=zuxian(x);
	int x2=zuxian(y);
	if(x1!=x2){
		f[x1]=x2;
	}
}
int main() {
	cin>>n>>m;
	string ch;
	for(int i=1; i<=m; i++) {
		cin>>a[i].x>>a[i].y>>ch;
		a[i].x--;//方便后面运算，这里直接减1
		if(ch[0]=='o') {//相同和不同要搞清楚
			a[i].z=1;
		} else {
			a[i].z=0;
		}
		b[++l]=a[i].x;
		b[++l]=a[i].y;
	}
	sort(b+1,b+l+1);
	l=unique(b+1,b+l+1)-b-1;
	for(int i=1;i<=l*2;i++){
		f[i]=i;
	}
	for(int i=1; i<=m; i++) {
		a[i].x=lower_bound(b+1,b+l+1,a[i].x)-b;//离散化
		a[i].y=lower_bound(b+1,b+l+1,a[i].y)-b;
		if(a[i].z==0){//种类并查集，分相同和不同操作
			if(zuxian(a[i].x)==zuxian(a[i].y+l)){//如果两个数奇偶性不同，矛盾，输出
				cout<<i-1;
				return 0;
			}
			else{//不然就合并集合
				hebing(a[i].x,a[i].y);
				hebing(a[i].x+l,a[i].y+l);
			}
		}
		else{
			if(zuxian(a[i].x)==zuxian(a[i].y)){//同理
				cout<<i-1;
				return 0;
			}
			else{
				hebing(a[i].x,a[i].y+l);
				hebing(a[i].x+l,a[i].y);
			}
		}
	}
	cout<<m;
	return 0;
}//完结撒花