用并查集,方法模仿POJ2492A Bug's Life, 这题是2*n个数,如果a和b是异性,那么a和b+n,b和a+n是同性,这样在判断a和b是否是同性时可以通过a+n,或b+n来判断。
而1182 这题是类似的方法,如果 b 被 a 吃,那么 a 和 b+n , a+n 和 b+2*n ,b 和 a+2*n
是同类。如果输入有“1 A B”, 如果A,B不同类 或 B 吃 A 则这句话是假的。
#include<cstdio>
int pre[150002];
void init(int n)
{
int i;
for(i=0;i<=n*3;i++)
{
pre[i]=-1;
}
}
int find(int x)
{
int p;
p=x;
while(pre[p]>=0)
{
p=pre[p];
}
return p;
}
int unit(int x,int y)
{
int a,b;
a=find(x);b=find(y);
if(a==b)
return 0;
else
if(pre[a]<pre[b])
{
pre[a]+=pre[b];pre[b]=a;
}
else
{
pre[b]+=pre[a];pre[a]=b;
}
return 0;
}
int main()
{
int n,k,i,j,a,b,c;
scanf("%d%d",&n,&k);
init(n);
int ans = 0;
while(k--)
{
scanf("%d%d%d",&a,&b,&c);
if(b>n||c>n||(a==2&&b==c))
{
ans ++;
continue;
}
if(a==1)
{
if(!(((find(b)==find(c+n))||(find(b+n)==find(c+2*n))||(find(c)==find(b+2*n)))
||((find(c)==find(b+n))||(find(c+n)==find(b+2*n))||(find(b)==find(c+2*n))))) // 如果不是 A 吃 B 或 B 吃 A
{
unit(b,c);
unit(b+n,c+n);
unit(b+2*n,c+2*n);
}
else ans++;
}
if(a==2)
{
if(find(b)==find(c)||((find(c)==find(b+n))||(find(c+n)==find(b+2*n))||(find(b)==find(c+2*n))))// 如果A,B不同类 或 B 吃 A
ans ++;
else
{
unit(b,c+n);
unit(b+n,c+2*n);
unit(c,b+2*n);
}
}
}
printf("%d\n",ans);
}
分享到:
相关推荐
2023-04-06-项目笔记-第二百六十一阶段-课前小分享_小分享1.坚持提交gitee 小分享2.作业中提交代码 小分享3.写代码注意代码风格 4.3.1变量的使用 4.4变量的作用域与生命周期 4.4.1局部变量的作用域 4.4.2全局变量的作用域 4.4.2.1全局变量的作用域_1 4.4.2.259局变量的作用域_259- 2024-09-19
项目工程资源经过严格测试可直接运行成功且功能正常的情况才上传,可轻松复刻,拿到资料包后可轻松复现出一样的项目,本人系统开发经验充足(全领域),有任何使用问题欢迎随时与我联系,我会及时为您解惑,提供帮助。 【资源内容】:包含完整源码+工程文件+说明(如有)等。答辩评审平均分达到96分,放心下载使用!可轻松复现,设计报告也可借鉴此项目,该资源内项目代码都经过测试运行成功,功能ok的情况下才上传的。 【提供帮助】:有任何使用问题欢迎随时与我联系,我会及时解答解惑,提供帮助 【附带帮助】:若还需要相关开发工具、学习资料等,我会提供帮助,提供资料,鼓励学习进步 【项目价值】:可用在相关项目设计中,皆可应用在项目、毕业设计、课程设计、期末/期中/大作业、工程实训、大创等学科竞赛比赛、初期项目立项、学习/练手等方面,可借鉴此优质项目实现复刻,设计报告也可借鉴此项目,也可基于此项目来扩展开发出更多功能 下载后请首先打开README文件(如有),项目工程可直接复现复刻,如果基础还行,也可在此程序基础上进行修改,以实现其它功能。供开源学习/技术交流/学习参考,勿用于商业用途。质量优质,放心下载使用。
本文阐述了人工智能在数据中心节能应用领域的理论与实践,通过介绍机器学习和基于物理机理模型的人工智能节能技术的应用情况,展示了如何利用AI技术来提升数据中心能源效率,减少PUE。并指出基于大数据分析的智能运维方法能优化数据中心冷却系统的运行状态,从而达成绿色节能目的;同时也强调了未来的节能系统发展趋势及标准化推进措施等重要方向。 适用人群:数据中心管理人员,环保工作者,信息和通信技术行业的专业人士。 使用场景及目标:适用于那些希望利用AI和其他技术优化其数据中心效能的企业;通过技术手段达到减少能耗、提升工作效率的目的。 其他:随着全球对环境友好技术的关注增加,在数据中心的建设和运维过程中融合AI等新技术已经成为必然趋势。
基于java的网上球鞋竞拍系统设计与实现.docx
【c语言入门】 静态库、动态链接库、include、makefile、io、文件操作函数、管道原理及应用、简单的数据结构
基于java中药分类管理系统设计与实现.docx
内容概要:文中针对大斜视SAR系统在动目标成像上遇到的各种问题,包括聚焦难、几何变形和交叉副瓣高等挑战,采用了一个融合了频谱旋转和稀疏化增强处理方式的新颖算法——频谱旋转ωk算法,进行了详细讨论并提供了一套完整解决方案。 适用人群:该研究对于SAR技术研究专家、学者、工程师有着特别的实际意义与价值。 使用场景及目标:本成果可应用于斜视角达到甚至超过七十度的高斜度SAR动目标成像系统中,提升动目标检测、定位、识别等能力。具体应用场景涵盖了战场态势监测、交通流量监管等多个领域。 本文通过详细的理论建模及仿真实验结果论证算法的有效可行性;此外,文中提及了未来在更高动态环境下SAR成像领域的扩展可能性。
基于java的新闻发布系统设计与实现.docx
基于java的应急资源管理系统设计与实现.docx
基于java的斗车交易系统设计与实现.docx
主要内容:文章探讨了随着6G通讯技术发展,将通感一体化应用于车联网的可能性及其带来的显著效果,尤其是在辅助自动驾驶、多车合作感知与控制、车路通感融合发展中的应用。通过阐述各方面的技术框架和细节(如波束管理和智能反射面技术),文中指出了车联网系统在实现高效率、安全性以及智能化管理上的关键突破。同时强调在实施中遇到诸如频带分配、信号混迭、硬件整合等现实挑战,并提出了未来发展方向。 适用人群:研究人员和开发人员,特别是从事车联网和新一代通讯技术支持的专业人士。 使用场景及目标:适用于车联网的研究和开发,目的是构建高效的交通通信系统,在实际使用中促进自动驾驶、智能交通管理系统等新技术落地,提高道路通行的安全性和效率。 相关背景与建议:本文对通感一体化的技术介绍深入浅出,并讨论了一系列技术前沿,包括智能反射技术的最新成果。阅读者应掌握一定的无线通讯基础知识,并能理解技术理论在工程实践里的潜在机遇与难题。
均包含代码,文章,部分项目包含ppt
均包含代码,文章,部分项目包含ppt
2019李宁跑步自媒体年度内容运营方案.pptx
基于java的中国咖啡文化宣传网站的设计与实现.docx
基于java的学生考勤管理设计与实现.docx
安卓开发:探索移动应用的无限可能
34521945-b0e9-461e-8b69-6436502dee5b-1.zip
完整的项目源码(注意更换自己的数据库名,并且字段设置要一样)
1.版本:matlab2014/2019a/2024a 2.附赠案例数据可直接运行matlab程序。 3.代码特点:参数化编程、参数可方便更改、代码编程思路清晰、注释明细。 4.适用对象:计算机,电子信息工程、数学等专业的大学生课程设计、期末大作业和毕业设计。