算法竞赛进阶指南:食物链

2021/12/9 1:17:03

本文主要是介绍算法竞赛进阶指南:食物链,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

原题链接

动物王国中有三类动物 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

 思路:并查集维护根节点距离

我们先不考虑每两个动物x,y是什么关系,我们根据题目来判断;

如果x,y的取值在1~n,可以根据D的值判断是真话还是假话,或者判断将其变成真话;

假设x,y在一个集合 对于集合元素有h->a->b->c,h吃a,a吃b,b吃c,h到根节点距离为3,a到根节点距离为2,b到根节点距离为1;

可以推断出h和c是同类,他们之间的的距离为3%3=0,b被c吃,其到c的距离为2%3=2,a吃c,两者之间距离为1%3=1;

所以可以得出结论:如果x,y在一个集合 可以通过x和y到根节点的距离之差判断他们之间的关系,从而判断是真话还是假话;

如果距离之差%3=0,说明是同类,如果%3=1(x>y),或者%3=-2(x<y),说明x吃y;

如果不在同一集合,可以通过合并集合,调整其跟节点到新集合根节点的距离可以使其变成真话;

如果要是x,y不在同一集合,要使x,y为同类,则合并后(d[x]+d[p[x]]-d[y])%3=0,所以将其d[p[x]]变成d[y]-d[x]就行;

使x吃y也是同理:(d[p[x]]+d[x]-d[y]-1)%3=0,所以d[p[x]]=1+d[y]-d[x];

d[p[x]]+d[x]-d[y]-1)%3=0与 x,y之差%3=1或者-2等价;

#include<iostream>
using namespace std;
const int N=5e5+10;
int p[N],d[N];//p数组存储x父节点,d存储x到根节点距离
int find(int x){
    if(p[x]!=x){
        int t=find(p[x]);//需要先存储根节点,不将父节点更新为根节点
        //将父节点到根节点全部路径压缩指向根节点,同时更新父节点到根节点的距离
        d[x]+=d[p[x]];//点x到根节点距离=x到父节点距离+父节点到根节点距离
        p[x]=t;//更新父节点为根节点
    }
    return p[x];//返回根节点
}
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;++i) p[i]=i;
    int res=0;//假话个数
    while(k--){
        int D,x,y;
        cin>>D>>x>>y;
         if(x>n||y>n) {
             res++;//超出动物编号范围,为假
            continue;
         }
           int px=find(x),py=find(y);//x,y的父节点
         if(D==1){
            
           if(px==py&&(d[x]-d[y])%3!=0) res++;//判断是否为同一集合且同类
           
           else if(px!=py){//不为同一集合可变为同类
               p[px]=py;
               d[px]=d[y]-d[x];
           }

        }else{
            
             if(px==py&&((d[x]-d[y])%3!=1&&(d[x]-d[y])%3!=-2)) res++; 
             //x吃y的两种情况,距离之差%3=-1或者2
            
            else if(px!=py){
                p[px]=py;
                d[px]=1+d[y]-d[x];
            }
        }
    }
    cout<<res;
    return 0;
}



这篇关于算法竞赛进阶指南:食物链的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程