639 字
2 分钟
博弈论
简单博弈论
概念详解
博弈论研究”两人轮流操作、信息完全公开、无法行动者输”的公平组合游戏。入门需要掌握两个核心工具：
1. Nim 游戏与异或和
规则： 有 n 堆石子，两人轮流从任意一堆中取走任意个（至少 1 个），取走最后一个的人获胜。
必胜/必败判定（Bouton 定理）： 设每堆石子数为 a₁, a₂, …, aₙ，令
X = a₁ ⊕ a₂ ⊕ … ⊕ aₙ（异或和）
- X ≠ 0：先手必胜（存在一种取法把 X 变成 0）；
- X = 0：先手必败（无论怎么取，都会把 X 变成非 0）。
为什么？ 若 X ≠ 0，设 X 的最高位为第 k 位，则至少有一堆 aᵢ 的第 k 位是 1；从这一堆取走 aᵢ - (aᵢ ⊕ X) 个（这是一个正数且小于 aᵢ），新的异或和就变成 0。若 X = 0，任意取法都会使某个 aᵢ 变化，异或和必然不再是 0。于是”X = 0”的状态只能转移到”X ≠ 0”，而”X ≠ 0”总能转移回”X = 0”；终局（全 0）的 X = 0，由此归纳出上面的结论。
2. SG 函数与有向图游戏
把每一个局面看成一个节点，一次合法操作相当于沿着有向边走到另一个局面。定义
SG(x) = mex{ SG(y) | x 能一步走到 y }
其中 mex 是”最小未出现的非负整数”。终态（无路可走）SG = 0。
- 单个游戏： SG(x) = 0 必败，SG(x) > 0 必胜；
- 多个独立游戏的和： 总 SG = 各子游戏 SG 的异或和，异或为 0 必败、非 0 必胜。Nim 游戏正是”每堆石子 SG = 石子数”的特例。
例题：Nim 游戏
题意
给定 堆石子，两位玩家轮流操作，每次可以从任意一堆中拿走任意数量的石子（至少 1 个，可以拿完）。 拿走最后一个石子的人获胜。问先手是否必胜。
输入格式
第一行包含整数 。
第二行包含 个整数，其中第 个整数表示第 堆石子的数量 。输出格式
如果先手必胜，则输出
Yes；否则输出No。数据范围
import java.io.*;import java.util.StringTokenizer;
public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); StringTokenizer st = new StringTokenizer(br.readLine()); int res = 0; while (n-- > 0) { res ^= Integer.parseInt(st.nextToken()); // 求所有堆的异或和 } System.out.println(res != 0 ? "Yes" : "No"); // 异或和不为 0 → 先手必胜 }} 分享
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时
相关文章 智能推荐