洛谷P4136 谁能赢呢？ 题解 博弈论

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

找规律

首先这道题目我没有什么思路，所以一开始想到的是通过搜索来枚举 \(n\) 比较小的时候的情况。

所以我开搜索枚举了 \(n \le 8\) 的所有情况。

搜索代码：

#include <bits/stdc++.h>

using namespace std;

const int maxn = 11;

int n;

bool vis[maxn][maxn], res[maxn][maxn];

int dir[4][2] = { -1, 0, 1, 0, 0, -1, 0, 1 };

inline bool in_map(int x, int y) { return x >= 0 && x < n && y >= 0 && y < n; }

bool dfs(int x, int y) {

    vis[x][y] = true;

    res[x][y] = false;

    bool flag = false;

    for (int i = 0; i < 4; i ++) {

        int xx = x + dir[i][0], yy = y + dir[i][1];

        if (!in_map(xx, yy) || vis[xx][yy]) continue;

        dfs(xx, yy);

        if (!res[xx][yy]) {

            res[x][y] = true;

            break;

        }

    }

    vis[x][y] = false;

}

void check() {

    printf("check (%d) : ", n);

    memset(vis, 0, sizeof(vis));

    memset(res, 0, sizeof(res));

    dfs(0, 0);

    puts(res[0][0] ? "YES" : "NO");

}

int main() {

    for (n = 1; n <= 8; n ++) check();

    return 0;

}

输出结果是：

check (1) : NO

check (2) : YES

check (3) : NO

check (4) : YES

check (5) : NO

check (6) : YES

check (7) : NO

check (8) : YES

所以，可以发现：当 \(n\) 为偶数时，先手胜，当 \(n\) 为奇数时，后手胜。

然后这道题目就这样通过 找规律 找到了一个假想的规律。

然后就AC了：

#include <bits/stdc++.h>

using namespace std;

int n;

int main() {

    while ( (cin >> n) && n ) {

        puts( (n % 2 == 0) ? "Alice" : "Bob" );

    }

    return 0;

}

然后证明转自 Shallowy大神的博客

想象一下，可以 把整个棋盘拆成若干个1*2的格子 ，那么，

很明显，后手只是从一个小格子的一侧走到了另一侧；

而先手则找到了一个新的格子。

因为后手只需走，但先手要找，所以在某个时刻游戏结束时，一定是先手找不到格子了...

当n为偶数时，棋盘能完美地被拆掉——可是先手会找不到；当n为奇数时，先手才能赢。