[蓝桥杯]取球博弈

取球博弈

题目描述

两个人玩取球的游戏。

一共有 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计算所有可能状态的最优策略结果。

算法步骤

1. ​​状态定义​​：

   • dp[s][a][b][turn]：剩余球数s，先手奇偶性a（0偶1奇），后手奇偶性b，当前玩家turn（0先手/1后手）
   • 值：1（先手赢）/0（平）/-1（先手输）

2. ​​状态转移​​：

   • ​​先手操作​​（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）

3. ​​边界处理​​：

   • 当s=0：根据奇偶性直接返回结果
   • 当s<min_take：无法取球，直接结算

4. ​​结果输出​​：

   • 对每局初始球数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;
}

代码解析

1. ​​状态压缩​​：

   • 使用a/b的0/1表示奇偶性，将球数状态压缩为4个维度
   • dp[s][a][b][turn]存储当前状态的最优结果

2. ​​核心转移逻辑​​：

   • ​​先手策略​​（L42-55）：优先选择使后手必输的操作（返回1），次选平局
   • ​​后手策略​​（L56-69）：优先选择使先手必输的操作（返回-1），次选平局
   • ​​奇偶更新​​：new_a = a ^ (k & 1)（异或等效模2加法）

3. ​​边界处理​​：

   • s=0时直接根据奇偶性判定（L24-28）
   • s<min_take时无法操作，直接结算（L35-39）

4. ​​结果查询​​：

   • 初始状态：dp[x][0][0][0]（双方0球，先手操作）
   • 结果映射：1→+/0→0/-1→-

实例验证

输入：1 2 3 + 1 2 3 4 5

​​输出​​：+ 0 + 0 -

​​状态分析​​：

1. ​​球数1​​：先手取1→剩0球，先手奇数(1)后手偶数(0)→先手赢+
2. ​​球数2​​：
   • 取1：转状态(1,1,0,1)→后手取1→(0,1,1,0)→平局
   • 取2：转状态(0,0,0,1)→平局
   • 最优平局0
3. ​​球数3​​：取3→(0,1,0,1)→先手赢+
4. ​​球数4​​：
   • 取1：转(3,1,0,1)→后手取3→(0,1,1,0)→平局
   • 取2/3：后手可迫使平局
   • 最优平局0
5. ​​球数5​​：
   • 所有走法后手可迫使先手输-

输入：1 4 5 + 10 11 12 13 15

​​输出​​：0 - 0 + +（符合样例）

注意事项

1. ​​奇偶性更新​​：

   • 使用异或运算a^(k&1)等效模2加法
   • 例：奇(1)+奇(1)→偶(0)：1^1=0

2. ​​不可操作状态​​：

   • 当s<min_take时直接结算
   • 需单独处理避免越界

3. ​​DP初始化​​：

   • s=0时turn维度无意义，但需完整初始化
   • 使用UNCALC标记未计算状态

4. ​​策略优先级​​：

   • 先手：赢→平→输（找到赢立即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	操作去重逻辑

优化建议

1. ​​循环优化​​：

   // 预处理合法操作（去重排序）
   sort(takes.begin(), takes.end());
   takes.erase(unique(takes.begin(), takes.end()), takes.end());

2. ​​维度压缩​​：

   • 奇偶状态仅需2位，可用位运算压缩为单整数

   int state = (a << 2) | (b << 1) | turn;

3. ​​记忆化搜索​​：

   // 替代迭代DP，减少无效计算
   int dfs(int s, int a, int b, int turn) {if (dp[s][a][b][turn] != UNCALC) return dp[s][a][b][turn];// ...递归计算
   }

4. ​​剪枝策略​​：

   • 当找到必胜/必杀策略时立即跳出循环
   • 倒序排序取法，优先尝试大数加速命中