食物链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)


相关推荐

  • 什么是纠删码_脑疝的常见类型

    什么是纠删码_脑疝的常见类型你能给纠删码一个好的定义吗? EthanMiller:纠删码是在丢失部分数据的情况下根据剩余数据将丢失的数据重建的一组算法。举个例子,如果我想保护六份数据,我会使用一种纠删码算法来产生两份额外的数据,这样总共就会有八份数据。这八份数据中的任意六份数据都能恢复另外两份数据。纠删码的要点是你可以选择对数据做任意数量的分片。我知道一些纠删码可以将数据至多分成200片或者奇数片,你也可以选择校验数

    2022年10月25日
  • maven本地仓库配置了不起作用_仓库数量出错的原因

    maven本地仓库配置了不起作用_仓库数量出错的原因在配置前请先看看这个链接里的东西https://blog.csdn.net/qq_35109803/article/details/80025853如果还是有错误的话就往下文看吧。如果你在配置maven本地仓库输入mvnhelp:system 运行出错的话,不妨试试以下方法。该方法仅对输入mvn-v可以成功运行,而输入mvnhelp:system出现Error的解决方…

  • X-Windows桌面

    X-Windows桌面

    2021年10月15日
  • mysql 截取字符串部分值_mysql截取字符串取值

    mysql 截取字符串部分值_mysql截取字符串取值使用mysql过程中根据实际业务的开发需求和表的设计有时候我们需要在sql中根据某个字符串截取并且取值:demo如下:ifnull(max(SUBSTRING_INDEX(c.check_score,’,’,-1)),’-‘)swjdf//按照,截取check_score这个字段的值,-1取的是倒数第一位即最后一位SUBSTRING_INDEX函数语法:SUBSTRING_INDEX(str…

  • DOM手术台

    DOM手术台

  • 滑动touchmove touchend遇到的问题[通俗易懂]

    今天遇到一个问题,在优化touchmove时候使用了防抖,touchmove和touchend中都改变了元素的样式,问题就产生了。函数节流和防抖都是使用setTimeout做延时,当拖动动作完成之后会触发touchend,touchmove有延时,可能会造成touchend执行之后才执行了touchmove解决办法可以给touchend加一个setTimeout,delay大于节流或者防抖的时…

发表回复

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

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