Codeforces 1363C - Game On Leave

日常一道算法题。

翻译

叶子游戏

Ayush 和 Ashish 在一个有 n 的节点的无根树玩游戏，节点为 1 到 n。玩家轮流进行以下操作：

• 选择一个叶子节点，移除它并且移除与它相连的边，叶子节点就是度小于等于1的节点。

一棵树是无项无环图，x是特殊节点，移除这个节点的玩家会赢得游戏。

Ayush先手，假定两个人都进行最优选择。

输入格式

输入整数 t 表示测试用例数。

每个测试用例，第一行输入 n x，接下来 n - 1 行输入 u v，表示 u 和 v 两个节点相连。

输出格式

输出赢家 Ayush 或 Ashish

分析

这是一道简单博弈论，最开始思路错了，写成了最小的操作次数，当然就错了。

应该求最大的操作次数，然后对 2 取余求结果。有两种情况：

1. 如果开始 x 就只有1个边或者0个边，那么只需要 1 步操作就赢了， 所以是 Ayush。
2. 如果开始 x 有多个边，那么求完最大的操作次数然后再减一，(因为需要求剩一个节点的次数，剩余x 和 另一个节点的情况下，玩家会直接移除 x)，然后对 2 取余。

用到了广度优先搜索，很久没写了，嘿嘿。

代码(Python 3)

# https://codeforces.com/problemset/problem/1363/B

import sys
import os
import heapq
import math

try:
    path = "./file/input.txt"
    if os.path.exists(path):
        sys.stdin = open(path, 'r')
    # sys.stdout = open(r"./file/output.txt", 'w')
except:
    pass

t = int(input())

def printd(value):
    # print(value)
    pass

graph = []
x = 0

def dfs(depth, index):
    global graph

    if len(graph[index]) <= 1 and index == x:
        return 1

    if len(graph[index]) == 0:
        return 1

    sumvalue = 1
    maxvalue = 0    

    for value in graph[index]:
        graph[value].remove(index)
        result = dfs(depth + 1, value)

        sumvalue += result

    if x == index:
        sumvalue -= 1

    return sumvalue

def case():
    global x
    arr = list(map(int, input().split(" ")))
    n, x = arr[0], arr[1]

    global graph
    graph = []

    for _ in range(n + 1):
        graph.append([])

    for _ in range(n - 1):
        arr = list(map(int, input().split(" ")))
        a, b = arr[0], arr[1]
        
        graph[a].append(b)
        graph[b].append(a)

    print("Ayush" if dfs(1, x) % 2 == 1 else "Ashish")

for _ in range(t):
    case()

更多代码尽在 https://github.com/Tconan99/Codeforces

by 费城的二鹏 2020.06.05 长春