洛谷P4018 Roy&October之取石子 题解 博弈论

题目链接：https://www.luogu.org/problem/P4018

首先碰到这道题目还是没有思路，于是寻思还是枚举找一找规律。

然后写了一下代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 101;

bool win[maxn];

bool isp(int a) {

    if (a < 2) return false;

    for (int i = 2; i * i <= a; i ++)

        if (a % i == 0)

            return false;

    return true;

}

void check(int n) {

    win[n] = false;

    if (!win[n-1]) {

        win[n] = true;

        return;

    }

    for (int p = 2; p <= n; p ++) {

        if (!isp(p)) continue;

        for (int q = 1; q <= n; q *= p) {

            if (win[n-q] == false) {

                win[n] = true;

                return;

            }

        }

    }

}

int main() {

    for (int i = 1; i < maxn; i ++) {

        check(i);

        printf("check (%d) ", i);

        puts(win[i] ? "YES" : "NO");

    }

}

输出结果如下：

check (1) YES

check (2) YES

check (3) YES

check (4) YES

check (5) YES

check (6) NO

check (7) YES

check (8) YES

check (9) YES

check (10) YES

check (11) YES

check (12) NO

check (13) YES

check (14) YES

check (15) YES

check (16) YES

check (17) YES

check (18) NO

check (19) YES

check (20) YES

check (21) YES

check (22) YES

check (23) YES

check (24) NO

check (25) YES

check (26) YES

check (27) YES

check (28) YES

check (29) YES

check (30) NO

check (31) YES

check (32) YES

check (33) YES

check (34) YES

check (35) YES

check (36) NO

check (37) YES

check (38) YES

check (39) YES

check (40) YES

check (41) YES

check (42) NO

check (43) YES

check (44) YES

check (45) YES

check (46) YES

check (47) YES

check (48) NO

check (49) YES

check (50) YES

check (51) YES

check (52) YES

check (53) YES

check (54) NO

check (55) YES

check (56) YES

check (57) YES

check (58) YES

check (59) YES

check (60) NO

check (61) YES

check (62) YES

check (63) YES

check (64) YES

check (65) YES

check (66) NO

check (67) YES

check (68) YES

check (69) YES

check (70) YES

check (71) YES

check (72) NO

check (73) YES

check (74) YES

check (75) YES

check (76) YES

check (77) YES

check (78) NO

check (79) YES

check (80) YES

check (81) YES

check (82) YES

check (83) YES

check (84) NO

check (85) YES

check (86) YES

check (87) YES

check (88) YES

check (89) YES

check (90) NO

check (91) YES

check (92) YES

check (93) YES

check (94) YES

check (95) YES

check (96) NO

check (97) YES

check (98) YES

check (99) YES

check (100) YES

发现只要不是 \(6\) 的倍数就是必胜态，只要是能被 \(6\) 整除就是必败态。

找到规律之后编写如下代码AC：

#include <bits/stdc++.h>

using namespace std;

int T, n;

int main() {

    cin >> T;

    while (T --) {

        cin >> n;

        puts( n % 6 ? "October wins!" :"Roy wins!" );

    }

    return 0;

}

然后来证明：

首先我们知道，所有 \(6^k\)（其中 \(k\) 为任意自然数）都不会是 \(p^k\) （其中 \(p\) 是素数）。

然后我们假设前 \(6 \times n\) 个状态已经确定了，并且所有的 \(6\) 的倍数都是必败态，其它状态都是必胜态。

然后因为 \(6n+1, 6n+2, 6n+3, 6n+4, 6n+5\) 都可以转换到必败态 \(6n\) ，所以这5个都是必胜态。

而 \(6n+6\) 不能转换到 \(6n, 6n-6, \dots 6, 0\) ，所以 \(6n+6\) 无论如何取都只能达到必胜态，所以 \(6n+6\) 就是必败态。

综上所述：所有 \(6\) 的倍数都是必败态，其他状态都是必胜态。