1. 从一道经典博弈题说起HDU 1079如果你在刷算法题尤其是博弈论相关的题目那么HDU 1079POJ 1082这道题大概率会出现在你的视野里。题目名字叫“Calendar Game”翻译过来就是“日历游戏”。乍一看题目描述很简单两个人轮流操作从一个给定的日期开始每次只能将日期移动到下一天或者移动到下个月的同一号如果下个月有这一天的话。谁先移动到2001年11月4日之后即2001年11月5日或更晚谁就输了。换句话说谁被迫走到这个日期之后谁就输这是一个典型的“无法移动者输”的公平组合游戏。很多朋友第一次看到这道题可能会觉得这不就是个简单的日期模拟吗甚至想直接写个BFS广度优先搜索去遍历所有可能的日期状态然后标记必胜态和必败态。理论上从1900年1月1日到2001年11月4日状态数也就几万个BFS完全可行。但问题在于题目要求的是对于输入的多个起始日期快速判断先手是否必胜。如果每个查询都重新BFS一遍在多次查询的场景下效率就太低了。这时候我们就需要引入更强大的武器记忆化搜索配合SG函数。这不仅仅是解这道题更是理解一大类博弈问题的核心思路。今天我就结合自己多次实现和教学的经验把这道题掰开揉碎了讲清楚。我们不止于AC代码更要弄明白为什么记忆化搜索在这里如此高效SG函数在这个游戏图里代表了什么如何设计一个无bug的状态表示和转移函数以及在实现过程中有哪些极易踩坑的细节。你会发现掌握了这套方法很多看似复杂的博弈题都会迎刃而解。2. 游戏规则抽象与状态建模在动手写代码之前我们必须把游戏规则彻底抽象成计算机能处理的形式。这是所有算法题的第一步也是最关键的一步建模的好坏直接决定了后续实现的复杂度。2.1 规则的形式化定义题目给出的规则可以这样严格定义状态一个具体的日期由年Year、月Month、日Day三元组(y, m, d)唯一确定。起始状态由输入给出是(y, m, d)。终止状态所有日期晚于2001年11月4日(2001, 11, 4)的状态都是终止状态。准确地说(2001, 11, 5)及以后的日期是“非法”或“失败”状态谁走到这里谁输。在博弈论中我们通常把“无法进行合法移动的状态”定义为必败态P-position。在这个游戏里当你面对一个日期它的两种移动方式都指向了终止日期之后你就无法移动了所以你处于必败态。合法移动即状态转移从当前状态(y, m, d)可以移动到两个可能的新状态移动到下一天next_day(y, m, d)。这需要正确处理月末、年末以及闰年二月的情况。移动到下个月的同一天next_month(y, m, d)。这需要判断下个月是否存在这一天。例如1月31日不能移动到2月31日因为2月没有31号。游戏的目标是双方都采取最优策略问先手玩家从给定的起始状态出发是否有必胜策略。2.2 关键建模决策日期到整数的映射日期本身是一个三元组在C/C中不适合直接作为数组下标进行记忆化。我们必须将其编码成一个唯一的整数。最直观的方法是利用日期的连续性将其转换为从某个固定起点如1900年1月1日开始的天数偏移即儒略日。但是计算儒略日需要处理闰年稍微有点繁琐。对于本题日期范围被限定在1900年1月1日到2001年11月4日总天数不超过365*102 闰年数大约3万7千多天。这个范围并不大。我们可以采用一个更“暴力”但实现简单的编码方式三维数组。定义一个全局的dp数组例如int dp[2002][13][32]。第一维是年1900-2001第二维是月1-12第三维是日1-31。这样状态(y, m, d)就直接对应数组元素dp[y][m][d]。虽然会浪费一些空间比如2月没有30、31号但空间复杂度2002*13*32 ≈ 80万对于现代计算机的内存来说完全可以接受换来的是编码和访问的极致简单。注意这里有一个非常重要的细节。数组下标从0开始而我们的年月日都是从1开始。为了保持逻辑清晰我建议让数组下标与真实的年月日数值对应即dp[2002][13][32]我们只使用[1900..2001][1..12][1..31]这个区间。初始化时可以将所有元素设置为一个未计算的标记值如-1。这样dp[y][m][d]就是状态(y, m, d)的SG值或胜负态标记。避免了y-1900这类容易出错的偏移计算。2.3 游戏图的构建有了状态表示我们可以将整个游戏看作一个有向无环图DAG。每个日期状态是一个节点。从每个节点出发最多有两条出边分别指向“下一天”和“下个月同一天”对应的节点如果目标状态合法。所有晚于2001年11月4日的节点是终结点没有出边。我们的任务就是为图中的每一个节点状态标记其胜负属性先手必胜还是必败或者计算其SG函数值。记忆化搜索的本质就是对这个DAG进行DFS遍历并缓存每个节点的计算结果避免重复计算。3. 核心武器SG函数与记忆化搜索原理为什么这道题要用SG函数直接用布尔值记录必胜/必败不就行了吗这里涉及到对博弈问题更深层次的理解。3.1 从必胜必败态到SG函数对于简单的“无法移动则输”的公平组合游戏我们通常用布尔数组win[pos]来表示状态pos是否为先手必胜态。其递推关系也叫动态规划是必败态P-position如果从该状态出发所有可能的移动都指向必胜态那么当前状态是必败态。因为无论你怎么走都让对方处于必胜局面。必胜态N-position如果从该状态出发存在至少一条移动指向必败态那么当前状态是必胜态。因为你可以选择这一步将必败局面丢给对方。这个递推关系是从后向前的。我们需要从所有已知的终结点必败态开始反向标记所有状态。对于DAG这可以通过拓扑排序的逆序DP或记忆化搜索来实现。而SG函数是这个概念的一个泛化和加强。它给每个状态赋予一个非负整数值。其定义是SG(pos) mex{ SG(next1), SG(next2), ..., SG(nextk) }其中next1, next2, ..., nextk是从状态pos出发所有可能的后继状态mex函数返回的是不属于这个集合的最小非负整数。SG函数的强大之处在于SG值为0的状态就是必败态P-positionSG值大于0的状态就是必胜态N-position。这完美对应了之前的布尔判定。对于多个独立游戏的组合即玩家每回合可以选择其中一个游戏进行一步操作其总状态的SG值等于各个子游戏SG值的异或和Nim和。这是SG定理的核心使得SG函数能解决更复杂的组合博弈问题。对于HDU 1079这道题它本身是单个游戏所以我们只需要利用“SG0即必败”这个性质就够了。使用SG函数的好处是其计算框架记忆化搜索mex具有极强的通用性学会之后可以轻松套用到其他许多博弈题目上。3.2 记忆化搜索的实现框架记忆化搜索是计算SG函数或单纯胜负态的利器尤其适用于状态转移关系明确但拓扑序不那么直观的DAG。其伪代码框架如下// 假设 dp 数组初始化为 -1表示未计算 int dfs(int y, int m, int d) { // 1. 边界条件/终止状态判断 if (is_later_than_2001_11_4(y, m, d)) { return 0; // 根据定义无法移动的状态实际是移动后的状态非法是必败态SG0 // 注意这里返回0代表“这个状态本身”是必败态。更准确地说是面对这个状态的人输了。 // 在递归中我们需要判断的是从当前状态移动后是否进入这个必败态。 } // 2. 记忆化检索 if (dp[y][m][d] ! -1) { return dp[y][m][d]; } // 3. 获取所有合法后继状态 vectorint nextStates; // 计算下一天状态 (y1, m1, d1)如果合法则加入nextStates // 计算下个月同一天状态 (y2, m2, d2)如果合法则加入nextStates // 4. 计算 mex unordered_setint s; for (auto next : nextStates) { s.insert(dfs(next)); // 递归计算后继状态的SG值 } int sg 0; while (s.count(sg)) { // 找到最小的不在集合s中的非负整数 sg; } // 5. 保存并返回 dp[y][m][d] sg; return sg; }这个框架清晰地将问题分解为状态表示、边界处理、状态转移、记忆化检索、SG值计算。其中is_later_than_2001_11_4和计算下一天、下个月同一天的函数是本题的具体实现细节也是主要的易错点。4. 实现细节与极易踩坑点剖析理论清晰了实现才是魔鬼。下面我结合代码逐一拆解那些你可能一不留神就掉进去的坑。4.1 日期比较与终止判断题目说谁移动到2001年11月4日之后谁输。这意味着(2001, 11, 4)本身还是一个可操作的状态可以从它移动到(2001, 11, 5)或(2001, 12, 4)而(2001, 11, 5)及以后的日期是“非法”或“失败”状态。所以在dfs函数中我们的边界判断应该是bool is_later_than_2001_11_4(int y, int m, int d) { if (y 2001) return true; if (y 2001 m 11) return true; if (y 2001 m 11 d 4) return true; return false; }在递归开始时如果is_later_than_2001_11_4(y, m, d)为真则直接返回 SG0。这里容易混淆这个返回的0表示“当前这个(y, m, d)状态”是必败态。但谁面对它是上一个玩家移动后到达了这个状态所以上一个玩家输了。在递归中这个返回值会被上一层用来计算mex。4.2 下一天与下个月同一天的计算这是本题最繁琐的部分必须小心处理闰年和月份天数。计算下一天next_day思路是先将天数加1如果超过了当前月份的天数则月份加1天数重置为1如果月份超过12则年份加1月份重置为1。关键在于需要一个函数days_in_month(y, m)来获取某年某月的天数。pairint, int next_day(int y, int m, int d) { d; int days get_days(y, m); // 获取y年m月的天数 if (d days) { d 1; m; if (m 12) { m 1; y; } } return {y, m, d}; }计算下个月同一天next_month思路是月份加1天数保持不变。但如果下个月不存在这一天比如1月31日2月没有31天则这个移动是非法的不应作为后继状态。// 返回一个有效的日期状态如果移动非法则返回一个标记值如年月日均为-1 pairint, int next_month(int y, int m, int d) { m; if (m 12) { m 1; y; } // 关键检查下个月的这一天存在吗 if (d get_days(y, m)) { return {y, m, d}; } else { return {-1, -1, -1}; // 表示非法移动 } }get_days函数的实现int get_days(int y, int m) { static int month_days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; if (m 2 is_leap_year(y)) { return 29; } return month_days[m]; } bool is_leap_year(int y) { return (y % 400 0) || (y % 4 0 y % 100 ! 0); }踩坑提示1next_month的合法性检查必须在月份进位之后进行。比如当前是2001年12月31日next_month会先变成2002年1月31日然后再检查1月是否有31天有所以这个移动是合法的。很多初学者会先检查再进位导致逻辑错误。踩坑提示2在记忆化搜索的dfs函数中调用next_day和next_month得到后继状态后必须立即用is_later_than_2001_11_4判断该后继状态是否已经“输掉”。如果已经“输掉”即日期晚于2001.11.4那么这个后继状态不应该被加入到nextStates集合中用于计算mex。因为游戏规则是走到那个状态的人输所以你的对手不会主动走到一个必输的状态换句话说对你而言这个移动选项是不存在的。这是博弈树剪枝的关键处理错了会导致SG值计算完全错误。4.3 记忆化搜索的递归与初始化在dfs函数中我们之前提到遇到is_later_than_2001_11_4为真的状态直接返回0必败态。这构成了递归的基座。初始化dp数组为-1未计算。然后对于每个查询的起始日期(y, m, d)调用sg dfs(y, m, d)。如果sg 0则先手必胜输出YES否则输出NO。这里有一个重要的优化点由于日期范围是确定的并且查询可能很多我们可以在程序开始时就预处理计算出所有可能日期的SG值。也就是从1900年1月1日开始用记忆化搜索填充整个dp数组。这样对于每个查询我们只需要O(1)的时间查表即可。预处理的总时间复杂度是O(状态数 * 转移数)大约3.7万 * 2完全可以接受。4.4 一个完整的代码片段示例结合以上所有点下面给出核心处理部分的代码框架#include iostream #include cstring #include unordered_set using namespace std; int dp[2005][13][32]; // 多开一点空间避免边界判断 int month_days[13] {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; bool is_leap(int y) { return (y % 400 0) || (y % 4 0 y % 100 ! 0); } int get_days(int y, int m) { if (m 2 is_leap(y)) return 29; return month_days[m]; } bool is_later(int y, int m, int d) { if (y 2001) return true; if (y 2001 m 11) return true; if (y 2001 m 11 d 4) return true; return false; } int dfs(int y, int m, int d) { // 边界超过2001.11.4必败态 if (is_later(y, m, d)) { return 0; } if (dp[y][m][d] ! -1) { return dp[y][m][d]; } unordered_setint s; // 移动1: 下一天 int ny y, nm m, nd d 1; if (nd get_days(ny, nm)) { nd 1; nm; if (nm 12) { nm 1; ny; } } if (!is_later(ny, nm, nd)) { // 只有移动后的状态没输这个移动才可选 s.insert(dfs(ny, nm, nd)); } // 移动2: 下个月同一天 ny y, nm m 1, nd d; if (nm 12) { nm 1; ny; } if (nd get_days(ny, nm)) { // 下个月有这一天移动才合法 if (!is_later(ny, nm, nd)) { // 同样移动后的状态不能是输的状态 s.insert(dfs(ny, nm, nd)); } } // 计算 mex int sg 0; while (s.count(sg)) sg; return dp[y][m][d] sg; } int main() { memset(dp, -1, sizeof(dp)); // 可以在这里预处理所有状态但更常见的是在dfs中惰性计算 int T; cin T; while (T--) { int y, m, d; cin y m d; int sg dfs(y, m, d); if (sg 0) { cout YES endl; } else { cout NO endl; } } return 0; }5. 算法扩展与思维提升解决了HDU 1079我们获得的不仅仅是一道题的AC代码更是一套解决类似博弈问题的工具箱。5.1 记忆化搜索的适用场景记忆化搜索SG函数/胜负态DP适用于以下特征的博弈问题状态空间有限状态数在可接受的范围内通常百万以内。状态转移明确从每个状态能到达的后继状态可以枚举。无环游戏图是一个DAG确保递归不会无限进行。通常这类“无法移动则输”的游戏随着操作进行日期越来越晚或数字越来越小等状态是单向发展的自然无环。多个独立子游戏如果问题涉及多个这样的游戏同时进行SG定理异或和就是终极武器。5.2 对比其他解法找规律与数学归纳对于HDU 1079由于其日期规则的对称性实际上存在一个更巧妙的规律月份与日期之和为偶数的日期大部分是先手必败态和为奇数的日期大部分是先手必胜态。但有几个特殊的日期如9月30日和11月30日是例外。很多题解会直接给出这个规律然后写一个简单的判断函数。这个规律是怎么来的其实就是通过我们上面的记忆化搜索程序或者打表观察所有日期的胜负态后归纳出来的。作为学习者我强烈建议不要满足于直接背规律。通过实现记忆化搜索你锻炼的是解决未知博弈问题的通用能力。而发现规律则是你在理解问题本质后进行优化和提炼的第二步。在竞赛中时间紧迫知道规律当然快但在学习阶段掌握通用的“武器”更重要。5.3 调试技巧与验证当你写完代码发现结果不对时如何调试小范围打表写一个简单的程序输出1900年1月1日之后一小段时间比如1个月内所有日期的SG值或胜负态。手动模拟几个日期验证你的程序输出是否正确。检查边界日期重点测试月末如1月31日、年末12月31日、闰年2月29日、以及目标日期2001年11月4日前后几天的状态。检查next_month逻辑这是最容易出错的地方。用几个典型用例测试1月30日合法、1月31日合法因为2月没有31天但1月31日可以移到2月不这里要检查1月31日的next_month是2月31日非法所以这个移动选项不存在、2月28日平年/闰年不同。理解递归含义在脑海中模拟递归过程。dfs(state)返回的是面对state状态的玩家的胜负情况SG0胜。所以当你在state选择移动到一个新状态next_state时你调用dfs(next_state)得到的是对手面对next_state的胜负情况。如果存在一个next_state使得dfs(next_state) 0对手必败那么你当前state就是必胜的。6. 从这道题到博弈论学习路径HDU 1079是一个完美的入门题它包含了公平组合游戏几乎所有的核心概念状态、转移、必胜必败态、SG函数、记忆化搜索。吃透这道题你就可以沿着这条路径继续深入基础巩固练习更多单堆/单状态游戏的题目如取石子游戏每次取1~3颗强化记忆化搜索和SG函数的计算手感。理解SG定理找一些简单的多堆独立组合游戏如Nim游戏几堆石子每次任选一堆取任意正数颗。这时你会发现单堆的SG值计算还是老方法但总游戏的胜负判断变成了各堆SG值的异或和。这是博弈论的一个关键飞跃。识别游戏模型很多复杂游戏可以分解为独立的“子游戏”。学习如何建模比如翻硬币游戏、棋盘移动游戏等。寻找规律与简化对于像Nim游戏SG值有简洁的数学表达式石子数本身。对于像本题可能存在奇偶性等简单规律。在掌握通用解法后尝试观察和证明这些规律能极大提升在竞赛中的解题速度。回到HDU 1079它就像一把钥匙帮你打开了博弈论算法的大门。下次再遇到“两个人轮流操作无法操作者输”的题目时你的第一反应就应该是定义状态画出转移图尝试用记忆化搜索计算SG函数或胜负态。这套思维模式才是刷这道题最大的收获。