POJ1733Parity game
题意
区间长度为n,给定m个关系,然后三个输入l,r,s(字符) ,如果s="even"表示(l,r) 有偶数个1,如果s="odd"表示(l,r) 有奇数个1,求k使得1-k个条件都能满足要求,而k+1个条件不能满足.
思路
边带权并查集,记录与父亲节点之间有偶数个1还是奇数个1,当权值为1时时偶数个1,当权值为0时为偶数个1.
代码
#include<bits/stdc++.h>
using namespace std
;
const int maxn
=1e5+10;
struct node
{
int l
,r
,id
;
}a
[maxn
];
int t
[maxn
],fa
[maxn
],d
[maxn
];
int find(int x
){
if(x
==fa
[x
]) return x
;
int fx
=find(fa
[x
]);
d
[x
]^=d
[fa
[x
]];
return fa
[x
]=fx
;
}
int main(){
int n
,m
;scanf("%d%d",&n
,&m
);
int tot
=0;
for(int i
=1;i
<=m
;i
++){
char s
[5];
scanf("%d%d%s",&a
[i
].l
,&a
[i
].r
,s
);
a
[i
].id
=s
[0]=='e'?0:1;
t
[++tot
]=a
[i
].l
-1;
t
[++tot
]=a
[i
].r
;
}
sort(t
+1,t
+tot
+1);
tot
=unique(t
+1,t
+tot
+1)-t
-1;
for(int i
=1;i
<=tot
;i
++) fa
[i
]=i
;
int ans
=m
,flag
=0;
for(int i
=1;i
<=m
;i
++){
int x
=lower_bound(t
+1,t
+tot
+1,a
[i
].l
-1)-t
;
int y
=lower_bound(t
+1,t
+tot
+1,a
[i
].r
)-t
;
int fx
=find(x
),fy
=find(y
);
if(fx
==fy
) {
if((d
[x
]^d
[y
])!=a
[i
].id
){
ans
=i
-1;
flag
=1;
break;
}
}
else {
fa
[fx
]=fy
;
d
[fx
]=d
[x
]^d
[y
]^a
[i
].id
;
}
}
printf("%d\n",ans
);
}
