P5932 多边形之战(简单博弈)

· · 题解

先回顾一下题目描述：

在一个有 n 个顶点的凸多边形上进行，这个凸多边形的 n-3 条对角线将多边形分成 n-2 个三角形。三角形中的一个被染成黑色，其余是白色。两方轮流沿着画好的对角线切三角形，想要赢得切黑色三角形。

分析：

那么，你要沿着画好的对角线就说明：得保证切的三角形两条边都在现在的多边形边上（即内部的三角形一定得在外部的三角形切完了才能切）

我们可以把这个图看作一棵树，记黑色三角形为源点，相邻两个三角形所代表的点连边。

那么可以发现一个结论： 一个三角形可以切 \iff 它是叶子结点。

继续分析：

$2$. 若共有偶数个点，先手一定可以在保证儿子数 $>1$ 的情况下把白点取成偶数个，那么上面 $1$ 情况的状态一定是后手取出来的，先手必胜。 $3$. 若共有奇数个点，先手只能把局面转成上面两种情况中的一种，先手必败。 代码没什么好说的，上面已经说得很清晰，直接按照题目输入、建图、判断、输出就可以 AC 了。 #### p.s. 其实蛮像入门版的 sg 函数必胜点和必败点了