[THUPC 2024 初赛] 三步棋

鸣谢 cinccout。赛时两次看出了我的错误/bx。

闲话：在我看过的所有人的做题过程中，大家都不约而同的把 棋子数量相同时答案相同 当作了第一发（。但是很可惜，这个结论是错误的。

样例已经给出了当棋子数量为 \(2\) 的答案，在此我们略去讨论。

对于棋子数量为 \(1\) 答案也很明显是后手必胜。

在进行讨论前，需要声明：能够通过旋转任意角度重合的两个图形，他们的答案相同。

对于证明，考虑虽然形状不能转，但是由于棋盘是正方形，所以我们可以旋转棋盘并且不改变形状，显然同一种形状的不同摆放状态都是相同的答案。

棋子数量为 \(3\) 时

对于棋子数量为 \(3\)，我们有两种本质不同的情况。即

o
oo ooo

第二种样例中已给出答案，故略去讨论。对于第一种形状，这里给出一种必胜策略。

假设目标图形为

o    101
oo   010

（右侧为先后顺序，并且第三列可以决胜负）

第一步随便下，对于后手的第二步肯定不能帮助先手拼凑图形，否则在下一步先手可以直接获得胜利。那么后手只要不下在先手的图形位置上就可以到下一轮。

我们发现第二轮的先手无法取胜，而在第二轮结束前后手总共有三步棋，可以直接按照自己的节奏胜利。

不过事情并没有这么简单。我们观察发现，角落里的一些格子似乎有着非凡的作用。

当图形如上时，如果我们下在棋盘的右上角那么，我们发现这一格无法作为形状中的任何一颗棋出现。于是相当于把相同的局面交给了后手，不过后手有三步可以操作是确实的，所以在这种情况中，先手无法干扰后手的必胜，故后手必胜。

棋子数量为 \(4\) 时

总共有如下五种本质不同的形状。

     o   ooo oo  oo
oooo ooo  o   oo oo

我们不妨从刚刚那种角落的棋子入手，这种存在可以交换先后手。我们发现 除了长条和方块形状 的其余形状，棋盘上都有 两 个位置，无法充当形状的部分。

这告诉我们，当我们想要 借先手的某枚棋子 构造从而在第二轮结束游戏时，先手可以下在这样的位置，从而变为后手。不过由于这样的位置有两个，所以后手可以再下在这样的地方变回先手。

经过这样的过程，我们的先后图变为了

xx1
010
101

我们发现后手在第二轮无法结束游戏，即使借助先手的一枚棋子构造也也只有 \(1 + 2 = 3\) 的操作空间。

而先手可以在第三轮以 \(1 + 4 = 5\) 的操作空间差取得胜利。

对于长条和方块形，没有上述类似的无用点，先手无法在第一轮结束，后手可以用 \(1 + 3\) 都操作空间结束游戏。

至此，我们结束了所有讨论。抓住会影响先后以及棋子数量的无用点，以及双方的操作空间大小，再细致讨论即可。