AcWing 240. 食物链

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 240. 食物链原题链接中等

作者：

秦淮岸灯火阑珊 , 2019-02-12 20:59:53 , 所有人可见 , 阅读 16528

148

66

原题链接

感谢@远山淡影大佬指出问题

题目描述

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

样例

并查集(拓展域)

这道题目我们主要是要开三个拓展的域,也就是天敌域,同类域,以及捕食域.

如果x,y是同类,但是x的捕食域有y,那么错误
如果x,y是同类,但是x的天敌域有y,那么错误
如果x是y的天敌,但是x的同类域中有y,那么错误
如果x是y的天敌,但是x的天敌域中有y,那么错误

C++ 代码

//这里我们将三个域,分别转化为了n,n+n,n+n+n.因为读入方面特别烦.
#include <bits/stdc++.h>
using namespace std;
int fa[200000];
int n,m,k,x,y,ans;
int get(int x)
{
    if(x==fa[x]) 
        return x;
    return fa[x]=get(fa[x]);
}
void merge(int x,int y)
{
    fa[get(x)]=get(y);
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=3*n;i++) 
        fa[i]=i;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&k,&x,&y);
        if(x>n || y>n) 
            ans++;
        else if(k==1)
        {
            if(get(x)==get(y+n) || get(x)==get(y+n+n)) //如果x,y是同类,但是x是y的捕食中的动物,或者x是y天敌中的动物,那么错误.
                ans++;
            else
            {
                merge(x,y);
                merge(x+n,y+n);
                merge(x+n+n,y+n+n);
            }
        }
        else
        {
            if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x
                ans++;//都是假话
            else
            {
                merge(x,y+n+n);//y的捕食域加入x
                merge(x+n,y);//x的天敌域加入y
                merge(x+n+n,y+n);//x的捕食域是y的同类域.
            }
        }
    }
    cout<<ans<<endl;
}
//x是同类域.
//x+n是捕食域
//x+n+n是天敌域

72 评论

醒了不起的盖兹比 2023-02-24 22:29

领域展开~无量假话

云雾 2022-02-10 23:38

if(x==y || get(x)==get(y) || get(x)==get(y+n)) //x就是y,或者他们是同类,再或者是y的同类中有x

中标记是否有误？不应该写成x就是y,或者他们是同类,再或者是y的捕食域中有x

Seeker. 2022-03-10 22:02

俺也感觉这里好像有点小问题

Grace25 2021-10-10 15:29

merge(x,y+n+n);//y的捕食域加入x -> y的天敌域加入x
merge(x+n,y);//x的天敌域加入y -> x的捕食域加入y
merge(x+n+n,y+n);//x的捕食域是y的同类域. -> x的天敌域可以捕食y的捕食域

Grace25 2021-10-10 15:29

是不是得这样修改一下

云雾 2022-02-10 23:29 回复了 Grace25 的评论

我觉得是这样，可能打错了。

Avril 2021-01-09 07:17

大佬思路很清晰学到了不少
但是请问这三句话的注释是不是有问题呢？

merge(x,y+n+n);     // y的捕食域加入x
merge(x+n,y);       // x的天敌域加入y
merge(x+n+n,y+n);   // x的捕食域是y的同类域.

我认为应该改为

merge(x,y+n+n);     // y的天敌域加入x
merge(x+n,y);       // x捕食域加入y
merge(x+n+n,y+n);   // x的天敌域为y的捕食域

李哥 2021-03-17 14:43

#include <iostream>

using namespace std;

int n, k;
int p[150010]; 

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int main()
{
    cin >> n >> k;
    // x是同类域. x+n是捕食域. x+n+n是天敌域
    for (int i = 1; i <= 3 * 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; }
        if (d == 1) // xy是同类.即xy是同类域
        {
            // 则x是y的捕食域||x是y的天敌域 假
            if (find(x) == find(y + n) || find(x) == find(y + n + n)) { res ++ ; continue; }
            // 更新xy三个域的关系
            p[find(x)] = find(y); // x的同类域=y的同类域
            p[find(x + n)] = find(y + n); // x的捕食域=y的捕食域
            p[find(x + n + n)] = find(y + n + n); // x的天敌域=y的天敌域
        }
        else // x吃y.即x是y的天敌
        {
            // 则x是y的同类域||x是y的捕食域 假
            if (find(x) == find(y) || find(x) == find(y + n)) { res ++ ; continue; }
            // 更新xy三个域的关系
            p[find(x)] = find(y + n + n); // x的同类域=y的天敌域
            p[find(x + n)] = find(y); // x的捕食域=y的同类域
            p[find(x + n + n)] = find(y + n); // x的天敌域=y的捕食域
        }
    }

    cout << res << endl;
    return 0;
}

chaosliang 2021-04-06 15:37

帮！

天才小笼包 2022-05-30 12:47 回复了李哥的评论

李哥的解释是对的.

krio 2023-01-28 15:52 回复了李哥的评论

非常清晰

今日臭明日香 6个月前

ORZ ORZ

自由_7 2023-06-08 22:43

%%%%%%%%%

Keven11 2023-01-14 19:57

nb，缪

lyxleo 2022-11-01 21:22

大师我悟了

ForeverStars 2022-07-21 21:43

%%%%%%%%%’

ZheyuHarry 2022-05-20 19:46

好聪明的想法，耳目一新！

图灵机 2022-05-19 00:23

%%%%%

Van_sama 2022-04-16 03:20

妙啊啊啊啊啊啊

撒野_9 2022-03-16 19:59

给定一句话，如果x，y动物不属于同一集合则，那么这句话一定为真吗？为什么？

xiuzhiyuan 2022-03-25 14:08

一定真。因为这道题对真话的判断就是如果无法根据话本身或前面的话判定为假，就是真话

撒野_9 2022-03-25 16:03 回复了 xiuzhiyuan 的评论

为什么不能根据前面的话判定为假？

xiuzhiyuan 2022-03-26 13:15 回复了撒野_9 的评论

具体来说如果x和y的本身、天敌域和捕食域全都没有交集，就说明它们前面没有过任何有关的说法。
所以根据题目的意思，是真的。
光是本身不属于同一集合只能说明没有被说过是同类。其实并不能说明什么。
所以要看你对“x,y动物不属于同一集合”到底怎么理解。

撒野_9 2022-03-26 16:47 回复了 xiuzhiyuan 的评论

谢谢你，我再想想

Zake 2022-01-30 18:12

‘’‘’
#include[HTML_REMOVED]

using namespace std;

const int N = 50010;

int n,m;

int p[N],d[N];

//找祖宗（并查集核心）
int find(int x){
//p[x]不是祖宗
if(p[x] != x){
int t = find(p[x]); //保存找到的祖宗，路径压缩（查）
d[x] +=d[p[x]]; //路径计算，爸爸的路径+爷爷（爸爸的爸爸）的路径
p[x] = t; //告诉孩子们祖宗是谁，路径压缩（合并）

}
return p[x];        //返回祖宗

}

int main(){

scanf("%d%d",&n,&m);//n：动物的总数，m：说话的总数
for(int i = 1; i<= n; i++)p[i] = i;  //初始化，每个都是祖宗(没有合并)

int res = 0;    //统计谎话
while(m--){
    int t, x, y;
    scanf("%d%d%d",&t,&x,&y);//t：1同类、2是x<-y（x吃y）；x：任意动物（数字）；y：任意动物（数字）

    if(x > n|| y > n) res ++;//谎话,规则2

    else{
        int px = find(x),py = find(y);  //找x和y的到祖宗的距离

        if(t == 1){//同类的情况下
             if( px == py && (d[x] - d[y])% 3)res ++;//px== py是同一个祖宗（集合），(d[x]-d[y])%3！=0，说明不是同类，不符合t =1，谎话

                 else if( px != py){    //不是同一个祖宗，把他们归宗
                     p[px] = py;    //将他们归为同一个祖宗（合并），px->py
                     d[px] = d[y] - d[x];   //并计算他们之间的距离，这里y- x 表示x到y的距离
             }
        }
        else{   //等于1的时候，吃与被吃
                if( px == py && (d[x] - d[y] - 1)%3)res ++;//x吃y ,(d[x]-d[y]-1)%3！=0说明，他们不是被吃关系，谎话

                else if(px != py){  //不是同一个祖宗，把他们归宗
                    p[px]  = py;     //将他们归为同一个祖宗（合并），px->py
                    d[px] = d[y] + 1 - d[x];//并计算他们之间的距离，这里y- x 表示x到y的距离,+1表示被吃的关系
            }
        }
    }
}
printf("%d\n",res); //输出谎话总数
return 0;

}

‘’‘
借楼