洛谷 P2024 [NOI2001]食物链
2018-08-13 07:35:40来源:博客园 阅读 ()
题目链接
点这里ww
题目描述
动物王国中有三类动物 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 句话,输出假话的总数。
题解
这道题我用了并查集求解
主要应用了反集的思想
详见注释
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 6 const int maxn=50005; 7 int f[maxn*3],ans=0;//x为本身,x+n为猎物,x+n*2为天敌 8 9 int find(int k){//查找 10 if(f[k]==k) 11 return k; 12 return f[k]=find(f[k]); 13 } 14 15 void unionn(int x,int y){//合并 16 x=find(x); 17 y=find(y); 18 f[x]=y; 19 } 20 21 int main(){ 22 int n,k; 23 cin>>n>>k; 24 for(int i=1;i<=n*3;i++){ 25 f[i]=i; 26 } 27 for(int i=1;i<=k;i++){ 28 int judge,x,y; 29 cin>>judge>>x>>y; 30 if(x>n || y>n){ 31 ans++;//在范围之外,是假话 32 continue; 33 } 34 if(judge==1){ 35 if(find(x+n)==find(y) || find(x+n*2)==find(y)){ 36 ans++;//本身与天敌与猎物不可能为同类 37 continue; 38 } 39 unionn(x,y); 40 unionn(x+n,y+n); 41 unionn(x+n*2,y+n*2); 42 continue; 43 } 44 if(judge==2){ 45 if(x==y){ 46 ans++;//我吃我自己 47 continue; 48 } 49 if(find(x)==find(y) || find(x+n*2)==find(y)){ 50 ans++;//我吃我自己 && 吃天敌 51 continue; 52 } 53 unionn(x+n*2,y+n); 54 unionn(x+n,y); 55 unionn(x,y+n*2); 56 continue; 57 } 58 } 59 cout<<ans; 60 return 0; 61 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:Qt动态链接库的创建和使用
- 洛谷P1164->小A点菜 2020-05-18
- 洛谷P1907口算练习题 2020-03-24
- 结题报告--P5551洛谷--Chino的树学 2020-03-13
- 结题报告--洛谷P3915 2020-03-13
- 洛谷P1034 矩形覆盖 2020-03-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash