并查集6

并查集6

并查集之

不一定只有fa,还可能有多种情况(扩展域)

什么意思

就是传递关系不止一种时,可以像dp增加状态一样增加一些关系

Parity game

题意：有一个长度已知的01串，给出[l,r]这个区间中的1是奇数个还是偶数个，给出一系列语句问前几个是正确的

样例输入

1051 2 even3 4 odd5 6 even1 6 even7 10 odd

样例输出

3

分析

代码

#include#define M 5005*2using namespace std;struct Node{int l,r,op;}quary[M];int a[M*2],fa[M*2],n,m,tot;int read(){ int cnt=0;char ch=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar(); return cnt;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}int main(){ n=read(),m=read(); for(int i=1;i<=m;i++){ char ch[5]; quary[i].l=read(),quary[i].r=read(); scanf("%s",ch),quary[i].op=(ch[0]=='e')?0:1; a[++tot]=quary[i].l-1,a[++tot]=quary[i].r; } sort(a+1,a+tot+1); n=unique(a+1,a+tot+1)-a-1; for(int i=0;i<=2*n;i++) fa[i]=i; for(int i=1;i<=m;i++){ int x=lower_bound(a+1,a+n+1,quary[i].l-1)-a; int y=lower_bound(a+1,a+n+1,quary[i].r)-a; int x_odd=x,x_even=x+n; int y_odd=y,y_even=y+n; if(quary[i].op==0){ if(find(x_odd)==find(y_even)){cout<

食物链

题目描述

动物王国中有三类动物 A,B,C，这三类动物的食物链构成了有趣的环形。A 吃 B，B

吃 C，C 吃 A。

现有 N 个动物，以 1 － N 编号。每个动物都是 A,B,C 中的一种，但是我们并不知道

它到底是哪一种。

有人用两种说法对这 N 个动物所构成的食物链关系进行描述：

第一种说法是“1 X Y”，表示 X 和 Y 是同类。

第二种说法是“2 X Y”，表示 X 吃 Y 。

此人对 N 个动物，用上述两种说法，一句接一句地说出 K 句话，这 K 句话有的是真

的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。

• 当前的话与前面的某些真的话冲突，就是假话

• 当前的话中 X 或 Y 比 N 大，就是假话

• 当前的话表示 X 吃 X，就是假话

你的任务是根据给定的 N 和 K 句话，输出假话的总数。

输入输出格式

输入格式：

第一行两个整数，N，K，表示有 N 个动物，K 句话。

第二行开始每行一句话

输出格式：

一行，一个整数，表示假话的总数。

输入输出样例

输入样例

100 71 101 12 1 22 2 32 3 31 1 32 3 11 5 5

输出样例

3

说明

1 ≤ N ≤ 5 ∗ 10^4

1 ≤ K ≤ 10^5

分析

(算法竞赛进阶指南)

代码

#include#define N 50005using namespace std;int fa[N*3],n,k,ans;int read(){ int cnt=0;char ch=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar(); return cnt;}int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}void merge(int x,int y){ x=find(x),y=find(y); if(x!=y) fa[x]=y;}int main(){ //freopen("1.in","r",stdin); n=read(),k=read(); for(int i=1;i<=n*3;i++) fa[i]=i; while(k--){ int op=read(),x=read(),y=read(); if(x>n||y>n){ans++;continue;} int x_self=x,x_eat=x+n,x_enemy=x+2*n; int y_self=y,y_eat=y+n,y_enemy=y+2*n; if(op==1){ if(find(x_eat)==find(y_self)||find(x_self)==find(y_eat)){ ans++;continue; } merge(x_self,y_self); merge(x_eat,y_eat); merge(x_enemy,y_enemy); } else{ if(find(x_self)==find(y_self)||find(x_self)==find(y_eat)){ ans++;continue; } merge(x_eat,y_self); merge(x_self,y_enemy); merge(x_enemy,y_eat); } } cout<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。