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;}