首页 > 代码库 > 【poj1733】 Parity game

【poj1733】 Parity game

2024-08-15 12:50:13   210人阅读

http://poj.org/problem?id=1733 (题目链接)

题意

　　一个由0,1组成的序列，每次给出一段区间的奇偶，问哪一条信息不合法。

Solution

　　并查集。

　　题目中序列的长度有很大，单纯搜索一定会TLE。

　　我们用s[i]表示前i个数的前缀和，那么a b even意味着s[b]和s[a-1]的奇偶性相同。a b odd意味着s[b]与s[a-1]的奇偶性不同。于是我们根据奇偶性的不同，用并查集依次处理他们之间的关系。当某条信息出现与并查集中记录的信息不符合时，则此信息不合法。

　　由于a和b的值可能会非常大，所以我们还需要将它离散化。

代码

// poj1733#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf 2147483640#define Pi 3.1415926535898#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int n,m,p[1000010],fa[1000010],s[1000010],x[1000010],y[1000010],pos[1000010],cnt;char ch[10];int binsearch(int x) {	int tl=1,tr=cnt;	while (tl<=tr) {		int m=(tl+tr)>>1;		if (x==pos[m]) return m;		if (x>pos[m]) tl=m+1;		else tr=m-1;	}}int find(int x) {	if (fa[x]==x) return x;	int f=find(fa[x]);	s[x]=(s[fa[x]]+s[x])&1;	fa[x]=f;	return fa[x];}void unnion(int i) {	s[fa[x[i]]]=(s[x[i]]+p[i])&1;	fa[fa[x[i]]]=y[i];}int main() {	scanf("%d%d",&m,&n);	for (int i=1;i<=n;i++) {		scanf("%d%d",&x[i],&y[i]);		scanf("%s",ch);		if (ch[0]==‘o‘) p[i]=1;		x[i]--;		pos[++cnt]=x[i];		pos[++cnt]=y[i];	}	sort(pos+1,pos+1+cnt);	pos[0]=1;	for (int i=2;i<=cnt;i++) if (pos[i]!=pos[pos[0]]) {pos[0]++;pos[pos[0]]=pos[i];}	cnt=pos[0];	for (int i=1;i<=cnt;i++) fa[i]=i;	for (int i=1;i<=n;i++) {		x[i]=binsearch(x[i]);		y[i]=binsearch(y[i]);		if (find(x[i])==find(y[i])) {if (((s[x[i]]+s[y[i]])&1)!=p[i]) {printf("%d",i-1);return 0;}}		else unnion(i);		}	printf("%d",n);	return 0;}

　　

【poj1733】 Parity game


联系
我们