题目链接:poj 1733 Parity game
题目大意:给出n,表示有一个长度为n由01组成的序列,给出m次询问,a b odd/even 表示在a~b这个区间上1的个数是奇数还是偶数,找到最先矛盾的那条语句。
解题思路:因为n非常大,但是询问非常小,所以要将点map离散化,我的做法是用两个map来处理,一个是f数组,一个v数组,每次有一个新的区间a b,就让b->a-1,权值为1/0,表示从b到a-1这段上面1的个数为奇数还是偶数,这样就映射成了带权并查集。
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std;
map<int, int> f;
map<int, int> v;
int n, m;
void judge (int x) {
if (f.count(x)) return ;
f[x] = x;
v[x] = 0;
}
int getfar (int x) {
if (x != f[x]) {
int t = f[x];
f[x] = getfar(f[x]);
v[x] = (v[x] + v[t]) % 2;
}
return f[x];
}
int solve () {
int a, b, ans = n;
char str[10];
for (int i = 0; i < n; i++) {
scanf("%d%d%s", &a, &b, str);
if (ans != n) continue;
a--;
judge(a);
judge(b);
int s = (strcmp(str, "odd") == 0) ? 1 : 0;
int p = getfar(a), q = getfar(b);
if (p == q) {
if (s == 1 && v[a] == v[b]) ans = i;
if (s == 0 && v[a] != v[b]) ans = i;
} else {
f[q] = p;
v[q] = (v[b] + 2 + s + v[a])%2;
}
}
return ans;
}
int main () {
while (scanf("%d%d", &m, &n) == 2) {
f.clear();
v.clear();
printf("%d\n", solve ());
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
2. bool nodePath (bstNode* pRoot, int value, std::vector*>& path) 3. { 6
北大POJ1027-The Same Game 解题报告+AC代码
北大POJ1753-Flip Game 解题报告+AC代码
poj 食物链代码.带权并查集,关键是找到其中的一些关系式.
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告
poj 1611 The Suspects 代码 并查集的应用
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
这份代码用C++实现了经典算法并查集,来源于poj题目1182
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
POJ2186-Popular Cows 【Tarjan+极大强连通分量+缩点】 解题报告+AC代码 http://hi.csdn.net/!s/BGDH68 附:我所有的POJ解题报告链接 . http://blog.csdn.net/lyy289065406/article/details/6642573
并查集基础 acm 算法 poj oi 并查集基础.ppt
POJ2528-Mayor's posters 【区间映射压缩(离散化)+线段树】 解题报告+AC代码 http://hi.csdn.net/!s/83XZJU ========> 我的所有POJ解题报告链接: http://blog.csdn.net/lyy289065406/article/details/6642573
POJ1089 并查集可以解决 并查集加路径压缩
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ初级-简单搜索 解题报告+AC代码