参考http://hi.baidu.com/z917912363/blog/item/26c1e7d2b09f3c3a06088b21.html
题目大意是:一个由0,1组成的数字串~~,现在你问一个人,第i位到第j位的1的个数为奇数还是偶数。一共会告诉你几组这样的数
要你判断前k组这个人回答的都是正确的,到第k+1组,这个人说的是错的,要你输出这个k,要是这个人回答的都是正确的,则输出组数
解题思路,并查集+动态规划
加入第i位到第j位为偶数个1,那么第1位到第i-1位和第1位到第j位1的个数同奇同偶
如果为奇数个1,那么第1位到第i-1位和第1位到第j位1的个数互异,即一个为奇,一个为偶。
设r[i]表示第1位到第i位的1个数的奇偶状况,r[i] = 0表示有偶数个1,r[i] = 1表示有奇数个1。
那么要是第i位到第j位为偶数个1时,r[i-1] = 1, r[j] = 1 或r[i-1] = 0, r[j] = 0 所以 r[i-1] ^ r[j] = 0
要是为奇数个1时,r[i-1] = 1, r[j] = 0 或 r[i-1] = 0, r[j] = 1所以r[i-1] ^ r[j] = 1
看到有1000000000位,而给的区间个数为5000个,给的区间点最多为10000个,所以用离散化hash,来hash方法用桶hash给每个区间点一个序号。
判断给出的区间段正确与否,假如之前给出的连续3个区间段组成了[a,b][b,c],[c,d]这个连续段,,当前的区间的两个点只有是(a,b,c,d)中的两个时,才能确定正确与否其他情况都不能确定
当前区间,能和之前的区间组成连续的区间时要合并它们,自然想到用并查集来解,(感觉线段树也能解决),没一个区间组成一个集合,能组成连续区间的集合合并成一个集合
离散化后r[i]的i映射为区间的点。r[i]初始化为0,合并区间的两个点,让低位的点作为父结点。每个集合的父结点的r始终为0
在findSet(int x)的时候
{
if(x != parent[x])
{
int tmp = findSet(parent[x]);
r[x] ^= r[parent[x]];
parent[x] = tmp;
}
return parent[x];
}
r[x] ^= r[parent[x]];是为了把父结点的状态传递子结点x
这是因为在合并的时候
bool unionSet(int x, int y)
{
int px = findSet(x), py = findSet(y);
if(px != py)
{
parent[py] = px;
r[py] = r[x] ^ r[y] ^ v;
return false;
}
return true;
}
r[py] = r[x] ^ r[y] ^ v;
[x, y]区间的状态保存在父y的父结点py里
#include <iostream> #include <cstdio> #include <cstring> using namespace std; struct node { int num, value, next; }; const int maxn = 1000010; int head[maxn], parent[maxn], r[maxn], e, num, n, m, v; node edge[maxn]; int hash(int x); int findSet(int x); bool unionSet(int x, int y); int main() { char s[10]; int hx, hy; bool flag = false; e = 0; num = 0; memset(head, -1, sizeof(head)); for(int i = 0; i < maxn; i++) parent[i] = i; scanf("%d %d", &n, &m); for(int i = 0; i < m; i++) { int x, y; scanf("%d %d %s", &x, &y, s); v = 0; if(s[0] == 'o') v = 1; hx = hash(x - 1); hy = hash(y); if(unionSet(hx, hy)) { if((r[hx] ^ r[hy]) != v) { printf("%d\n", i); flag = true; break; } } } if(!flag) printf("%d\n", m); return 0; } int hash(int x) { int h = x % maxn; for(int i = head[h]; i != -1; i = edge[i].next) { if(x == edge[i].value) return edge[i].num; } edge[e].value = x; edge[e].num = num++; edge[e].next = head[h]; head[h] = e++; return (num - 1); } int findSet(int x) { if(x != parent[x]) { int tmp = findSet(parent[x]); r[x] ^= r[parent[x]]; parent[x] = tmp; } return parent[x]; } bool unionSet(int x, int y) { int px = findSet(x), py = findSet(y); if(px != py) { parent[py] = px; r[py] = r[x] ^ r[y] ^ v; return false; } return true; }