题解：UVA1482 Playing With Stones

chenwenmo · 2025-06-23 20:42:37 · 题解

这是一个有向图博弈，直接考虑 SG 函数。

先设最终状态，即 \mathrm{SG}(0)=\mathrm{SG}(1)=0，

那么 \mathrm{SG}(i) = \mathrm{mex}_{j=1}^{\lfloor\frac{i}{2}\rfloor} \mathrm{SG}(i-j)，

赛时可以通过暴力打表发现规律，也可以考虑数学证明。

结论：\mathrm{SG}(x)=\begin{cases}\frac{x}{2} & x\bmod 2=0 \\ \mathrm{SG}(\frac{x-1}{2}) & x\bmod 2=1\end{cases}

证明：

当 x\le 2 时结论成立，

当 x > 2 时，假设 \forall y<x，结论成立，

• 设 $S$ 为 $x$ 的转移点集合， - 对于 $y\in S,y\bmod 2=0$，$\mathrm{SG}(y)$ 覆盖 $[\lceil\frac{x}{4}\rceil,\frac{x}{2}]$； - 对于 $y\in S,y\bmod 2=1$，发现这些 $y$ 对应的 $\frac{y-1}{2}$ 构成 $z$ 的转移点，其中 $z=\begin{cases}\frac{x}{2}+1 & \frac{x}{2}\bmod 2=1 \\ \frac{x}{2} & \frac{x}{2}\bmod 2=0\end{cases}$，（特别的，如果 $\frac{x}{2}$ 是奇数，那么 $\frac{\frac{x}{2}-1}{2}$ 不是 $z$ 的转移点，那么 $z$ 会缺一个转移点 $z-1$，但由于 $\mathrm{SG}(\frac{\frac{x}{2}-1}{2})=\mathrm{SG}(z-1)$，因此不影响）。 因此 $x\bmod 2$ 时结论成立。

综上所述，结论成立。

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const int N = 1e2 + 5;

int n;

LL SG(LL a) {
    while (a & 1) {
        a = ((a - 1) >> 1);
    }
    return (a >> 1);
}

void solve() {
    cin >> n;
    LL a, sum = 0;
    for (int i = 1; i <= n; i++) {
        cin >> a;
        sum ^= SG(a);
    }
    cout << (sum ? "YES\n" : "NO\n");
}

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

    int T;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}