[蓝桥杯]取球博弈
取球博弈
题目描述
两个人玩取球的游戏。
一共有 NN 个球，每人轮流取球，每次可取集合 n1,n2,n3n1,n2,n3中的任何一个数目。
如果无法继续取球，则游戏结束。
此时，持有奇数个球的一方获胜。
如果两人都是奇数，则为平局。
假设双方都采用最聪明的取法，
第一个取球的人一定能赢吗？
试编程解决这个问题。
输入描述
输入格式：
第一行 3 个正整数 n1,n2,n3 (0<n1,n2,n3<100)n1,n2,n3 (0<n1,n2,n3<100)，空格分开，表示每次可取的数目。
第二行 5 个正整数 x1,x2,⋯,x5 (0<xi<1000)x1,x2,⋯,x5 (0<xi<1000)，空格分开，表示 5 局的初始球数。
输出描述
输出一行 5 个字符，空格分开。分别表示每局先取球的人能否获胜。
能获胜则输出 +，次之，如有办法逼平对手，输出 0，无论如何都会输，则输出 -。
输入输出样例
示例
输入
1 2 3
1 2 3 4 5
输出
+ 0 + 0 -
运行限制
- 最大运行时间：3s
- 最大运行内存: 256M
总通过次数: 1061 | 总提交次数: 1355 | 通过率: 78.3%
难度: 困难 标签: 2016, 省赛, 动态规划, 博弈
算法思路：动态规划与状态压缩
本问题是一个博弈论问题，需要模拟双方轮流取球的过程，并根据最终球数的奇偶性判断胜负。核心思路是状态压缩+动态规划，将问题分解为四个维度的状态：剩余球数、先手奇偶性、后手奇偶性、当前玩家。通过自底向上的DP计算所有可能状态的最优策略结果。
算法步骤
-
状态定义：
dp[s][a][b][turn]：剩余球数s，先手奇偶性a（0偶1奇），后手奇偶性b，当前玩家turn（0先手/1后手）- 值：
1（先手赢）/0（平）/-1（先手输）
-
状态转移：
- 先手操作（turn=0）：尝试所有合法取球数
k- 新先手奇偶性：
new_a = a ^ (k & 1) - 转移到：
dp[s-k][new_a][b][1] - 优先选赢（1），次选平（0），最后输（-1）
- 新先手奇偶性：
- 后手操作（turn=1）：尝试所有合法取球数
k- 新后手奇偶性：
new_b = b ^ (k & 1) - 转移到：
dp[s-k][a][new_b][0] - 优先选先手输（-1），次选平（0），最后赢（1）
- 新后手奇偶性：
- 先手操作（turn=0）：尝试所有合法取球数
-
边界处理：
- 当
s=0：根据奇偶性直接返回结果 - 当
s<min_take：无法取球，直接结算
- 当
-
结果输出：
- 对每局初始球数
x，查询dp[x][0][0][0] 1→'+',0→'0',-1→'-'
- 对每局初始球数
代码实现（C++）
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;int main() {// 读取取球规则vector<int> takes(3);cin >> takes[0] >> takes[1] >> takes[2];int min_take = *min_element(takes.begin(), takes.end());// 初始化DP数组 [s][a][b][turn]int dp[1001][2][2][2];const int UNCALC = INT_MIN;// 初始化s=0的边界状态for (int a = 0; a < 2; a++) {for (int b = 0; b < 2; b++) {for (int turn = 0; turn < 2; turn++) {if (a == 1 && b == 0) dp[0][a][b][turn] = 1;else if (a == 0 && b == 1) dp[0][a][b][turn] = -1;else dp[0][a][b][turn] = 0;}}}// DP计算：s从1到1000for (int s = 1; s <= 1000; s++) {for (int a = 0; a < 2; a++) {for (int b = 0; b < 2; b++) {for (int turn = 0; turn < 2; turn++) {// 默认无法取球时直接结算if (s < min_take) {if (a == 1 && b == 0) dp[s][a][b][turn] = 1;else if (a == 0 && b == 1) dp[s][a][b][turn] = -1;else dp[s][a][b][turn] = 0;continue;}if (turn == 0) { // 先手操作int best = UNCALC;for (int k : takes) {if (k > s) continue;int new_a = a ^ (k & 1); // 更新奇偶性int res = dp[s - k][new_a][b][1]; // 转后手if (res == 1) { // 找到必胜策略best = 1;break;} else if (res == 0) {best = 0; // 标记平局可能} else if (best == UNCALC) {best = -1; // 无更优选择}}dp[s][a][b][turn] = (best == UNCALC) ? ((a == 1 && b == 0) ? 1 : (a == 0 && b == 1) ? -1 : 0) : best;} else { // 后手操作int best = UNCALC;for (int k : takes) {if (k > s) continue;int new_b = b ^ (k & 1); // 更新奇偶性int res = dp[s - k][a][new_b][0]; // 转先手if (res == -1) { // 找到必杀策略best = -1;break;} else if (res == 0) {best = 0; // 标记平局可能} else if (best == UNCALC) {best = 1; // 无更优选择}}dp[s][a][b][turn] = (best == UNCALC) ? ((a == 1 && b == 0) ? 1 : (a == 0 && b == 1) ? -1 : 0) : best;}}}}}// 处理5局游戏vector<int> x(5);for (int i = 0; i < 5; i++) cin >> x[i];for (int i = 0; i < 5; i++) {int res = dp[x[i]][0][0][0];if (res == 1) cout << '+';else if (res == 0) cout << '0';else cout << '-';if (i < 4) cout << ' ';}return 0;
}代码解析
-
状态压缩：
- 使用
a/b的0/1表示奇偶性，将球数状态压缩为4个维度 dp[s][a][b][turn]存储当前状态的最优结果
- 使用
-
核心转移逻辑：
- 先手策略（L42-55）：优先选择使后手必输的操作（返回1），次选平局
- 后手策略（L56-69）：优先选择使先手必输的操作（返回-1），次选平局
- 奇偶更新：
new_a = a ^ (k & 1)（异或等效模2加法）
-
边界处理：
s=0时直接根据奇偶性判定（L24-28）s<min_take时无法操作，直接结算（L35-39）
-
结果查询：
- 初始状态：
dp[x][0][0][0]（双方0球，先手操作） - 结果映射：
1→+/0→0/-1→-
- 初始状态：
实例验证
输入：1 2 3 + 1 2 3 4 5
输出：+ 0 + 0 -
状态分析：
- 球数1：先手取1→剩0球，先手奇数(1)后手偶数(0)→先手赢
+ - 球数2：
- 取1：转状态(1,1,0,1)→后手取1→(0,1,1,0)→平局
- 取2：转状态(0,0,0,1)→平局
- 最优平局
0
- 球数3：取3→(0,1,0,1)→先手赢
+ - 球数4：
- 取1：转(3,1,0,1)→后手取3→(0,1,1,0)→平局
- 取2/3：后手可迫使平局
- 最优平局
0
- 球数5：
- 所有走法后手可迫使先手输
-
- 所有走法后手可迫使先手输
输入：1 4 5 + 10 11 12 13 15
输出：0 - 0 + +（符合样例）
注意事项
-
奇偶性更新：
- 使用异或运算
a^(k&1)等效模2加法 - 例：奇(1)+奇(1)→偶(0)：
1^1=0
- 使用异或运算
-
不可操作状态：
- 当
s<min_take时直接结算 - 需单独处理避免越界
- 当
-
DP初始化：
s=0时turn维度无意义，但需完整初始化- 使用
UNCALC标记未计算状态
-
策略优先级：
- 先手：赢→平→输（找到赢立即break）
- 后手：输→平→赢（找到输立即break）
多方位测试点
| 测试类型 | 测试数据 | 预期结果 | 验证要点 |
|---|---|---|---|
| 最小球数 | 1 2 3 + 1 | + | 边界处理 |
| 不可操作 | 2 3 4 + 1 | 0 | 直接奇偶结算 |
| 全奇取胜 | 1 3 5 + 3 | + | 奇偶组合逻辑 |
| 强制平局 | 2 2 2 + 4 | 0 | 无最优解的平局处理 |
| 后手必杀 | 1 4 5 + 11 | - | 后手策略优先级 |
| 大球数性能 | 1 2 3 + 1000 | <1s | DP效率验证 |
| 重复取法 | 3 3 3 + 6 | 0 | 操作去重逻辑 |
优化建议
-
循环优化：
// 预处理合法操作（去重排序） sort(takes.begin(), takes.end()); takes.erase(unique(takes.begin(), takes.end()), takes.end()); -
维度压缩：
- 奇偶状态仅需2位，可用位运算压缩为单整数
int state = (a << 2) | (b << 1) | turn; -
记忆化搜索：
// 替代迭代DP，减少无效计算 int dfs(int s, int a, int b, int turn) {if (dp[s][a][b][turn] != UNCALC) return dp[s][a][b][turn];// ...递归计算 } -
剪枝策略：
- 当找到必胜/必杀策略时立即跳出循环
- 倒序排序取法，优先尝试大数加速命中