题目描述
简述题意:
(1)存在A吃B,B吃C,C吃A的闭环;
(2)现有N个动物,编号从1~N,这些动物只属于A,B,C这三类中的其中一种;
(3)有人用两种说法对这 N 个动物所构成的食物链关系进行描述:
第一种说法是 1 X Y,表示 X 和 Y 是同类。
第二种说法是 2 X Y,表示 X 吃 Y。
(4)当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
- 当前的话与前面的某些真的话冲突,就是假话;
- 当前的话中 X 或 Y 比 N 大,就是假话;
- 当前的话表示 X 吃 X,就是假话。
问给定的 N 和 K 句话,输出假话的总数。
解题思路
(1)此处p[x]的理解:
①p[x]存储的是根节点; a.初始的时候,p[x]的根节点就是x;b.只要x在真话中被提及到,它就会和y并为一个集合;
②此处只要是真话,x和y都会归并到一个集合中
【重点,与之前并查集中p[x]的含义理解有所不同】
(表示在真话中被提及过,其并不表示x和y是同一个类,x和y是否为同一个类是通过距离d[x]-d[y]判断的)
(2)d[x]的理解【数组表示 和 数组存储 的含义不一样!!!】
①d[x]表示x到父节点p[x]的距离,d[p[x]]表示父节点到父父节点的距离;d[x]存储的是x到根节点的距离。
②通过递归的方式,我们可以计算出x到根节点的距离,就像通过递归的方式使x找到其所在的根节点
(3)关系表示【重点】
①通过求余循环的方式建模实现(此处一共有三种关系,捕食,被捕食,同类,所以是对3求余);
②余1:可以吃根节点 ; 余2:可以被根节点吃; 余3:与根节点是同类
(4)如何理解,详见下图图示,相关信息可以打印出来方便理解
(d[x] - d[y])%3, d[px] = d[y] - d[x]
(d[x]-d[y]-1)%3, d[px] = d[y]+1-d[x]
算法1
时间复杂度
C++ 代码
#include<iostream>
using namespace std;
const int N = 50010;
int n,k;
//p[i]表示第i个节点的父节点,存储的是第i个点的祖宗节点/根节点
//d[i]表示x到p[x]的距离,存储的当前节点到根节点的距离【通过递归得到距离值】;
【借助d[i]来判断节点之间的关系】
//对3求余循环,余1:可以吃到根节点;余2:可以被根节点吃;余3:与根节点是同类
int p[N],d[N];
int find(int x)
{
if(p[x]!=x)
{
int t = find(p[x]); //先记录下x的根节点
d[x] += d[p[x]]; //第x节点到父节点的距离 加上 其父节点到父父节点的距离
p[x] = t; //更新到x的根节点
}
return p[x];
}
int main()
{
//input
scanf("%d%d",&n,&k);
//processing
int cnt = 0;
for(int i = 1;i<=n;i++) p[i] = i;
while(k--)
{
int D,x,y;
scanf("%d%d%d",&D,&x,&y);
//假话1
if(x>n || y>n) cnt++;
else
{
int px = find(x),py = find(y); //分别找到x和y的根节点
if(D == 1)
{
//(1)如果x和y在之前的话中被提及过(在这里只要被提及过,并且是真话,节点就会归并到一个集合中),距离差求余非0(即存在捕食关系),
//两句话如果同时成立表示该句话为假话,所以就cnt++
//以下视为真话的处理
//(2)如果x和y在之前没有被提及过并且距离差求余为0,则此话为真话(同类之间没有捕食关系)
//(3)如果x和y在之前没有被提及过,进行集合融合对p[]和d[]做处理
if(px == py && (d[x] - d[y])%3) cnt++;
else if(px != py)
{
p[px] = py;
d[px] = d[y] - d[x]; //此处(d[y]-d[x])的取值范围为[-2,2]
}
}
else
{
//当D=2时,x吃y所以(d[x]-d[y])%3 = 1
//如果x和y在之前的话中被提及过(即x和y存在关系),并且不存在x吃y的捕食关系,则此话为假话
if(px == py && (d[x]-d[y]-1)%3) cnt++;
else if(px != py)
{
p[px] = py;
d[px] = d[y]+1-d[x]; //+1这里表示x吃y,同时也起到初始化的作用
//printf("x = %d,px = %d,y = %d,py = %d\n",x,px,y,py);
// printf("d[%d]=%d ,d[%d]=%d,d[%d]=%d\n",x,d[x],px,d[px],y,d[y]);
}
}
}
}
printf("%d\n",cnt);
return 0;
}