题目描述
动物王国中有三类动物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句话有的是真的,有的是假的。
当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N和K句话,输出假话的总数。
输入格式
第一行是两个整数N和K,以一个空格分隔。
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
若D=1,则表示X和Y是同类。
若D=2,则表示X吃Y。
输出格式
只有一个整数,表示假话的数目。
数据范围
1≤N≤50000,
0≤K≤100000
样例
输入样例:
100 7
1 101 1
2 1 2
2 2 3
2 3 3
1 1 3
2 3 1
1 5 5
输出样例:
3
有几个重点:
1.
如果x到根节点的距离mod 3 == 1
,说明可以吃根节点;
如果x到根节点的距离mod 3 == 2
,说明可以被根节点吃;
如果x到根节点的距离mod 3 == 0
,说明该点与根节点同类。可以画一个三角形理解一下;
距离表示:假设x吃y,y到x的距离就为1
2.
如果x y的关系是同类
同类意味着d[x]+d[px]-d[y])%3 == 0
,故有d[px] = d[y] - d[x]
;
如果x y的关系是x吃y
x吃y意味着d[x]-d[y]-1)%3 == 0
,故有d[px] = d[y] + 1 - d[x]
;
3.
假设x吃y,y就是第0
代,吃y的x就是第1
代,吃第1
的就是第2
代假设是z吃第2
代的就是第3
代
假设第3
代为k以次类推,该距离就表示第几代,比如距离为5
就是第五代,三个一循环,所以推出0与3位
同类,得到:”1.”中的结论!
算法1
(并查集)
C++ 代码
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 100000;
int n,m;
int fa[N << 1],d[N << 1]; //fa-->根节点,d-->到根节点的的距离
int find (int x) //并查集维护关系
{
if(fa[x] != x)
{
int u = find(fa[x]); //压缩到树根,防止再更新时丢失!
d[x] += d[fa[x]]; //更新到根节点的距离
fa[x] = u; //父节点也压缩到树根
}
return fa[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) fa[i]=i; //重载关系,将每个点的父节点设为自己
int res = 0; //记录谎话的数量
while(m--) //查询操作
{
int t,x,y;
scanf("%d%d%d",&t,&x,&y);
//t--> 说法种类
//x--> 吃的物
//y--> 被吃的物
int dx = find(x),dy = find(y); //先找到父节点
if(x > n || y > n) res++; //如果不满住条件二,res++
else if(t==1) // 如果为同类
{
if(dx == dy && (d[y] - d[x]) % 3) res++; //且父节点相同,并且y到根节点的距离 比 x到根节点的距离多三,则为谎话
else if(dx != dy) //如果不在同一集合内,并到一起,更新距离
{
fa[dx] = dy;
d[dx] = d[y] - d[x];
}
}
else //如果为吃被吃掉的关系
{
if(x == y || dx == dy && (d[x] - d[y] - 1) % 3) res++; //如果x == y 不满足条件三,谎话;
//如果x到根节点的距离比y到根节点的距离再减一 mod 3为真 --->>谎话
else if(dx != dy)//如果不在同一集合内,并到一起,更新距离
{
fa[dx] = dy;
d[dx] = d[y] + 1 - d[x];
}
}
}
printf("%d",res); //最后输出谎话的数量!
return 0;
}
能问一下,如果是负数怎么办啊
以下K行每行是三个正整数 D,X,Y,两数之间用一个空格隔开,其中D表示说法的种类。
### 因为都是正整数,所以不需要考虑负数的情况
我意思是,d[dx] = d[y] - d[x];像这个操作,假如d[x]是大于d[y]的呢,那么d[dx]不就是负数了嘛
我意思是,d[dx] = d[y] - d[x];像这个操作,假如d[x]是大于d[y]的呢,那么d[dx]不就是负数了嘛
写得好详细呀 nice