题解：P2252 [SHOI2002] 取石子游戏 |【模板】威佐夫博弈

题目传送门

问题分析

游戏规则：有两堆石子，每次可以从一堆中取任意多石子，或从两堆中取相同数量的石子。

胜利条件：

取走最后一颗石子者获胜。

关键发现： 若满足以下条件不管怎么拿都会输。

1.若两堆石子数量为(a, b) 且

a \le b

。

2.当且仅当

a = ⌊k\cdot \varphi⌋ , b = a + k

时，当前玩家必败。

3.其中

\varphi

是黄金比例

(\frac{\sqrt{5}+1}{2} \approx 1.618

，k 是正整数）。

Code：

CPP

#include <bits/stdc++.h>
#define int long long

using namespace std;

signed main() {
    int a, b;
    cin >> a >> b;
    
    if (a > b) swap(a, b);
    int k = b - a;
    
    // 计算 w = floor(k * phi)，其中 phi = (1+sqrt(5))/2
    // 利用 phi 的性质：phi = 1 + 1/phi，且 w = (k * (sqrt(5) + 1)) / 2 的整数部分
    // 用高精度计算避免误差
    long double phi = (1.0L + sqrtl(5.0L)) / 2.0L;  // 用 long double 提高精度
    long double k_phi = k * phi;
    int w = (int)k_phi;
    if (w == a && k_phi < w + 1.0L) {
        cout << 0 << endl;
    } else {
        cout << 1 << endl;
    }
    
    return 0;
}

题解：P2252 [SHOI2002] 取石子游戏 |【模板】威佐夫博弈

文章操作

题目传送门

问题分析

Code：

相关推荐

评论

题解：P2252 [SHOI2002] 取石子游戏 |【模板】威佐夫博弈