QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: jiangly

Posted at: 2025-12-12 23:29:40

Last updated: 2025-12-12 23:29:43

Back to Problem

题解

轮到后手时,如果局面是 $3k$ 个 $1$ 则必败。所以轮到先手时如果局面是 $3k$ 个 $1$ 加上任意非零数,或是 $3k-1$ 个 $1$ 加上一个大于 $1$ 的数则必胜。实际上这就是充要条件。

注意到 $n\bmod 3=2$ 时先手必败。如果轮到后手时,有 $n\bmod 3=0$ 堆石子,且有一堆大于 $1$,则可以两次拿掉这堆大于 $1$ 的,变成 $n\bmod 3=2$ 的局面。如果 $n\bmod 3=1$,则任意拿掉两堆(如果 $n=1$ 直接获胜),同样变成 $n\bmod 3=2$。

再注意到先手必胜的必要条件是最多一堆大于 $1$。如果轮到后手 $n\bmod 3=2$ 且 $n\ge 5$,且有两堆大于 $1$,拿掉其余的两堆,剩下还有两堆大于 $1$。否则只有一堆大于 $1$,我们拿掉两堆,剩下 $n\bmod 3=0$ 个 $1$,仍然是先手必败。

Comments

No comments yet.