题解 P5937 【[CEOI1999]Parity Game】
houzhiyuan
·
·
题解
Parity Game
这题需要用到：种类并查集（也叫扩展域），离散化。
不了解并查集的请移步
关于本题主要做法
由于数列中只有 0 或 1，那么使先开一个 s 数组表示前缀和，那么：
区间的关系是已知的，而 $s$ 是未知的，那么就可以用区间的条件来限定前缀和，如果出现奇偶性的矛盾，就可以直接输出。
### 关于种类并查集
扩展域，顾名思义，就是将原来并查集扩大，已达到储存每个元素的多个关系。
如本题就要记录与自己相同的和与自己不同的，就将 $f$ 数组开大到原来的两倍，用 $f[i]$ 表示与自己奇偶性相同的集合，用 $f[i+n]$ 表示与 $i$ 奇偶性不同的元素集合。
代码实现：
合并相同的元素：
```cpp
if(getfather(x)==getfather(y)){//x和y不同，矛盾
cout<<i-1;
return 0;
}
else{
hebing(x,y);
hebing(x+n,y+n);//与x不同的集合也和y不同
}
```
合并不同的元素：
```cpp
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。~~
具体代码实现：
```cpp
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代码：**
```cpp
#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;
}//完结撒花
```