POJ 1733 Parity game

题意：对一个只由1和0组成的字符串，给出指令，a b even/odd，表示字符串中第a位到第b位之间的1的个数为even/odd(偶数/奇数)。给出m个指令，a,b <= 10^9，问第一个与前面指令矛盾的指令是哪一个，如果没有与前面矛盾的指令，就输出m。若m为0，则输出m。

解法：类似POJ 1182。首先设函数g(x)表示字符串的前x位含有1的个数，令g(0) = 0。则指令a b even/odd的信息转化为g(a-1)和g(b)的奇偶性是否相同。所以，建一个树，每个节点有两个参数，参数f表示其父亲节点的编号，参数r表示它与父亲节点的奇偶性是否相同。(0表示相同，1表示不同)。

　　　由于题目数据太大，a,b <= 10^9，但是m <= 5000，所以要离散化处理。

tag：并查集

  1 /*
  2  * Author:  Plumrain
  3  * Created Time:  2013-11-27 17:53
  4  * File Name: DS-POJ-1733.cpp
  5  */
  6 #include <iostream>
  7 #include <cstdio>
  8 #include <algorithm>
  9 #include <vector>
 10 #include <map>
 11 
 12 using namespace std;
 13 
 14 #define PB push_back
 15 
 16 struct temp{
 17     int a, b;
 18     bool x;
 19     char s[10];
 20 };
 21 
 22 struct node{
 23     int f, r;
 24 };
 25 
 26 int n, m, all;
 27 vector<int> ttt;
 28 map<int, int> mp;
 29 node a[10005];
 30 temp tt[5005];
 31 
 32 void init()
 33 {
 34     mp.clear();
 35     ttt.clear();
 36 
 37     scanf ("%d", &m);
 38 
 39     if (!m)
 40         return;
 41     
 42     for (int i = 0; i < m; ++ i){
 43         scanf ("%d%d%s", &tt[i].a, &tt[i].b, tt[i].s);
 44 
 45         if (tt[i].a > tt[i].b)
 46             swap(tt[i].a, tt[i].b);
 47 
 48         -- tt[i].a;
 49         if (tt[i].s[0] == 'e') tt[i].x = 0;
 50         else tt[i].x = 1; 
 51         ttt.PB (tt[i].a); ttt.PB (tt[i].b);
 52     }
 53     
 54     sort(ttt.begin(), ttt.end()); 
 55     int tmp = ttt[0], sz = ttt.size();
 56     all = 0;
 57     mp[tmp] = all++;
 58     for (int i = 1; i < sz; ++ i) if (ttt[i] != tmp){
 59         tmp = ttt[i];
 60         mp[tmp] = all++;
 61     }
 62 
 63     for (int i = 0; i < all; ++ i){
 64         a[i].f = i;
 65         a[i].r = 0;
 66     }
 67 }
 68 
 69 int find(int x)
 70 {
 71     if (x != a[x].f){
 72         int y = a[x].f;
 73         a[x].f = find(a[x].f);
 74         a[x].r = (a[x].r + a[y].r) % 2;
 75     }
 76     return a[x].f;
 77 }
 78 
 79 void merge(int ta, int tb, bool x, int fa, int fb)
 80 {
 81     a[fb].f = fa;
 82     a[fb].r = (a[ta].r + a[tb].r + x) % 2;
 83 }
 84 
 85 bool ok(int ta, int tb, bool x, int fa, int fb)
 86 {
 87     return x == ((a[ta].r + a[tb].r) % 2);
 88 }
 89 
 90 int gao()
 91 {
 92     bool x;
 93     int ta, tb, fa, fb;
 94     for (int i = 0; i < m; ++ i){
 95         ta = mp[tt[i].a]; tb = mp[tt[i].b]; x = tt[i].x;
 96         fa = find(ta); fb = find(tb);
 97 
 98         if (fa != fb)
 99             merge(ta, tb, x, fa, fb);
100         else
101             if (!ok(ta, tb, x, fa, fb)) return i;
102     }
103     return m;
104 }
105 
106 int main()
107 {
108     int n;
109     while (scanf ("%d", &n) != EOF){
110         init();
111         if (!m) printf ("0
");
112         else printf ("%d
", gao());
113     }
114     return 0;
115 }

View Code

------------------------------------------------------------------
现在的你，在干什么呢？
你是不是还记得，你说你想成为岩哥那样的人。