Oiclass PUJI 1277 题解

博弈论

题目简述

有 \(n\) 个硬币，两位玩家，每次去取 \(l \sim r\) 个，取不到者负，都执行最优策略，哪一方必胜？

思路

和显然，这个问题就是博弈论中十分经典的 Nim 取子问题 。首先我们发现，对于一种状态，如果后面的任何状态都是必败状态，那么我们可以发现，这个状态就是我们常说的必胜态，因为，无论下一步怎么走，都是无法获胜。而同时，如果一个状态后面有必胜态，那么这个状态就是必败态，因为我们下一步的人可以执行最优策略到达这个必胜态。

了解了这个思路之后，我们就可以开始写代码了。

实现

我们可以很轻易的写出像这样的代码：

#include <iostream>

#define int long long

using namespace std;

int t, n, l, r;

bool dfs(int x, int left, int right) {
    if (x == 0 || x < left) {
        return false;
    }
    if (left <= x && x <= right) {
        return true;
    }
    bool p = true;
    for (int i = left; i <= right; i++) {
        if (x - i >= 0) {
            p &= dfs(x - i, left, right);
        }
    }
    return !p;
}

signed main() {
    cin >> t;
    while (t--) {
        cin >> n >> l >> r;
        cout << (dfs(n, l, r) ? "yes\n" : "no\n");
    }
}

如果你尝试提交，那么恭喜你的代码拿到了 \(0\) 分的好成绩。为什么？代码中的 DFS 实在太垃圾了，导致了严重的时间超限和内存超限。

我们考虑如何优化。对r于参与游戏的两人，在可取的情况下，他们肯定是拼尽全力的多取的，因此，我们会发现，当 \(n \geq l + r\) 时，两人的胜率始终维持在 \(50 \%\) 。因此，我们会发现只有当 \(n \leq l + r\) ，二者的胜率才会有所改变，因此，我们只需要考虑胜率不同的一部分即可。故我们可以将 \(n\) 取模 \(l + r\) 再进行计算。这样的做法大大缩减了 DFS 函数的时间和空间需求优化了我们程序的性能。同时也能保证答案正确。

AC Code：

#include <iostream>

#define int long long

using namespace std;

int t, n, l, r;

bool dfs(int x, int left, int right) {
    if (x == 0 || x < left) {
        return false;
    }
    if (left <= x && x <= right) {
        return true;
    }
    bool p = true;
    for (int i = left; i <= right; i++) {
        if (x - i >= 0) {
            p &= dfs(x - i, left, right);
        }
    }
    return !p;
}

signed main() {
    cin >> t;
    while (t--) {
        cin >> n >> l >> r;
        n %= (l + r);
        cout << (dfs(n, l, r) ? "yes\n" : "no\n");
    }
}