• luogu P2024 食物链


    P2024 食物链


    题目描述

    动物王国中有三类动物 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 句话,输出假话的总数。


    输入输出格式

    输入格式:

     从 eat.in 中输入数据

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

    第二行开始每行一句话(按照题目要求,见样例)

    输出格式:

     输出到 eat.out 中

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


    输入输出样例

    输入样例#1:
    100 7
    1 101 1
    2 1 2
    2 2 3
    2 3 3
    1 1 3
    2 3 1
    1 5 5
    
    输出样例#1:
    3
    

    说明

    1 ≤ N ≤ 5 ∗ 10^4

    1 ≤ K ≤ 10^5


     玄学的加权并查集qwq

    在%3的意义下,AB两点之间距离为0表示同类,1表示A吃B,2表示A被B吃

    实现不是很好弄……细节看代码qwq

    (关于处理距离的地方我也没看太懂就是了……qwq)

    (好像建个三倍集也能做?感觉好麻烦啊不想写)

    #include<iostream>
    #include<cstdio>
    using namespace std;
    const int N=5*1e5+9;
    int n,k,ans,fa[N],dis[N];
    int found(int x)
    {
        if(x==fa[x])return x;
        int f=found(fa[x]);
        dis[x]=(dis[x]+dis[fa[x]])%3;
        return fa[x]=f;
    }
    int main()
    {
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;++i)fa[i]=i;
        while(k--)
        {
            int t,x,y;
            scanf("%d%d%d",&t,&x,&y);
            if(x>n||y>n){++ans;continue;}
            if(t==1)//同类 
            {
                int p=found(x),q=found(y);
                if(p==q){    
                    if(dis[x]!=dis[y])++ans; 
                }
                else{
                    dis[fa[x]]=(dis[y]-dis[x]+3)%3;
                    fa[fa[x]]=fa[y];
                }
            }
            else//
            {
                if(x==y){++ans;continue;}
                int p=found(x),q=found(y);
                if(p==q){    
                    if(dis[x]!=(dis[y]+1)%3)++ans; 
                }
                else{
                    dis[fa[x]]=(dis[y]-dis[x]+4)%3;
                    fa[fa[x]]=fa[y];
                }
            }
            
        }
        cout<<ans;
        return 0;
    }
    食物链

    by:wypx


  • 相关阅读:
    【LeetCode】147. Insertion Sort List
    【LeetCode】64. Minimum Path Sum
    【LeetCode】7. Reverse Integer
    【LeetCode】107. Binary Tree Level Order Traversal II (2 solutions)
    【LeetCode】114. Distinct Subsequences
    【LeetCode】35. Search Insert Position (2 solutions)
    为什么easyui的datagrid里getSelections还有getChecked只能获取一行值呢?
    IE兼容模式下 SCRIPT1028: 缺少标识符、字符串或数字
    修改easyui的easyloader的默认css目录路径
    如何在Visual Studio的查找功能中使用正则表达式?
  • 原文地址:https://www.cnblogs.com/ck666/p/7630088.html
一二三 - 开发者的网上家园