1. 从一道蓝桥杯算法题看“DOTA”中的博弈与策略最近在整理蓝桥杯的历年算法训练题时又翻到了这道编号为ALGO-529标题叫“DOTA”的题目。说实话第一次看到这个标题作为一个老玩家心里还咯噔了一下以为要模拟什么复杂的英雄对战或者装备合成。但仔细读完题面才发现这又是一道典型的“披着游戏外衣”的算法题内核其实是经典的博弈论问题。这道题在蓝桥杯的练习体系中属于“无序阶段”的解题训练意味着它考察的不是对某种特定数据结构的熟练度而是对问题本质的抽象能力和策略分析能力。今天我就结合自己刷题和打游戏当然是合理规划时间的前提下的双重经验来拆解一下这道题聊聊它背后的博弈思想以及如何用C语言实现一个高效的解法。题目本身描述并不复杂它模拟了一个简化版的DOTA对战场景有两个英雄每个英雄有初始生命值他们轮流进行攻击每次攻击可以造成固定的伤害。但攻击有一个“冷却时间”的设定即一次攻击后需要等待若干回合才能进行下一次攻击。英雄可以选择“攻击”或者“等待”即跳过回合以缩短冷却。目标是在自己存活的前提下击败对方。这听起来是不是有点像我们平时对线时的换血和技能CD计算只不过题目把它极端抽象和简化了。我们需要写程序来判断在双方都采取最优策略的情况下先手英雄是否有必胜策略。这立刻让我想到了博弈论中的“有向图游戏”或者“公平组合游戏”的一些模型比如SG函数。但仔细分析后发现它更贴近于一种“状态搜索”问题因为英雄的生命值和技能冷却时间构成了一个有限的状态空间。我们可以用动态规划或者记忆化搜索来遍历所有可能的状态从而判断某个状态下当前操作者的胜负情况。这对于算法新手来说是一个绝佳的练习能让你深刻理解“状态”、“决策”和“最优子结构”这些概念。下面我们就一步步来构建这个问题的解决方案。2. 问题建模将游戏规则转化为状态参数解决任何算法问题的第一步都是彻底理解题意并将其转化为可计算的模型。我们先把题目中模糊的“DOTA”背景剥离提取出精确的数学规则。假设两个英雄分别为A先手和B后手。每个英雄有三个关键属性生命值HP_A, HP_B当生命值小于等于0时英雄死亡。攻击力Damage每次攻击造成的固定伤害值。冷却时间Cooldown发动一次攻击后需要等待的回合数。在冷却期间该英雄无法攻击。每个回合当前行动的英雄必须从以下两个动作中选择一个执行攻击Attack如果攻击不在冷却中则可以攻击对方使对方生命值减少Damage点。然后自身进入冷却状态持续Cooldown个回合。等待Wait不进行攻击。如果自身正处于冷却状态则冷却回合数减1。游戏立即结束的条件是某一方英雄生命值降至0或以下。轮到某英雄行动时如果对方已经死亡则该英雄获胜。我们需要判断的是给定初始生命值、攻击力和冷却时间在双方都绝对聪明总是采取最优策略的情况下先手英雄A是否有必胜策略。注意是“有必胜策略”而不是“一定赢”。这意味着存在一种行动序列无论后手英雄B如何应对A都能确保获胜。如何建模呢关键在于定义“状态”。一个状态需要能唯一描述游戏在某一时刻的所有信息足以推导后续发展。对于这个游戏一个状态可以用一个五元组来表示(hp_A, hp_B, cool_A, cool_B, turn)其中hp_A,hp_B是双方当前生命值。cool_A,cool_B是双方剩余的冷却时间。cool_X 0表示英雄X可以攻击。turn表示当前轮到谁行动可以是A或B。初始状态是(HP_A, HP_B, 0, 0, A)。我们的目标就是判断在这个初始状态下选手A是否是“必胜”的。这个状态空间是有限的因为生命值有下限0即结束冷却时间也是循环的。理论上我们可以枚举所有可能的状态。但直接枚举可能状态数会很多比如生命值上限如果为100冷却时间上限为5状态数大约是100 * 100 * 6 * 6 * 2 ≈ 72万。对于算法竞赛来说这个规模是可以通过记忆化搜索Memoization或动态规划DP来处理的。3. 核心算法记忆化搜索与必胜态分析有了状态定义接下来就是设计算法来计算每个状态的胜负属性。这是一个典型的“零和博弈”问题我们可以使用“必胜态Winning State”和“必败态Losing State”的概念来分析。定义必胜态N-position当前玩家轮到行动的玩家有策略可以迫使对手最终失败无论对手如何应对。必败态P-position当前玩家无论怎么走对手都存在一种应对策略可以迫使当前玩家最终失败。我们的目标就是判断初始状态S0是否是先手玩家A的必胜态。如何推导呢这需要从终局状态倒推。终局状态如果轮到玩家X行动时对方生命值hp_opponent 0那么当前玩家X立即获胜。这个状态对X而言是必胜态。注意这里不需要行动因为游戏已经结束。在实现时我们可以在搜索中优先检查这个条件。状态转移对于非终局状态S当前玩家有若干合法的移动攻击或等待。玩家会选择一个移动使游戏进入一个新的状态S。S的胜负属性是从对手视角看的。如果存在至少一种移动能够使得移动后的状态S是对手的必败态那么当前玩家就可以选择这个移动将必败态留给对手。因此状态S就是当前玩家的必胜态。反之如果所有可能的移动都导致移动后的状态S是对手的必胜态那么无论当前玩家怎么走都会把必胜态送给对手。因此状态S就是当前玩家的必败态。这形成了一个递归定义。我们可以用深度优先搜索DFS来遍历状态空间并用一个记忆化数组或哈希表来存储已经计算过的状态的胜负结果避免重复计算这就是记忆化搜索。具体到本题的状态(hp_A, hp_B, cool_A, cool_B, turn)当前玩家的合法操作有攻击如果cool_self 0则可以执行。新状态hp_opponent - damagecool_self变为cooldown完整的冷却值cool_opponent保持不变但轮到对手行动时会先减1这里需要仔细。turn切换为对手。需要检查攻击后对方生命值是否0如果是则当前玩家直接获胜。等待总是可以执行。新状态cool_self max(0, cool_self - 1)cool_opponent保持不变。turn切换为对手。注意即使冷却为0也可以选择等待这是一种策略性拖延。这里有一个关键细节冷却时间的更新时机。题目描述是“发动攻击后进入冷却”而“等待”会减少冷却。但在状态表示中cool_A和cool_B表示的是“剩余冷却回合数”。当轮到A行动时cool_A表示A在本回合行动前剩余的冷却。如果A选择攻击攻击后A进入冷却所以下一回合轮到B时A的冷却值应该是cooldown。如果A选择等待那么A的冷却值减1至少为0然后轮到B。轮到B时B的冷却值表示B行动前的剩余冷却B行动后才会更新。这个顺序一定要在状态转移时编码正确否则会得到错误结果。基于以上分析我们可以设计递归函数int dfs(hp_A, hp_B, cool_A, cool_B, turn)返回值表示当前状态下当前玩家turn所指是否必胜1必胜0必败。伪代码如下// 全局记忆化数组 memo[HP_A_MAX][HP_B_MAX][COOL_MAX][COOL_MAX][2] int dfs(int hp_A, int hp_B, int cool_A, int cool_B, int turn) { // 1. 边界条件游戏是否已经结束 if (turn A_TURN) { if (hp_B 0) return 1; // A行动时B已死A胜 if (hp_A 0) return 0; // A已死不会走到这里但为安全起见 } else { if (hp_A 0) return 1; // B行动时A已死B胜注意函数返回当前玩家胜负此时当前玩家是B if (hp_B 0) return 0; } // 2. 查询记忆化数组 if (memo[hp_A][hp_B][cool_A][cool_B][turn] ! -1) { return memo[...]; } int can_win 0; // 初始假设无法必胜 int my_cool (turn A_TURN) ? cool_A : cool_B; int opp_cool (turn A_TURN) ? cool_B : cool_A; int *my_hp_ptr (turn A_TURN) ? hp_A : hp_B; int *opp_hp_ptr (turn A_TURN) ? hp_B : hp_A; // 3. 尝试所有合法操作 // 操作1: 等待 int new_my_cool (my_cool 0) ? my_cool - 1 : 0; int next_turn (turn A_TURN) ? B_TURN : A_TURN; int next_cool_A (turn A_TURN) ? new_my_cool : cool_A; int next_cool_B (turn A_TURN) ? cool_B : new_my_cool; // 递归进入对手回合如果对手必败则当前操作能导致当前玩家必胜 int result_wait dfs(hp_A, hp_B, next_cool_A, next_cool_B, next_turn); // dfs返回的是 next_turn 玩家的胜负我们需要取反 if (result_wait 0) { // 对手必败 can_win 1; } // 操作2: 攻击 (如果冷却为0) if (my_cool 0 !can_win) { // 如果等待已经能赢攻击可以不用尝试剪枝 int new_opp_hp *opp_hp_ptr - DAMAGE; // 检查攻击是否直接致死 if (new_opp_hp 0) { can_win 1; // 直接获胜 } else { // 更新状态对方减血自身进入冷却对方冷却不变回合切换 int next_cool_A_attack, next_cool_B_attack; if (turn A_TURN) { next_cool_A_attack COOLDOWN; // A攻击后进入冷却 next_cool_B_attack cool_B; } else { next_cool_A_attack cool_A; next_cool_B_attack COOLDOWN; // B攻击后进入冷却 } int next_hp_A (turn A_TURN) ? hp_A : new_opp_hp; int next_hp_B (turn A_TURN) ? new_opp_hp : hp_B; int result_attack dfs(next_hp_A, next_hp_B, next_cool_A_attack, next_cool_B_attack, next_turn); if (result_attack 0) { // 对手必败 can_win 1; } } } // 4. 存储并返回结果 memo[hp_A][hp_B][cool_A][cool_B][turn] can_win; return can_win; }这个递归函数是算法的核心。初始调用dfs(HP_A, HP_B, 0, 0, A_TURN)如果返回1则先手A有必胜策略。4. 实现细节与C语言代码实战理论清晰后我们来讨论C语言实现的细节。蓝桥杯的环境通常对时间和内存有明确限制例如本题可能1s128MB因此我们需要对上述算法进行优化和精心的实现。4.1 状态压缩与数组维度我们的状态是五维的(hp_A, hp_B, cool_A, cool_B, turn)。生命值hp的范围需要根据题目输入确定假设最大为N。冷却时间cool的范围是0 ~ Cooldown因为冷却从Cooldown开始递减到0。turn是2种。 因此记忆化数组memo的大小大约是N * N * (C1) * (C1) * 2。如果N100C5就是100*100*6*6*2 720,000个int大约2.7MB在内存限制内。但如果N更大比如200就可能达到约11MB需要留意。我们可以使用char类型来存储胜负只有0/1并初始化为-1表示未计算这样可以节省空间。4.2 递归深度与栈溢出递归深度最大可能等于游戏的总回合数在最坏情况下双方一直等待可能达到(hp_A hp_B) * something有栈溢出风险。虽然本题状态空间有限递归深度通常不会极端深但为了稳健我们可以考虑使用迭代式的动态规划DP或BFS。不过记忆化搜索的代码更直观易懂。在竞赛中如果担心栈溢出可以尝试增大栈空间但蓝桥杯环境通常不允许或者改用DP。这里我们先按记忆化搜索实现。4.3 输入与参数处理题目输入通常会给出A生命值B生命值攻击力冷却时间。我们需要将这些作为全局常量或函数参数。注意攻击力和冷却时间对双方是相同的这是题目简化条件。4.4 代码实现示例下面是一个完整的、可运行的C语言实现框架。请注意为了清晰我假设生命值上限为100冷却时间上限为10实际应根据题目要求调整。#include stdio.h #include string.h #define MAX_HP 105 // 稍大一些防止越界 #define MAX_COOL 11 #define A_TURN 0 #define B_TURN 1 // 全局变量存储输入参数 int HP_A, HP_B, DAMAGE, COOLDOWN; // 记忆化数组-1:未计算0:必败1:必胜 char memo[MAX_HP][MAX_HP][MAX_COOL][MAX_COOL][2]; // 初始化记忆化数组 void init_memo() { memset(memo, -1, sizeof(memo)); } // 记忆化搜索函数 // 返回在当前状态下当前行动方turn是否必胜1胜0败 int dfs(int hp_a, int hp_b, int cool_a, int cool_b, int turn) { // 边界条件有人生命值0游戏结束 // 注意轮到谁行动时发现对方死了谁就赢了 if (turn A_TURN) { if (hp_b 0) return 1; // A行动时B已死A赢 if (hp_a 0) return 0; // A已死理论上不会走到这步 } else { // B_TURN if (hp_a 0) return 1; // B行动时A已死B赢 if (hp_b 0) return 0; } // 查询记忆化 if (memo[hp_a][hp_b][cool_a][cool_b][turn] ! -1) { return memo[hp_a][hp_b][cool_a][cool_b][turn]; } int can_win 0; // 假设当前玩家无法必胜 int my_cool (turn A_TURN) ? cool_a : cool_b; int opp_cool (turn A_TURN) ? cool_b : cool_a; // 操作1: 等待 (总是可行的) int new_my_cool_wait (my_cool 0) ? my_cool - 1 : 0; int next_turn (turn A_TURN) ? B_TURN : A_TURN; int next_cool_a_wait, next_cool_b_wait; if (turn A_TURN) { next_cool_a_wait new_my_cool_wait; next_cool_b_wait opp_cool; } else { next_cool_a_wait opp_cool; next_cool_b_wait new_my_cool_wait; } // 递归如果对手在下一状态必败则当前操作能导致我方必胜 int res_wait dfs(hp_a, hp_b, next_cool_a_wait, next_cool_b_wait, next_turn); // res_wait 表示下一状态对手行动下对手的胜负。若对手必败(res_wait0)则当前状态我方必胜。 if (res_wait 0) { can_win 1; } // 操作2: 攻击 (仅当自身冷却为0时可行) if (my_cool 0 !can_win) { // 如果等待已经能赢攻击可以剪枝 // 计算攻击后的生命值 int new_hp_a hp_a; int new_hp_b hp_b; if (turn A_TURN) { new_hp_b hp_b - DAMAGE; } else { new_hp_a hp_a - DAMAGE; } // 检查攻击是否直接杀死对方 if ((turn A_TURN new_hp_b 0) || (turn B_TURN new_hp_a 0)) { can_win 1; } else { // 更新冷却攻击方进入完整冷却对方冷却不变 int next_cool_a_attack, next_cool_b_attack; if (turn A_TURN) { next_cool_a_attack COOLDOWN; next_cool_b_attack opp_cool; } else { next_cool_a_attack opp_cool; next_cool_b_attack COOLDOWN; } int res_attack dfs(new_hp_a, new_hp_b, next_cool_a_attack, next_cool_b_attack, next_turn); if (res_attack 0) { can_win 1; } } } // 存储结果并返回 memo[hp_a][hp_b][cool_a][cool_b][turn] can_win; return can_win; } int main() { // 假设输入格式为HP_A HP_B DAMAGE COOLDOWN // 例如30 25 5 2 scanf(%d %d %d %d, HP_A, HP_B, DAMAGE, COOLDOWN); init_memo(); int result dfs(HP_A, HP_B, 0, 0, A_TURN); // 初始状态A先手双方无冷却 if (result 1) { printf(A\n); // 或者输出1根据题目要求 } else { printf(B\n); // 或者输出0 } return 0; }4.5 重要注意事项与调试技巧数组越界这是最易犯的错误。生命值hp_a和hp_b在递归中可能减少到负数。在访问memo数组前务必先进行边界判断生命值0直接返回胜负。同时数组大小MAX_HP应大于等于最大可能生命值1。如果攻击后生命值变为负数在存储到记忆化数组时负索引会导致崩溃。安全的做法是在递归入口处就判断生命值如果0直接返回结果不再访问memo。状态对称性剪枝本题中除了先手后手区别双方属性完全一样。理论上状态(hp_a, hp_b, cool_a, cool_b, A)和(hp_b, hp_a, cool_b, cool_a, B)可能存在对称关系可以利用这一点减少计算。但实现起来稍复杂在数据范围不大时直接记忆化搜索已足够。理解“必胜”与“必败”递归函数返回的是当前玩家的胜负。因此在得到子状态对手回合的结果res_sub后判断逻辑是如果res_sub 0对手在子状态必败那么当前玩家在当前状态就是必胜的。这个取反关系一定要清晰。测试用例自己构造一些简单用例测试。例如A生命1B生命1攻击力1冷却0。A先手攻击直接获胜应返回A胜。A生命2B生命1攻击力1冷却1。A攻击后进入冷却B攻击AA死。但A可以先等待一回合冷却仍为0然后攻击B获胜。这是一个需要“等待”策略的例子。A生命5B生命5攻击力2冷却2。这是一个更复杂的需要计算的状态。5. 从算法题到实战策略的思考解完这道题我们不妨跳出来想想它和真实的DOTA游戏有什么关联虽然题目极度简化但它确实捕捉到了MOBA游戏中的一个核心策略点技能管理与时机选择。在DOTA中英雄的技能有冷却时间CD和魔法消耗Mana。对线期你需要计算自己和对手的关键技能CD。比如敌方英雄刚用掉了眩晕技能你有大约10秒的安全输出时间。这就是“冷却”概念的体现。题目中的“等待”操作类似于你在技能CD时走位拉扯、补刀而不是无意义地冲上去平A。更深一层这道题是一个完全信息博弈双方都知道所有状态并且是零和一胜一负。现实中的DOTA则是不完全信息博弈有战争迷雾不知道对方确切位置和装备并且策略维度多得多装备选择、团战时机、地图控制等。但完全信息博弈是研究复杂博弈的基础。AlphaGo等AI也是先攻克了完全信息的围棋再向不完全信息的《星际争霸》等游戏迈进。对于算法学习者来说这道题的价值在于建立博弈思维理解“必胜态”和“必败态”的递推关系这是解决许多博弈类问题如尼姆游戏、SG函数问题的基础。掌握状态空间搜索如何定义状态如何设计状态转移如何使用记忆化搜索避免重复计算。这是动态规划和搜索算法的核心。锻炼严谨的编码能力状态参数多边界条件复杂非常考验对细节的把控能力。一个下标错误或条件顺序错误就可能导致全盘皆输。在竞赛中遇到此类题目我的经验是先画状态转移图对于简单的初始值手工推导几步验证自己对规则的理解。明确递归函数定义写在注释里特别是返回值代表谁当前玩家的胜负。优先处理边界条件在递归函数开头就把所有导致游戏结束的情况判断并返回。小心处理负数索引对于可能小于0的参数在访问数组前进行判断或偏移处理。最后虽然这道题叫“DOTA”但它的内核是纯粹的算法与博弈。通过解决它我们不仅练习了编程更训练了一种将复杂现实问题抽象为可计算模型的思维能力。这种能力无论是在后续学习更复杂的算法还是在解决工程实际问题时都是无比宝贵的。下次再看到这类“标题党”算法题不妨会心一笑然后专注于挖掘它背后真正的算法考点。