题解 | #小A取石子#

本题是经典 Nim 游戏 的变种。

核心思路

核心观察

本题基于经典 Nim 游戏，其胜负由所有石子堆数量的 异或和（XOR sum） 决定：

若异或和 $\neq 0$ ，先手必胜；
若异或和 $= 0$ ，先手必败。

小A在游戏开始前可执行一次特殊操作：从某一堆中恰好拿走 $k$ 个石子 注意不是 $[0-k]$ （需满足该堆 $\geq k$ ），之后正常开始游戏（小A仍为先手）。

关键数学性质如下：

当原始异或和为 0 时，若存在某堆 $a_i \geq k$ 且 $k > 0$ ，则操作后的新异或和为
$a_i \oplus (a_i - k)$
由于 $k > 0$ ，必有 $a_i \neq a_i - k$ ，因此该值 $\neq 0$ 。
即：只要能合法执行一次 $k$ 操作（ $k > 0$ 且有堆足够大），小A就能将必败态转为必胜态。

此外：

若 $k = 0$ ，相当于无法改变局面；
若所有堆均 $< k$ ，也无法操作。

算法步骤

读入整数 $n$ （堆数）和 $k$ （可提前拿走的石子数）。
读入 $n$ 个石子堆数量 $a_0, a_1, \dots, a_{n-1}$ ，同时计算：
- 总异或和 total = a[0] ^ a[1] ^ ... ^ a[n-1]
- 最大堆大小 mx = max(a[i])
判断胜负：
- 若 total != 0：小A无需操作即可获胜 → 输出 "YES"；
- 否则（total == 0）：
  - 若 k == 0 或 mx < k：无法有效操作 → 输出 "NO"；
  - 否则：存在合法操作使新局面异或和 $\neq 0$ → 输出 "YES"。

正确性分析

情况一：原始异或和 $\neq 0$
小A作为先手，在标准 Nim 游戏中已有必胜策略，无需使用预操作。故输出 "YES" 正确。
情况二：原始异或和 $= 0$
- 若 $k = 0$ ：小A不能改变任何堆，局面不变，仍为必败态 → "NO" 正确。
- 若 $\max(a) < k$ ：无一堆满足 $a_i \geq k$ ，无法操作 → "NO" 正确。
- 若 $\max(a) \geq k$ 且 $k > 0$ ：
  设选中堆为 $a_i$ ，操作后该堆变为 $a_i - k$ 。
  新异或和为 $a_i \oplus (a_i - k) \neq 0$ （因 $k > 0$ ），
  小A作为新局先手，面对非零异或和，必胜 → "YES" 正确。

条件	结果	说明
$k = 0$	$X' = 0$	无法改变局面，仍必败
$\forall i,\ a_i < k$	操作非法	无合法操作，必败
$\exists i,\ a_i \geq k > 0$	$X' \neq 0$	必胜

综上，算法覆盖所有情况，逻辑严密。

复杂度分析

时间复杂度： $O(n)$
仅需一次遍历计算异或和与最大值。
空间复杂度： $O(n)$
存储石子堆数组；若边读边处理，可优化至 $O(1)$ 额外空间。

数学逻辑推导

==命题 A==（平衡态不可维持）若 $X = 0$ ，则任何合法操作都会使新异或和 $X' \neq 0$ 。

==命题 B==（非平衡态可修复）若 $X \neq 0$ ，则存在至少一个合法操作，使新异或和 $X' = 0$ 。

证明命题 A： $X = 0 \Rightarrow$ 任何操作导致 $X' \neq 0$

设当前 $X = a_1 \oplus a_2 \oplus \cdots \oplus a_n = 0$ 。

玩家必须选择某堆 $i$ ，将其从 $a_i$ 改为 $a_i'$ ，其中 $0 \leq a_i' < a_i$ （因至少取 1 个）。

新异或和为：

\begin{aligned} X' &= a_1 \oplus \cdots \oplus a_i' \oplus \cdots \oplus a_n \\ &= (a_1 \oplus \cdots \oplus a_n) \oplus a_i \oplus a_i' \\ &= X \oplus a_i \oplus a_i' \\ &= 0 \oplus a_i \oplus a_i' = a_i \oplus a_i' \end{aligned}

由于 $a_i' < a_i$ ，必有 $a_i \neq a_i'$ ，因此：

a_i \oplus a_i' \neq 0 \quad \Rightarrow \quad X' \neq 0

==命题 A 得证==：从 $X=0$ 出发，任何操作都会破坏平衡。

证明命题 B： $X \neq 0 \Rightarrow$ 存在操作使 $X' = 0$

设当前 $X = a_1 \oplus \cdots \oplus a_n \neq 0$ 。

令 $k$ 为 $X$ 的最高位 1 的位置（例如 $X = 6 = 110_2$ ，则 $k = 2$ ）。

因为 $X$ 的第 $k$ 位为 1，说明有奇数个堆在第 $k$ 位为 1。
因此，至少存在一个堆 $a_i$ 满足其第 $k$ 位为 1。

对这个堆 $a_i$ ，定义：

a_i' = a_i \oplus X

我们验证：

$a_i' < a_i$ （操作合法）
- 因为 $X$ 的最高位是 $k$ ，且 $a_i$ 的第 $k$ 位为 1，
  所以 $a_i \oplus X$ 会将 $a_i$ 的第 $k$ 位变为 0，而更高位不变，
  故 $a_i' < a_i$ 。
新异或和为 0 $X' = X \oplus a_i \oplus a_i' = X \oplus a_i \oplus (a_i \oplus X) = 0$

命题 B 得证：从 $X \neq 0$ 出发，总能一步归零。

归纳论证： $X = 0$ 是必败态

基础：终止状态 $(0,\dots,0)$ 满足 $X=0$ ，且当前玩家输。
归纳：
- 若当前 $X = 0$ ，由命题 A，玩家只能转移到 $X' \neq 0$
- 对手面对 $X' \neq 0$ ，由命题 B，总能回到 $X'' = 0$
- 如此循环，最终当前玩家将面对 $(0,\dots,0)$ 而输

因此，所有 $X = 0$ 的状态都是必败态，
而 $X \neq 0$ 的状态都是必胜态。

在标准 Nim 游戏中：

若初始异或和 $X = 0$ ，先手必败，后手必胜；

若初始异或和 $X \neq 0$ ，先手必胜。

代码

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

int main() {
    int n,k;cin>>n>>k;
    vector<int>v(n);
    int total=0,mx=0;
    for(int i=0;i<n;i++){
        cin>>v[i];
        total^=v[i];//总异或值
        mx=max(mx,v[i]);//堆里最大石子数量
    }
    if(total!=0){cout<<"YES";return 0;}
    if(mx<k)cout<<"NO";
    else if(k!=0)cout<<"YES";
    else cout<<"NO";

}

题解 | #小A取石子#

核心思路

核心观察

算法步骤

正确性分析

复杂度分析

数学逻辑推导

证明命题 A： 任何操作导致

==命题 A 得证==：从 出发，任何操作都会破坏平衡。

证明命题 B： 存在操作使

命题 B 得证：从 出发，总能一步归零。

归纳论证： 是必败态