自动搬运

查看原文

来自洛谷，原作者为

	Hu0_gu0_4u31 ——暗殺教室系列学家、珂学家，florr.io450+粉（网址去掉.cn看个人介绍）

搬运于2025-08-24 22:51:43，当前版本为作者最后更新于2023-12-04 22:24:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P9772题目传送门

本蒟蒻发布的第一篇题解纪念！

Part -1：赛时唠嗑

当我比赛时点进这题时心想：这不就是博弈论吗？多试一试就能过！

首先对题目进行一顿分析，然后写出代码：

n = int(input())
if n % 2:
    print('Kelin')
else:
    print('Draw')

不出所料听取WA声一片。

Part 0：题目分析

题目描述大概是两个人走一种棋子，可以通过给一个格子周围四个地方都染上色来得分。最终得分多者胜。得分相同即为平局。

这题一看就是博弈论。

那我们就要思考获胜的情况了。

题目只给出了 $n$，因此情况无非就这几种：

• 输出固定答案。

• 根据 $n \bmod k$（$k$ 为任意整数且 $k>0$）的结果判断答案。

于是，我们便可以枚举 $n=1$，$n=2$ 等的情况。

Part 1：开始做题

首先来看看 $n=1$。

很显然，由于只有四个地方可以下，后手必胜。

那么 $n=2$ 呢？样例已经给出，后手必胜。

那么 $n=3$ 呢？我们可以枚举几种情况，也可以得出后手必胜。

由于答案只有三种，因此我们就可以大胆地猜想：后手必胜。

print('Kelin')

Part 2：必胜策略

既然结论是后手必胜，那我们要证明必须找到必胜策略。

后手必胜的策略是：画出整个网格的对角线。

如果 Walk Alone 下在一个位置，那么 Kelin 就下在与它对于网格对角线呈轴对称的位置。

由此可见，如果下的位置所在的正方形不在对角线上，几回合下来这个位置所在的正方形如果是 Walk Alone 得分，轴对称的位置就是 Kelin 得分，反之亦然。

如果下的位置所在的正方形在对角线上，显然是 Kelin 得分。

由于每个方格的分数最终一定所有人都会拿到，因此因为 Kelin 有对角线得分优势，最终总是 Kelin 获胜。

以上就是这题的必胜策略。

因此，本题输出 Kelin 即可。