Paritygame(poj1733)题解及思路分析

有以个串&＃xff0c;每次给出【i&＃xff0c;j】之间的1的个数&＃xff0c;
有m次询问&＃xff0c;判断当前询问是否和之前的询问相冲突&＃xff0c;冲突就break。

思路&＃xff1a;

由于本题的区间范围有点大&＃xff0c;所以要先离线。

1. 本每次输入的左右区间依次存入一个 数组 中。
2. 之后把重复的出现去掉unique&＃xff08;为了后面的二分查找&＃xff09;
3. 之后就是带权并查集的基本操作&＃xff0c;
4. 本题的dis【】稍微改变一下&＃xff0c;就可以了&＃xff08;本题even为0&＃xff0c;odd为1&＃xff09;
5. 所以find中的dis

dis[x]^&＃61;dis[f[x]];

6. merge中的

f[A]&＃61;B;dis[A]&＃61;dis[x]^dis[y]^p[i].op;

反思

1. 离线的学习。

For(i,1,q){int l,r;char s[10];scanf("%d%d%s", &l, &r, s);p[i].l&＃61;a[&＃43;&＃43;cnt]&＃61;l-1;p[i].r&＃61;a[&＃43;&＃43;cnt]&＃61;r;p[i].op&＃61;(s[0]&＃61;&＃61;&＃39;o&＃39;)?1:0;}

离线后之后直接访问第几个即可。
2. 异或运算的学习。
本题的操作和异或运算给很像
本题的路径并不是dis[A]&＃61;dis【b】- dis【a】&＃43; x&＃xff1b;

因为&＃xff1a;

odd&＃43;odd&＃61;even&＃xff1b;
odd-odd&＃61;even&＃xff1b;
even&＃43;even&＃61;even&＃xff1b;
even-even&＃61;even&＃xff1b;
odd&＃43;even&＃61;odd&＃xff1b;
odd-even&＃61;odd&＃xff1b;
所以无关加减了&＃xff0c;直接异或走起

#include
#include
#include
#define For(i,x,y) for(register int i&＃61;(x); i<&＃61;(y); i&＃43;&＃43;)
using namespace std;
const int maxn&＃61;1e4&＃43;10;
struct point
{int l,r;int op;
}p[maxn];
int f[maxn<<1], dis[maxn<<1], a[maxn<<1],cnt,n,q,x;
int find(int x)
{if(x&＃61;&＃61;f[x])return x;int root&＃61;find(f[x]);dis[x]^&＃61;dis[f[x]];return f[x]&＃61;root;
}
int main()
{scanf("%d", &n);scanf("%d", &q);For(i,1,q){int l,r;char s[10];scanf("%d%d%s", &l, &r, s);p[i].l&＃61;a[&＃43;&＃43;cnt]&＃61;l-1;p[i].r&＃61;a[&＃43;&＃43;cnt]&＃61;r;p[i].op&＃61;(s[0]&＃61;&＃61;&＃39;o&＃39;)?1:0;}For(i,1,2*q)f[i]&＃61;i;// For(i,1,n)cout<int ans&＃61;0;sort(a&＃43;1,a&＃43;1&＃43;cnt);n&＃61;unique(a&＃43;1,a&＃43;1&＃43;cnt)-(a&＃43;1);//cout<For(i,1,q){ans&＃61;i;//cout<int x&＃61;lower_bound(a&＃43;1,a&＃43;1&＃43;n,p[i].l)-a-1;int y&＃61;lower_bound(a&＃43;1,a&＃43;1&＃43;n,p[i].r)-a-1;// cout<int A&＃61;find(x);int B&＃61;find(y);if(A&＃61;&＃61;B){if(dis[x]^dis[y]!&＃61;p[i].op){ans--;break;}}else{f[A]&＃61;B;dis[A]&＃61;dis[x]^dis[y]^p[i].op;}}cout<<ans<<endl;return 0;
}