米哈游 8.3 笔试

第三题我也是这么想的，看微信公众号其他人是使用拓扑排序解的！

拓扑排序+GTO博弈论。 所谓的基环树指的是：在一棵树的基础上加上一个环。 以后大家看到这种：每个人都会按照最优策略进行选择，最后判断谁会获胜。这种字眼的时候，基本就可以确定是一个GTO（博弈论）的题目。基本的做题思路就是找到一个规律可以直接得出结论的。 对于这道题，有一个显而易见的结论，如果x在环中，那么无论如何删点都不可能删的掉，因此必然是Draw。 如果点不在环中呢？ 我们可以考虑在删除x点之前（包括x），有多少个节点是可以删除的？假设这个值是cnt。 如果cnt是偶数的话，那么Xiaoyo作为先选取的一方，一定是无法删除这个点的。因为双方的操作是对称的。 反之，则是Pyrmont获胜。 因此大题思路与拓扑排序类似，不断地将度数为1的节点加入队列，记录在删除x节点之前最多可以访问的节点数（包括x节点）。最后判断x的奇偶性即可。 需要注意的是 如果x节点是在环中的，那么我们永远无法遍历到这个节点，此时必然是Draw。 如果x节点的度数初始值就是1，那么此时Xiaoyo获胜。 C++