其实很不好意思的说，这道题我的方法肯定不大好，非常的慢，需400多ms
但是再怎么说也是好不容易写出来的
这道题的转换方法很巧妙
要不是上网搜出来的，我肯定不敢相信这是用并查集做
主要是把区间化为单个数的想法来做
这一点的处理我是用cube stacking同样的想法来做的
还有一点，离散化，这是基本上资料对这题的所要求的一点，这一点我不大懂
这一题确实有个很大的特点，10亿的数据，只有5000个操作
离散化，还是要慢慢体会的
这是我的代码，很长，很繁琐
而且思路不是很清楚
因为边改边想着做出来的
1
#include<iostream>
2#include<string>
3#include<map>
4using namespace std;
5typedef struct{
6 int parent;
7 //int rank;
8 int on;//决定从根到该结点的1的个数是奇还是偶，奇则为1，偶为0
9}NODE;
10typedef map<int,NODE> Mate;
11typedef Mate::value_type value_type;
12Mate Map;
13int find_set(int x)
14{
15 int t=Map[x].parent;
16 if(Map[x].parent!=x){
17 Map[x].parent=find_set(Map[x].parent);
18 Map[x].on=(Map[x].on+Map[t].on)%2;
19 }
20 return Map[x].parent;
21}
22void union_set(int x,int y,int c)
23{
24 Map[y].parent=x;
25 Map[y].on=c;
26}
27int main()
28{
29 NODE *t;
30 Mate::iterator xt,yt;
31 int i,n,qus,x,y,ct,xp,yp,k;//xp表示x-1的祖先,yp表示y的祖先
32 string condi;
33 scanf("%d%d",&n,&qus);
34 for(i=1;i<=qus;i++){
35 cin>>x>>y>>condi;
36 if(condi=="even")ct=0;
37 else if(condi=="odd")ct=1;
38 xt=Map.find(x-1);
39 yt=Map.find(y);
40 if(xt!=Map.end()&&yt!=Map.end()){//x-1,y都存在于Map中，但是也有不同的情况，可能二者在同一个集合中
41 //可能二者也不在同一个集合中，如果在的话就好办了，直接验证
42 //如果不则要合并
43 xp=find_set(x-1);//find 一次 就更新了x-1到根的路径上的on值
44 yp=find_set(y);//同上
45 if(xp==yp){
46 if((Map[y].on+Map[x-1].on)%2!=ct){
47 printf("%d\n",i-1);
48 break;}}
49 k=(Map[x-1].on+ct+Map[y].on)%2;
50 if(xp<yp)union_set(xp,yp,k);
51 else union_set(yp,xp,k);
52 }
53 else if(xt!=Map.end()&&yt==Map.end()){//x-1在Map中，而y不在
54 t=(NODE*)malloc(sizeof(NODE));
55 Map.insert(value_type(y,*t));
56 union_set(x-1,y,ct);
57 }
58 else if(xt==Map.end()&&yt!=Map.end()){//x-1不在Map中，而y在
59 yp=find_set(y);
60 t=(NODE*)malloc(sizeof(NODE));
61 Map.insert(value_type(x-1,*t));
62 union_set(yp,x-1,(ct+Map[y].on)%2);
63 }
64 else if(xt==Map.end()&&yt==Map.end()){//x-1和y都不在Map中
65 t=(NODE*)malloc(sizeof(NODE));
66 t->on=0;
67 t->parent=x-1;
68 Map.insert(value_type(x-1,*t));
69 t=(NODE*)malloc(sizeof(NODE));
70 Map.insert(value_type(y,*t));
71 union_set(x-1,y,ct);
72 }
73 }
74 if(i>qus)printf("%d\n",i-1);
75 return 0;
76}
这是另外个代码，还没看懂
1#include <stdio.h>
2#include <map>
3using namespace std;
4
5#define N 5001
6int x[N], y[N], parent[N+N];
7bool odd[N], parity[N+N];
8
9void swap( int &a, int &b) {
10 int tmp=a; a=b; b=tmp;
11}
12
13map<int,int> mmp;
14
15void unionab( int a, int b, bool e) {
16 parent[a]=b;
17 parity[a]=e;
18}
19
20int findx( int x, bool &e) {
21 int r=x;
22 bool res=parity[x];
23 while( parent[r]!=r) {
24 r=parent[r];
25 res ^=parity[r];
26 }
27 e=res;
28 return r;
29}
30
31bool check( int id) {
32 int a=x[id], b=y[id];
33 bool e=odd[id], ea, eb;
34 int ra=findx(a, ea), rb=findx(b, eb);
35 if( ra==rb) {
36 if( ea^eb!=e)
37 return false;
38 }
39 else
40 unionab( ra, rb, ea^eb^e);
41 return true;
42}
43
44int main() {
45 int n, i, tmp, a,b, idx;
46 char s[7];
47 scanf("%d%d", &tmp, &n);
48 for( i=1,idx=1; i<=n; i++) {
49 scanf("%d%d%s", &a,&b,s);
50 if(a>b) swap(a,b);
51 --a;
52 if(a<0) {
53 printf("1\n");
54 return 0;
55 }
56 if( !mmp.count(a)) mmp[a]=idx++;
57 if( !mmp.count(b)) mmp[b]=idx++;
58 x[i]=mmp[a]; y[i]=mmp[b];
59 odd[i]=(s[0]=='o');
60 }
61 for( i=1; i<=idx; i++) {
62 parent[i]=i; parity[i]=false;
63 }
64 for( i=1; i<=n; i++) {
65 if( !check(i) )
66 break;
67 }
68 printf("%d\n", i-1);
69 return 0;
70}
71
http://acm.pku.edu.cn/JudgeOnline/problem?id=1733
posted on 2008-01-27 22:26
zoyi 阅读(254)
评论(0) 编辑 收藏 引用