首页/新闻资讯/正文详情

P1488 肥猫的游戏【洛谷算法习题】

发布时间:2026/11/21 13:12:45 来源:云帆数科 栏目:资讯中心
P1488 肥猫的游戏【洛谷算法习题】
P1488 肥猫的游戏网页链接P1488 肥猫的游戏题目描述野猫与胖子合起来简称肥猫是一个班的同学他们也都是数学高手所以经常在一起讨论数学问题也就不足为奇了。一次野猫遇到了一道有趣的几何游戏题目便拿给胖子看。游戏要求在一个有n nn个顶点凸多边形上进行这个凸多边形的n − 3 n-3n−3条对角线将多边形分成n − 2 n-2n−2个三角形这n − 3 n-3n−3条对角线在多边形的顶点相交。三角形中的一个被染成黑色其余是白色。双方轮流进行游戏当轮到一方时他必须沿着画好的对角线从多边形上切下一个三角形。切下黑色三角形的一方获胜。胖子一看觉得确实很有趣不如就一起玩玩吧。假设游戏由野猫先开始那么野猫是否有必胜的策略呢请写一个程序帮助野猫算一算。输入格式第一行为一个整数n nn表示多边形的顶点数多边形的顶点由0 00至n − 1 n-1n−1顺时针标号。接着的n − 2 n-2n−2行描述组成多边形的三角形。第i 1 i1i1行( 1 ≤ i ≤ n − 2 ) (1 \leq i \leq n-2)(1≤i≤n−2)有三个空格分隔的非负整数a aa、b bb、c cc它们是第i ii个三角形的顶点编号。第一个给出的三角形是黑色的。输出格式只有一行倘若野猫有必胜策略输出JMcat Win否则输出PZ Win注意大小写和空格。输入输出样例 #1输入 #16 0 1 2 2 4 3 4 2 0 0 5 4输出 #1JMcat Win说明/提示4 ≤ n ≤ 5 × 10 4 4 \leq n \leq 5 \times 10^44≤n≤5×104。如果连接一个多边形中任意两点的线段都完全包含于这个多边形则称这个多边形为凸多边形。解题思路本题是凸多边形三角剖分 博弈论结论推导的经典题目通过将问题转化为对偶树上的删叶子博弈结合奇偶性性质可以得到极简的判定结论无需复杂建图。1. 模型转化对偶树删叶子博弈凸多边形的三角剖分可以转化为一棵对偶树每个三角形对应树的一个节点。若两个三角形共享一条对角线则对应节点之间连边。游戏规则“沿对角线切下三角形”等价于在对偶树上删除叶子节点只有一个邻居的节点对应三角形仅有一条对角线与其余部分相连删除黑色节点的一方获胜。2. 边界特判黑色三角形在边界如果黑色三角形有两条边是原多边形的边界边即该三角形是对偶树的叶子节点那么先手第一步就可以直接切下黑色三角形获胜。判断一条边是否为边界两个顶点的编号差的绝对值为1或者为n-1顶点0与n-1顺时针相邻。3. 一般情况奇偶性结论当黑色三角形不在边界时胜负仅由多边形顶点数n的奇偶性决定若n为偶数先手野猫必胜。若n为奇数后手胖子必胜。原理推导设黑色三角形在对偶树中有k个分支每个分支的节点数为s₁, s₂, ..., s_k。所有分支大小之和为总三角形数减1即sum(s_i) (n-2) - 1 n-3。博弈的胜负由奇数大小的分支数量的奇偶性决定奇数个奇数分支则先手胜偶数个则先手败。而奇数分支的数量的奇偶性等价于所有分支大小之和的奇偶性偶数不改变整体奇偶性也就是n-3的奇偶性完全由n的奇偶性决定。因此无需知道具体剖分结构仅通过n即可判定胜负。4. 复杂度分析时间复杂度为O(1)仅需处理第一个黑色三角形的三个顶点无需依赖其余三角形的剖分信息完美适配n ≤ 5×10^4的数据规模。总结核心逻辑将问题转化为对偶树删叶子博弈特判边界黑三角形直接先手胜其余情况通过n的奇偶性直接判定胜负。关键操作边界边判定、奇偶性结论应用。效率保障常数级运算无需建图与搜索运行速度极快。代码简要说明边界边统计函数check接收黑色三角形的三个顶点逐条边判断是否为原多边形的边界边顶点差绝对值为1或n-1统计边界边总数c。若边界边数等于2说明黑三角形本身就在多边形边界直接输出JMcat Win并结束程序。主函数逻辑读入顶点数n。循环读取三角形数据仅对第一个三角形黑色调用check函数校验边界情况。若未触发边界特判通过(n-5)%2判断奇偶性与n-3奇偶性完全一致结果非零则n为偶数输出JMcat Win否则输出PZ Win。细节说明自定义absl函数计算长整型绝对值避免类型溢出问题。代码中循环读取n次三角形属于不严谨写法标准输入仅有n-2行但由于仅第一个三角形有效不影响最终判定结果。输入优化关闭流同步并解绑tie配合scanf提升大数据量下的读取效率。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll n,x,y,z,c;llabsl(ll a){returna0?a:-a;}voidcheck(ll x,ll y,ll z){ll tabsl(x-y);if(t1||tn-1)c;tabsl(y-z);if(t1||tn-1)c;tabsl(z-x);if(t1||tn-1)c;if(c2){printf(JMcat Win);exit(0);}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld,n);for(ll i1;in;i){scanf(%lld%lld%lld,x,y,z);if(i1)check(x,y,z);}if((n-5)%2)printf(JMcat Win);elseprintf(PZ Win);return0;}

相关推荐

供需适配视角下 智圣新创智慧学生社区服务平台全链路实施指南
供需适配视角下 智圣新创智慧学生社区服务平台全链路实施指南

近年来随着教育部一系列“一站式”学生社区建设相关政策陆续落地,全国高校普遍进入从线下空间改造转向数智化效能升级的关键阶段,智圣新创智慧学生社区服务平台为不同类型院校提供了可落地的标准化建设路径,有效解决了当前多数院校建设过程中… · 2026/9/23 19:24:06

Forsaken喜欢正方形【牛客tracker  每日一题】
Forsaken喜欢正方形【牛客tracker 每日一题】

Forsaken喜欢正方形 时间限制:1秒 空间限制:256M 网页链接 牛客tracker 牛客tracker & 每日一题,完成每日打卡,即可获得牛币。获得相应数量的牛币,能在【牛币兑换中心】,换取相应奖品!助… · 2026/11/21 13:12:45

网文签约前AI率超标怎么办?降到平台要求以内再交稿
网文签约前AI率超标怎么办?降到平台要求以内再交稿

网文签约前AI率超标怎么办?降到平台要求以内再交稿 你已经走到签约这一步了,编辑也点头了,就差把稿子过一遍平台的 AI 检测。结果一测,AI 率超标,编辑委婉地让你"调整一下再交"。到手的签约悬在半空&#x… · 2026/9/23 19:48:01

工地太忙根本没时间复习考试?电工作业邦网上查询全攻略来了
工地太忙根本没时间复习考试?电工作业邦网上查询全攻略来了

工地太忙根本没时间复习考试?电工作业邦网上查询全攻略来了 工地太忙根本没时间复习考试?你不是一个人。很多电工师傅都面临同样的问题:白天忙得脚不沾地,晚上还得熬夜复习备考,身心俱疲。尤其是像电工作业邦这种需要实操和理论结合的考试,更让人头大。… · 2026/11/21 13:12:32

商丘市电工证在哪考全国通用报名门槛不高怎么考
商丘市电工证在哪考全国通用报名门槛不高怎么考

商丘市电工证在哪考全国通用报名门槛不高怎么考 学历不高怕报不上名?别担心, 商丘市电工证在哪考 其实没你想象的那么难,只要掌握方法, 全国通用… · 2026/11/21 13:12:32

特种工操作赵老师郑州报考避坑指南:实操考试心里没底怕挂科?全流程攻略来了
特种工操作赵老师郑州报考避坑指南:实操考试心里没底怕挂科?全流程攻略来了

特种工操作赵老师郑州报考避坑指南:实操考试心里没底怕挂科?全流程攻略来了 实操考试心里没底怕挂科?你不是一个人。在郑州,不少准备报考特种作业操作证的朋友,都曾在考试前焦虑万分,担心一不小心就掉进“挂科”陷阱。今天, 特种工操作赵老师… · 2026/11/21 13:12:32

电工证低压复审费用全攻略:良心建议帮你避开报名陷阱
电工证低压复审费用全攻略:良心建议帮你避开报名陷阱

电工证低压复审费用全攻略:良心建议帮你避开报名陷阱 你是不是还在为不知道去哪报名怕被中介坑而发愁?别急,这篇文章就是 电工证低压复审费用 的良心建议,帮你搞清楚复审流程、费用明细、报名渠道,以及如何用最低成本拿到最靠谱的证书。… · 2026/11/21 13:12:32

电工证宁海哪里考的上岗必须要这个证吗
电工证宁海哪里考的上岗必须要这个证吗

宁海电工证哪里考的值不值得考 实操考试心里没底怕挂科怎么办 实操考试心里没底怕挂科?宁海电工证哪里考的值不值得考,这个问题不少想考电工证的小伙伴都在问。尤其是对于刚入行或打算转行的朋友来说,电工证不仅是一个门槛,更是一把打开行业的钥匙。但面… · 2026/11/21 13:12:32

松江低压电工证在哪考 考了能拿多少工资
松江低压电工证在哪考 考了能拿多少工资

松江低压电工证在哪考 考了能拿多少工资 你是不是正愁找不到工作,手里又没有合适的特种作业证?现在各行各业对特种作业证要求越来越严格, 松江低压电工证… · 2026/11/21 13:11:32

长春初级电工证怎么考?通过率揭秘全在这里
长春初级电工证怎么考?通过率揭秘全在这里

长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/20 16:18:19

国内电工证报考条件与考试时间
国内电工证报考条件与考试时间

低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/20 18:25:07

电工作业时如何断电?电子证书到底能不能全国通用?
电工作业时如何断电?电子证书到底能不能全国通用?

电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/20 17:56:32

电工证征求意见2026河南最新政策怎么应对?学历不高也能考!
电工证征求意见2026河南最新政策怎么应对?学历不高也能考!

电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 你是不是也担心自己学历不高, 怕报不上名 ?尤其是像焦作水利工程这样的从业者,常年在一线作业,但证书却成了晋升、转岗、接项目的关键门槛。 2026河南最新政策… · 2026/11/21 0:00:17

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来
电工证征求意见怎么填?含金量高不高?济源电工朋友看过来

电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 不知道去哪报名怕被中介坑,电工证征求意见填错了不仅白费钱,还可能影响后续考试和工作。最近很多济源的电工朋友都在问: 电工证征求意见怎么填… · 2026/11/21 0:00:17

房建企业特种工考前押题怎么找?别让培训费打了水漂
房建企业特种工考前押题怎么找?别让培训费打了水漂

房建企业特种工考前押题怎么找?别让培训费打了水漂 怕考不过白交培训费?房建企业特种工考试难度高、题型多,很多人报名后才发现没有合适的复习资料,最终考试落榜,白白浪费了时间和金钱。别担心,掌握【考前押题】的技巧,能让你事半功倍,顺利通过考试。… · 2026/11/21 0:00:17

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:45

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:54

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:26:03

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码