Luogu P1290 欧几里德的游戏

题目描述

https://www.luogu.com.cn/problem/P1290

Solution

我们不妨令当前局面为 $(a,b)$，其中 $a>b$

注意到问题可以转换为有 $n$ 堆按照顺序排好的石子，每个人只能操作第一堆石子，每次可以拿任意个

注意到如果当前第一堆石子的数量大于 $1$，那么先手必胜，因为无论将第一堆石子去掉之后的局面是必胜还是必败，先手总能获胜（如果必胜，那么将第一堆拿到剩 $1$ 个，如果必败，直接将第一堆拿完

所以我们递归判断即可

#include <iostream>
#include <cstdio>
using namespace std;

int n, m;

bool dfs(int a, int b, int p) {
    if (a % b == 0) return p;
    if (a / b >= 2) return p;
    return dfs(b, a - b, p ^ 1); 
}

void work() {
    cin >> n >> m;
    if (n < m) swap(n, m);
    cout << (dfs(n, m, 1) ? "Stan wins" : "Ollie wins") << "\n"; 
} 

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0;
} 

现在唯一的问题就是假设我们有多个欧几里得游戏，那么我们就需要计算一个游戏的 $sg$ 值

我们不妨设有 $n$ 堆石子，每堆石子的数量为 $a_i$

那么游戏的 $sg$ 值应该为

int sg = a[n];
for (int i = n - 1; i; --i)
    sg = a[i] - (sg >= a[i]);

至于原因，我大概写一下（因为我也是猜的

首先对于第一堆之后的石子，我们不妨设其 $sg$ 值为 $y$，那么我们就能把后面一大堆石子替换成一堆有 $y$ 个石子，不妨设第一堆石子有 $x$ 个（正确性存疑

我们考虑暴力计算 $(x,y)$ 的 $sg$ 值，我们有 $sg(x,y)=mex\{sg(x-1,y),sg(x-2,y),\cdots ,sg(1,y),sg(y)\}$

注意到如果 $sg(y)=y$，那么如果 $y>=x$，那么容易得到 $sg(x,y)=x-1$

如果 $y<x$，那么 $sg(x,y)=x$，那么 $sg$ 值的计算就如上式，我们倒着合并即可

正确性仍然存疑