题目

点击展开题目

米小游和派蒙在进行一场游戏。游戏在一个基环树（点数与边数相等的无向简单连通图）上进行，定义图中一个点的度数为与其相连的边数，二人轮流进行以下操作：

选择图中一个度数为 1 的点，删除这个点以及与这个点相连的边。

图中有一个特殊的点 x ，删除了点 x 的玩家即获得胜利。

现在，由米小游先进行操作。在双方都采取最优策略的情况下，胜者是谁？

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数 T(1<=T<=1000) 代表数据组数，每组测试数据描述如下：

第一行输入两个整数 n,x(3<=n<=10^5, 1<=x<=n) 表示图的点数及特殊点的编号。

此后 n 行，第 i 行输入两个整数 ui 和 vi (1<=vi,ui<=n ; ui!=vi) 表示树上第 i 条边连接节点 ui 和 vi 。保证图联通，没有重边。

除此之外，保证给定的边构成一个基环树，所有的 n 之和不超过 2*10^5 。

输出描述

对于每一组测试数据，在一行上输出胜者的名字（ Xiaoyo 或 Pyrmont ）。特别地，若点 x 不可能被删除，请输出 Draw 。

示例 1

输入

输出

Xiaoyo
Pyrmont
Draw

如何构造无向图？

        int n = sc.nextInt();
        int x = sc.nextInt();
        
        List<List<Integer>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; ++i) {
            graph.add(new ArrayList<>());
        }

        int[] indegre = new int[n + 1];
        for (int i = 0; i < n; ++i) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
            graph.get(b).add(a);
            indegre[a]++;
            indegre[b]++;
        }

其中， graph[i] 的定义为哪些节点和节点 i 相连，indegre[i] 表示节点 i 的度数（一个点的度数为与其相连的边数）。

博弈思路

这里的博弈思路只能靠自己多举几个样例，然后找规律

以下面的图为例，x 为 2：

graph

在 2 被删除前，最多有 5 6 7 这三个节点可以被删除。

题目中提到：每个人都会按照最优策略进行选择，最后判断谁会获胜。那么，我们的策略是竭尽全力阻止点 x 被被对方删点。

也就是说，对于两个人来说，最优的策略就是尽可能多地删除其他无关紧要的节点，不要把节点 x 暴露给对方。

如果某一轮轮到自己删除节点，假如把 5 删除，那么节点 x 也就是 2 会暴露给对方，自己输掉，所以该轮的最优操作是删除除了节点 5 之外的其他节点。

整体来看，节点 5 是迫不得已不能删除，只能留给对方删除的。

由特殊到一般

假设包含节点 x 在内，最多有 t 个节点可以被删除；
- 如果 t 为偶数，那么「迫不得已只能把删除节点 x 的机会让给对方」的是先手者，后手者赢；
- 反之，如果 t 为奇数，那么「迫不得已只能把删除节点 x 的机会让给对方」的是后手者，先手者赢；
如果删除了所有能删除的节点，但是节点 x 还是不能被删除，那么无解。

解题思路

构造无向图，包括邻接表和度数表
维护一个队列集合，记录当前度数为 1 的所有节点，每次节点出队（也就是被删除）的时候通过邻接表更新度数表，找出度数为 1 的节点入队
通过第二步循环往复，最终得到最多有 n 个节点可以被删除
a. 如果被删除的节点中不包含节点 x，那么无解
b. 否则按照刚刚得到的规律进行分析

代码

package dev.rennen.exam.mihoyo0803;

import java.util.*;

/**
 * @author rennen.dev
 * @date 2024/8/5 14:52
 */
public class Test3 {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        int T = sc.nextInt();
        for (int i = 0; i < T; i++) {
            solve();
        }
    }

    static void solve() {
        int n = sc.nextInt(), x = sc.nextInt();
        // 初始化图
        List<List<Integer>> graph = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }
        int[] indegree = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int t1 = sc.nextInt(), t2 = sc.nextInt();
            graph.get(t1).add(t2);
            graph.get(t2).add(t1);
            indegree[t1]++;
            indegree[t2]++;
        }
        // 初始化集合
        LinkedList<Integer> deletable = new LinkedList<>();
        // 所有可被删除的节点总数
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 1) {
                if (i == x) {
                    // 如果最开始节点 x 的度数就是 1，那么肯定先手赢
                    System.out.println("Xiaoyo");
                    return;
                }
                deletable.add(i);
            }
        }
        boolean solvable = false;
        while (!deletable.isEmpty()) {
            int t = deletable.removeFirst();
            count++;
            if (t == x) {
                solvable = true;
                continue;
            }
            for (int i : graph.get(t)) {
                indegree[i]--;
                if (indegree[i] == 1) {
                    deletable.add(i);
                }
            }
        }
        if (!solvable) {
            System.out.println("Draw");
        } else if (count % 2 == 0) {
            System.out.println("Pyrmont");
        } else {
            System.out.println("Xiaoyo");
        }
    }
}

参考资料

米哈游秋招第一场笔试，难度中等（0803笔试真题解析）

Rennen