POJ 1733 Parity game

举报
Linux猿 发表于 2021/08/06 00:32:42 2021/08/06
【摘要】 题目链接~~> 做题感悟:做完这题第一感觉就是并查集的题只要一加深一下就不会了。 解题思路:               给你长度为 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

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。