食物链3_食物链条数计算公式

食物链3_食物链条数计算公式动物王国中有三类动物 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 句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

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

输入格式
第一行是两个整数 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
#include<bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10;
int f[N],d[N];
int Find(int x){ 
   
    if(x != f[x]){ 
   
        
        int t = Find(f[x]);
        d[x] = (d[x] + d[f[x]]);
    
        f[x] = t;
    }
    return f[x];
}
int main(){ 
   
    int n,k;
    cin>>n>>k;
    for(int i = 0;i <= n;i ++)f[i] = i;
    memset(d,0,sizeof d);
    int res = 0;
    int t,x,y;
    for(int i = 0;i < k;i ++){ 
   
        cin>>t>>x>>y;
        if(x > n || y > n)res ++;
        else{ 
   
            int a = Find(x),b = Find(y);
            if(t == 1){ 
   
                if(a != b){ 
   
                    f[a] = b;
                    d[a] = (d[y] - d[x]);
                }else{ 
   
                    if(abs(d[y] - d[x]) % 3)res ++;
                }
            }
            else { 
   
                if(a != b){ 
   
                    f[a] = b;
                    d[a] = (1 + d[y] - d[x]);
                }else { 
   
                    if(abs(d[x] - d[y] - 1) % 3)res ++;
                }
            }
        }
    }
    cout<<res<<endl;
    
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/168607.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Android listView用法详解

    Android listView用法详解1.前言在android开发中ListView是比较常用的组件,它以列表的形式展示具体内容,并且能够根据数据的长度自适应显示。列表的显示需要三个元素:1.ListVeiw:用来展示列表的View。2.适配器:用来把数据映射到ListView上的中介。3.数据:被映射的字符串,图片,或者基本组件。2.listView的使用listVi

  • idea激活服务器 3月最新注册码

    idea激活服务器 3月最新注册码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • SpringBoot2-[SpringBoot优缺点、微服务理解、版本仲裁]

    SpringBoot2-[SpringBoot优缺点、微服务理解、版本仲裁]??‍?博主介绍:大家好,我是芝士味的椒盐,一名在校大学生,热爱分享知识,很高兴在这里认识大家??擅长领域:Java、大数据、运维、电子??如果本文章各位小伙伴们有帮助的话,?关注+??点赞+?评论+?收藏,相应的有空了我也会回访,互助!!!?另本人水平有限,旨在创作简单易懂的文章,在文章描述时如有错,恳请各位大佬指正,在此感谢!!!文章目录Spring.ioSpring5重大升级SpringBoot优点SpringBoot缺点微服务SpringBoot官方文档Maven设置SpringBo..

  • 我的 Vue.js 学习日记 (四) – v-bind:class / style 用法

    我的 Vue.js 学习日记 (四) – v-bind:class / style 用法

  • QQ图片文件夹说明及清理

    QQ图片文件夹说明及清理C2C(个人与好友之间的图片传输,清空与否依照个人意愿)Group(群组之间的图片传输,很乱建议全部清空)MarktingMsgCachePic(Markting+Msg+Cache+Pic意思是消息图片缓冲集合,就是你聊天时候发送的一些图片保存的地方,无用,可删除)MsgWander(漫游信息,浏览信息,可删)SharePic(分享图片,可删)*注意不要删掉文件夹(比如SharePic)要打开选

  • python读取modis数据

    python读取modis数据本期记录只上干活,废话不多说,主要是后面与HEG配合使用,实现一系列研究与反演操作。python环境:Python3.5.2+Pycharm模块包:pyhdf安装方法(命令行输入):pipinstallpyhdf一、获取hdf数据集:frompyhdf.SDimportSDHDF_FILR_URL=”E:\Persona_project\Py-Pro…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号