POJ 1733 Parity game
【摘要】 题目链接~~>
做题感悟:做完这题第一感觉就是并查集的题只要一加深一下就不会了。
解题思路:
给你长度为 n 的 0 和 1 组成的字符串,然后问给你许多条件 x ~ y 之间(包括x , y )...
做题感悟:做完这题第一感觉就是并查集的题只要一加深一下就不会了。
解题思路:
给你长度为 n 的 0 和 1 组成的字符串,然后问给你许多条件 x ~ y 之间(包括x , y )有奇数个 1 或偶数个 1 ,基于以前的条件判断是否正确(只要存在一种情况正确就可以).首先对于 x ~ y 如果你知道 x~z 的奇偶性(即 1 的个数的奇偶性)同时知道 y~z 的奇偶性,从而就可以判断 x~y 的奇偶性。
例如:x ~ z 为偶数个(用 0 表示),y ~ z 为奇数个(用 1 表示),那么x ~ y 必定奇数个。这样可以用异或来表示: T[x].relation ^ T[y].relation .
判断时:如果 find( x ) = = find( y ) 只要异或一下看是否等于输入的奇偶性就可以了。 否则,合并 x y 所在集合。
因为 n 很大开数组开不下,而m可以开的下,so 用map 离散化。
代码:
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
const double PI = 3.1415926 ;
const int INF = 99999999 ;
const int MX =100006 ;
int n,mx ;
struct node
{
int parent,relation ;
}T[MX] ;
void init() // 初始化
{
for(int i=0 ;i<MX ;i++)
{
T[i].parent=i ;
T[i].relation=0 ;
}
}
int find(int x) // 寻找父亲 同时更新节点信息
{
if(T[x].parent!=x)
{
int temp=T[x].parent ;
T[x].parent=find(temp) ;
T[x].relation=T[x].relation^T[temp].relation ;
return T[x].parent ;
}
return T[x].parent ;
}
int main()
{
int x,y,r=0,i,c ;
char s[20] ;
map<int,int>m ;
scanf("%d%d",&n,&mx) ;
init() ;
for(i=1 ;i<=mx ;i++)
{
scanf("%d%d%s",&x,&y,s) ;
if(s[0]=='e')
c=0 ;
else c=1 ;
x-- ;
if(m.find(x)==m.end()) // 因为 n 很大 so 用map离散化
m[x]=r++ ;
if(m.find(y)==m.end())
m[y]=r++ ;
x=m[x] ;
y=m[y] ;
int ax=find(x) ; // 寻找父亲
int ay=find(y) ;
if(ax==ay) // 父亲相同
{
if((T[x].relation^T[y].relation)!=c)
break ;
}
else
{
T[ay].parent=ax ;
T[ay].relation=T[x].relation^T[y].relation^c ;
}
}
printf("%d\n",i-1) ;
return 0 ;
}
文章来源: blog.csdn.net,作者:Linux猿,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/nyist_zxp/article/details/22513325
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)