P9772 [HUSTFC 2023] 网格染色 题解

· · 题解

P9772题目传送门

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

Part -1：赛时唠嗑

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

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

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

不出所料听取WA声一片。

Part 0：题目分析

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

这题一看就是博弈论。

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

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

于是，我们便可以枚举 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 即可。