©2020-2024 ioDraw All rights reserved
<>奇偶游戏【离散化+并查集】
POJ1733、ACwing239
#include<bits/stdc++.h> using namespace std; #define int long long const int N
= 10000; struct query{ //记录需要查询的m个序列 int l,r,ans; } v[5005]; int father[N + 5],
dis[N + 5],a[N + 5],b[N + 5]; //分别记录祖先、和根节点的奇偶关系、离散化前、离散化后 int n,m,k,kk; int
find_f(int x){ //找到祖先结点并且更新dis和father数组 if(father[x] == x) return x; int root =
find_f(father[x]); //先遍历 dis[x] ^= dis[father[x]]; //等待父亲结点更新之后再更新该结点信息 return
father[x] = root; //缩短路径 } void discrete(){ //离散化后得到数组b sort(a + 1,a + 1 + k); b
[++kk] = a[1]; for(int i = 2;i <= k;++i) if(a[i] != a[i - 1]) b[++kk] = a[i]; }
int find_w(int x){ //找到离散化后代替x的值 return lower_bound(b + 1,b + kk + 1,x) - b; }
void solve(){ for(int i = 1;i <= N;++i) //初始化 father[i] = i; cin>>n>>m; int l,r,
p,q; string s; for(int i = 1;i <= m;++i){ //输入操作并且得到离散化前的数组a cin>>v[i].l>>v[i].r
>>s; v[i].ans = s[0] == 'e' ? 0 : 1; //有偶数个1的话说明前半段和整段的奇偶性相同，用0表示 a[++k] = v[i].
l;a[++k] = v[i].r; } discrete(); //离散化得到数组b for(int i = 1;i <= m;++i){ l =
find_w(v[i].l) - 1;r = find_w(v[i].r); //得到前半段和整段的下标 p = find_f(l);q = find_f(r)
; //分别找出祖宗结点 if(p == q){ //在同一个集合 if(dis[l] ^ dis[r] != v[i].ans){
//用两个点和祖先结点的奇偶性去异或得到两个数的奇偶性 //如果不和答案相同的话，就说明说谎了 cout<<i - 1; return; } } else{
//如果没有在同一个集合，那么就合并并且建立关系 father[p] = q; dis[p] = dis[l] ^ dis[r] ^ v[i].ans;
//l到r的奇偶性是dis[l] ^ dis[r] ^ pq之间的奇偶性 //即:v[i].ans = dis[l] ^ dis[r] ^ pq之间的奇偶性
//得到：pq之间的奇偶性 = v[i].ans ^ dis[l] ^ dis[r] } } cout<<m; } signed main(){ ios::
sync_with_stdio(false),cin.tie(0),cout.tie(0); // int tt; // cin>>tt; //
while(tt--) solve(); return 0; }