poj1733(种类并查集+离散化)

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

题意: 输入n表示有一个长度为n的0,1字符串, m表示接下来有m行输入, 接下来的m行输入中x, y, even表示第x到第y个字符中间1的个数为偶数个, x, y, odd表示第x到第y个字符中间1的个数为奇数个, 若m句话中第k+1是第一次与前面的话矛盾, 输出k;

思路: 若x, y之间1的个数为偶数个, 那么1~x 与1~y中1的个数同奇偶性, 反之则异奇偶性, 我们可以将其理解为若输入x, y, even, 即x, y属于同种, 反之则属于不同种,

用种类并查集就可以啦...不过要注意三点, 一是数据范围1e9, 不能直接用做数组下标, 要先离散化一下; 二是输入的数据中x, y是闭区间, 不好处理, 我们可以将其化为半开区间来处理, (x-1, y] 或者 [x, y+1); 还有就是如果全部正确的话就输出m(这里wa了我好久~)....

代码:

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 #include <map>

 #define MAXN 5010

 using namespace std;

 int rank[*MAXN], pre[*MAXN];

 int find(int x){  //***递归压缩路径

     if(x!=pre[x]){

         int px=find(pre[x]);

         rank[x]=rank[x]^rank[pre[x]];  //***更新rank[x]

         pre[x]=px;

     }

     return pre[x];

 }

 int jion(int x, int y, int d){

     int fx=find(x);

     int fy=find(y);

     if(fx==fy){

         if(rank[x]^rank[y]!=d){

             return ;

         }else{

             return ;

         }

     }else{

         pre[fy]=fx;

         rank[fy]=(rank[x]+rank[y]+d)%;

     }

     return ;

 }

 int main(void){

     map<int, int>mp;

     int n, m, gg=, jj=;

     mp.clear();

     scanf("%d%d", &n, &m);

     for(int i=; i<=*MAXN; i++){

         pre[i]=i;

         rank[i]=;

     }

     for(int i=; i<=m; i++){

         int x, y, d;

         char ch[];

         scanf("%d%d%s", &x, &y, ch);

         if(!mp[x-]){

             mp[x-]=jj++;

         }

         if(!mp[y]){

             mp[y]=jj++;

         }

         if(strstr(ch, "even")){

             d=;

         }else{

             d=;

         }

         if(jion(mp[x-], mp[y], d)&&!gg){

             gg=i;

         }

     }

     if(!gg){

         gg=m+;

     }

     printf("%d\n", gg-);

     return ;

 }

巴特西

poj1733(种类并查集+离散化)

最新文章

热门文章