这题的大意是对于一个正整数的区间，有若干句话，判断第一句错误的位置，每句话所描述的意思是对于一个区间[a, b]有奇数个1或是偶数个1。[a,b]有1的个数的奇偶性可以通过判断[0,a-1]到[0,b]的奇偶性异同来判断。相同的话，用0表示，不同的话，用1表示。则这种关系是满足传递性的。对于上述转换过来的问题，与原问题是等价的。然后用并查集来维护这之间的关系就可以了。
感谢：
http://hi.baidu.com/yhc0/blog/item/faede08f7095e3f2503d9215.htmlhttp://hi.baidu.com/lilymona/blog/item/16ac11970ebba1037af4801c.html
http://blog.sina.com.cn/s/blog_3f3a72e30100devr.html
代码 #include < iostream > #include < string > #include < vector > #include < map > #include < queue > #include < math.h > using namespace std; const int MAX = 50005 ; struct NODE{ int f, w; NODE() { f = - 1 ; w = 0 ; }}node[MAX]; int a[MAX], b[MAX], c[MAX];map < int , int > mm;vector < int > v; void ready(){ for ( int i = 0 ; i < MAX; i ++ ) node[i] = NODE(); mm.clear();} void hash(vector < int > v){ int cnt = 0 ; sort(v.begin(), v.end()); mm[v[ 0 ]] = cnt ++ ; for ( int i = 1 ; i < v.size(); i ++ ) { if (v[i] != v[i - 1 ]) mm[v[i]] = cnt ++ ; }} int myFind( int x){ if (node[x].f == - 1 ) return x; int f = myFind(node[x].f); node[x].w += node[node[x].f].w; node[x].w %= 2 ; node[x].f = f; return f;} void join( int x, int y, int z){ int xx = myFind(x); int yy = myFind(y); node[yy].f = xx; node[yy].w = (z + node[x].w - node[y].w + 2 ) % 2 ;} int main(){ int K; // while(scanf("%d%d", &K, &K) != EOF) { scanf( " %*d%d " , & K); // vector<int> v; v.clear(); ready(); for ( int i = 0 ; i < K; i ++ ) { string t; scanf( " %d%d " , & a[i], & b[i]); a[i] -- ; v.push_back(a[i]); v.push_back(b[i]); cin >> t; if (t == " even " ) c[i] = 0 ; else c[i] = 1 ; } if (K) hash(v); int j = 0 ; for (j = 0 ; j < K; j ++ ) { a[j] = mm[a[j]]; b[j] = mm[b[j]]; int aa = myFind(a[j]); int bb = myFind(b[j]); if (aa != bb) { join(a[j], b[j], c[j]); } else { if ((node[a[j]].w - node[b[j]].w + 2 ) % 2 != c[j]) break ; } } printf( " %d\n " , j); }}
转载于:https://www.cnblogs.com/litstrong/archive/2010/08/06/1793978.html
