正題

POJ題目鏈接:http://poj.org/problem?id=1733
jzoj題目鏈接:https://jzoj.net/senior/#main/show/1779

---

題目大意

長度為ll的01串，nn個答案，表示一段區間內有偶數或奇數個1，求最多前多少個答案是對的。

---

解題思路

我們可以先離散化一下，然后我們再用并查集，然后兩個點直接的并查集和權值表示這兩個點之間1的奇偶。然后每次合并和壓縮路徑的時候就用異或操作。

---

code

#include<cstdio> #include<algorithm> using namespace std; struct node{int l,r,ans; }q[5010]; int l,n,f[5010],d[5010],a[5010*2],tot; char c[5]; int find(int x){if(x==f[x]) return x;int fa=find(f[x]);d[x]^=d[f[x]];return f[x]=fa; }//壓縮路徑 int main() {scanf("%d%d",&l,&n);for(int i=1;i<=n;i++){scanf("%d %d %s",&q[i].l,&q[i].r,&c);if(c[0]=='e') q[i].ans=0;else q[i].ans=1;a[++tot]=q[i].l-1;a[++tot]=q[i].r;}//以上是輸入sort(a+1,a+tot+1);l=unique(a+1,a+tot+1)-a-1;//以上是離散for(int i=1;i<=l;i++) f[i]=i;//初始化并查集for(int i=1;i<=n;i++){int x=lower_bound(a+1,a+1+l,q[i].l-1)-a;int y=lower_bound(a+1,a+1+l,q[i].r)-a;//找到位置int fa=find(x),fb=find(y);if(fa==fb){if(d[x]^d[y]!=q[i].ans){printf("%d",i-1);return 0;}//不符合}elsef[fa]=fb,d[fa]=d[x]^d[y]^q[i].ans;//連接}printf("%d",n); }

總結

以上是生活随笔為你收集整理的POJ1733,jzoj1779-Parity game(奇偶游戏)【带权并查集,离散化】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。