很多年前我第一次在OJ上刷到 Public Sale 这道题时第一反应是这也能算博弈一个拍卖出价的场景底价、加价限制居然能牵扯出大名鼎鼎的巴什博弈。后来把题意彻底吃透才发现它其实是巴什博弈最经典的入门形态之一几乎把“先手必胜态”的所有判断细节都考了一遍。对于刚接触博弈论的算法新手来说这题的价值不在于难而在于它逼着你想清楚一件事什么情况下先手能赢以及第一次到底出多少钱才能保证赢。这篇文章就把这道题拆开揉碎讲清楚包括判定原理、输出陷阱、代码实现以及我实际踩过的坑希望能给正在刷题的你省点时间。1. Public Sale 这道题到底在干什么1.1 还原题面拍卖规则并不复杂题目设定大致是这样有一件商品要拍卖底价为 M。两个人轮流加价每次加价必须在 1 到 N 之间整数谁先让总价达到或超过 M谁就拍下这件商品。Lele 先手需要你判断他第一次出多少价才能保证自己最终获胜并且把所有可行的出价都输出如果必败就输出none。输入是多组测试数据每组一行两个整数 M 和 N直到文件结束。我当初读题时最容易被“达到或超过”这四个字带偏总想着必须刚好等于 M 才算赢。实际上题目说的是超过也算赢也就是你报出的价格只要不小于底价 M拍卖立刻结束。这个细节后面会专门展开因为它是输出结果里最容易出错的地方。举个例子M 10N 3两人每次只能加 1 到 3。先手如果第一次出 2总价变成 2后手无论加 1、2 还是 3先手都能在后面把两个人的单轮增幅保持在 4最后先手总能让自己报出 10。这个例子具体怎么控制后面推导完原理自然就懂了。现在你只需要知道这道题和“取石子”博弈完全等价。1.2 为什么说它等价于取石子把“距离底价还差多少”看成一堆石子初始就是 M 个。每次加价 x 等价于从这堆石子里取走 x 个谁取走最后一个石子让总价达到或超过 M谁赢。所以这道题的本质就是有一堆 M 个石子两人轮流取每次取 1 到 N 个取到最后一个的人获胜。这个转化几乎是巴什博弈的标准开场。生活里更常见的版本是“抢 30”游戏两个人轮流报数每次至少报 1 个数、最多报 3 个数谁报到 30 谁赢。你把它看成 30 个石子、每次取 1 到 3本质上和这道题一模一样。很多事情一旦抽象成石子堆模型博弈解法就变得清晰了。2. 巴什博弈的判定原理自己推一遍才不会忘2.1 从终点倒推必胜态与必败态要理解巴什博弈不能只背结论最好自己从终点倒推一遍。我们把“轮到某人时距离底价还差 r”看作一个局面数值 r 越小对当前玩家越有利。如果 r N当前玩家可以直接一次加价到位所以这是一个必胜局面如果 r 0意味着商品已经被对方拍下当前玩家已经输了严格说这是终局不是“轮到谁”的有效局面。再往前看r N 1 的时候当前玩家无论取 1 到 N 中的哪个数剩下的 r 都会落在 1 到 N 之间于是对方下一手就能直接取完获胜。换句话说遇到剩余 N1 的人必败。这就是巴什博弈里最核心的“必败态”。继续倒推下去会发现一个规律只要剩余数量 r 是 N1 的整数倍当前玩家就必败不是整数倍就必胜。原因很简单当你把局面交给对方时如果剩余数量正好是 N1 的倍数那么对方无论怎么取你都可以在下一轮补足到 N1让他始终面对倍数局面直到他取完最后一个。2.2 核心结论只看 M 对 N1 取余于是巴什博弈的判定结论可以压缩成一句话若 M % (N1) 0则先手必败否则先手必胜。这里的 M 是初始剩余量N 是单次最大取走数量。为什么是 N1而不是 N 或者别的数因为两个玩家加起来一轮最多就是 N1而“补足策略”正好建立在 N1 这个周期上。M 10N 3 时N1 4M % 4 2余数不为 0先手必胜。先手第一步最稳妥的做法就是出 2把剩余量变成 8也就是 4 的倍数。之后不管后手出 a1 到 3先手都出 4-a两个人每轮合计消耗 4。于是后手每次面对的剩余量始终是 4 的倍数直到剩余 4 时后手出多少先手都能一次性补完。整个过程先手牢牢掌握节奏。M 6N 2 时N1 36 % 3 0先手必败。先手出 1剩余 5后手出 2剩余 3先手出 2剩余 1后手出 1 收尾。先手无论如何都会把某个 3 的倍数局面交给后手之前先陷入被动。这就是剩余量为周期倍数的宿命。2.3 “补足 N1”策略为什么有且仅有这一条有读者可能会问先手面对必胜局面时第一步是不是必须出余数当 M % (N1) 不等于 0 且 M N 时这个答案基本是唯一的先手只有把剩余量变成 N1 的倍数才能保证后续无论对方怎么玩都能应对。因为双方每轮最多合计消耗 N1而只有当你把对方置于倍数局面时“对方取 a、你补 N1-a”这套镜像策略才能成立。你可能会想先手出别的是不是也能赢比如 M 10N 3先手第一步出 1剩余 9后手只要出 1剩余 8也就是 4 的倍数局势瞬间被后手接管先手后面再也没法翻盘。所以在 M N 的区间想要直接锁定胜局第一步只有出余数这一个正解。只有当 M N 时规则发生了变化先手一次就能把价格抬到不低于底价 M 的位置并且由于上限是 N他可以出的范围是 M 到 N 之间的任意整数。这是拍卖“达到或超过”规则带来的特殊输出情况也是这题和老套路取石子模型最大的区别。取石子模型里剩余 5 个、每次最多取 10 个时你只能取 5 个结束但拍卖模型里你还可以取 6、7、8、9、10因为超过底价同样算你赢。3. 代码实现一句判断加一段特判3.1 输出规则整理成一张速查表在做题之前先把所有可能的情况列清楚。输入两个数 M 和 N输出共三种形态条件结果说明M N输出 M 到 N 的所有整数先手可以直接抬价到不低于底价任意一个都能赢M N 且 M % (N1) 0输出 none先手必败第一步无论怎么出都会送对方进必胜态M N 且 M % (N1) ! 0输出 M % (N1)先手第一步必须出这个余数才能把剩余量变成周期倍数这里注意 M N 时为什么不是输出“M 到 N 之间所有整数还要空格分隔”而是全部输出因为每个数都对应一种可行的第一次出价。之后后手不可能再有反击机会拍卖当场结束所以这些方案都是必胜的。比如 M 5N 10先手出 5、6、7、8、9、10 都直接成交输出就是这些数。3.2 C/C 参考代码与关键细节代码本身很短但你千万别因为它短就小看。输入终止条件是 EOF输出格式要求每个测试数据占一行多个可行解用空格分隔末尾不能有多余空格。下面这份 C 风格代码可以直接用#include cstdio int main() { int M, N; while (scanf(%d%d, M, N) ! EOF) { if (M N) { for (int i M; i N; i) { if (i M) printf( ); printf(%d, i); } printf(\n); } else { int r M % (N 1); if (r 0) { printf(none\n); } else { printf(%d\n, r); } } } return 0; }我特别说一下空格处理。if (i M) printf( )这段逻辑利用了一个事实当 M N 时循环从 M 开始至少会输出一个数所以第一个数前不加空格之后的每个数前补一个空格。这种写法比“输出一个记录一个、最后单独处理空格”更省心也不容易在边界上出错。3.3 Python 版本与多组输入的读写技巧如果你习惯用 Python 刷题注意多组输入要用sys.stdin逐行读。下面是完整实现import sys for line in sys.stdin: line line.strip() if not line: continue M, N map(int, line.split()) if M N: print( .join(str(x) for x in range(M, N 1))) else: r M % (N 1) print(r if r else none)Python 里用列表推导式生成输出字符串再 .join拼接既避免手动处理空格也天然满足“末尾无多余空格”的要求。判断r if r else none算是 Python 里写这类分支比较简洁的姿势但如果你更看重可读性写成明确的 if 语句也没问题。3.4 自测用例把边界情况一次测明白我建议你写完代码后用下面这组数据自测一遍。这些用例专门覆盖了容易漏掉的分支输入输出对应场景5 105 6 7 8 9 10M N输出整个区间4 214 % 3 1先手必胜6 2none6 % 3 0先手必败10 3210 % 4 2先手出 23 2none3 % (21) 0先手必败像 3 2 这种小数据最容易让人产生错觉M 3N 2好像先手出 2 就直接超过底价了但规则里 M N先手一次最多加 2出 2 之后总价是 2还没有达到 3后手再出 1 就成交了。所以先手是必败的。这也是为什么 M N 和 M N 必须分开处理不能只套一个取余公式。4. 实战中的坑与排查技巧4.1 最常见的三类错法我见过不少人在 Public Sale 上卡住问题大多不在博弈原理而在输出细节。第一个坑是没有处理 M N 的情况导致 M 5、N 10 时只输出一个余数 5漏掉了 6 到 10。原因就是只记住了取余公式忘了“达到或超过”让先手多了一堆直接获胜的出价。第二个坑是输出格式不对。none拼错或者该换行的地方没有换行又或者每个可行解之间用了逗号而不是空格都会直接换一个 Wrong Answer。这类格式问题在 OJ 上特别隐蔽因为样例往往只有一组样例能过不代表全对。第三个坑是判断边界时少写了等号。比如把M N写成M N然后 M N 时会走取余分支。比如 5 5正确结果是输出 5写成M N后5 % 6 5输出 5结果碰巧一样。但 M 2、N 2 时正确是输出 2错误代码会算 2 % 3 2还是碰巧一样。真正暴露问题的是 M 4、N 4正确输出 4错误代码算 4 % 5 4又一样。所以这个等号错误在大多数数据上不敏感直到遇到 M 1、N 1 这类数据时正确输出 1错误代码算 1 % 2 1还是一样。坦白讲M N和M N在这道题里因为取余结果恰好等于 M输出经常相同但你不能指望这种巧合。4.2 不放心就写个暴力对拍如果你推导完结论还是觉得虚可以写一个暴力递归函数来验证小范围内的所有情况。核心逻辑是当前剩余 rem如果 rem N当前玩家直接赢否则尝试取 1 到 N只要存在一个取法能让对方进入必败态当前就是必胜态。bool dfs(int rem, int N) { if (rem N) return true; for (int x 1; x N; x) { if (!dfs(rem - x, N)) return true; } return false; }这里rem - x可能变成 0 或负数但因为rem N x所以减去之后不会小于 1不会出现负数递归总是能正常终止。对拍时固定 N枚举 M 从 1 到 30 左右把暴力结果和M % (N 1)的结论作比较能让你对结论非常放心。我第一次做对拍时发现暴力跑出来 M 4、N 2 是先手胜而直觉总觉得 4 个石子每次取 1 到 2 个应该是先手难赢结果一推演发现先手出 1 就能把局面交给“剩余 3”这个必败态瞬间理解了倒数第二个关键局面。这个顿悟比记住任何公式都更有价值。4.3 容易混淆的巴什博弈变体巴什博弈有个常见变体是“取到最后一个的人输”也就是反巴什博弈。那种题的判定会从“M % (N1) 0 必败”变成别的条件比如某些情况下余数为 1 时结果反转。如果你后面遇到这类题一定要先确认是“取完赢”还是“取完输”别把 Public Sale 的结论直接套上去。还有一个容易混淆的模型是这样的如果不要求“达到或超过”而是要求“最后一次必须刚好加到 M超了算违规”那 M N 时的输出就会变成只有 M 一个数而不是 M 到 N 的整个区间。很多题解讨论里吵的就是这个。Public Sale 原题明确写了“达到或超过”所以输出区间是对的。做题时第一件事一定是读清楚题目里到底写的是“等于”还是“达到或超过”。5. 从这道题延伸出去巴什博弈的思维方式5.1 抢 30 游戏里的同一套打法差不多每个学博弈的人都玩过抢 30从 1 开始轮流报数每次可以报 1 到 3 个连续的数谁先报到 30 谁赢。用石子模型看这就是 M 30、N 3 的巴什博弈。30 % 4 2所以先手先报两个数1、2。之后不管后手报几个数先手都补到 4 个数的周期最后一定由先手报出 30。这套思路在现实生活中也挺有用。比如两个人轮流往一个目标金额里加钱谁先加满谁赢你能提前算出控制点掌握主动权。本质就是先算周期再找余数然后每次都用“对方加 a我加 N1-a”的策略锁定局面。5.2 模式识别看到“轮流、上限、先手”就想到周期刷题多了你会发现巴什博弈的识别方式很简单两人轮流操作、单次操作数量有上限、谁先达到目标谁赢。满足这几个特征可以先尝试用取余公式判断。尤其当 N 相对 M 很大或者很小的时候边界条件更要仔细处理。更重要的是理解“必败态”这个概念。很多博弈题的突破口就是找那个让对手无法翻盘的周期点而不是真的把所有状态都搜索一遍。掌握了这个思维后面学威佐夫博弈、尼姆博弈、SG 函数时会顺畅很多。5.3 后续可以挑战的进阶方向如果你把 Public Sale 吃透了下一步可以按这个顺序继续扩展先做几个变种巴什博弈比如把输出改成“先手必败时输出 0”这类格式变化然后接触尼姆博弈理解多堆石子时的异或判定再往后就是 SG 函数它能统一处理很多复杂博弈。每个阶段都会用到今天推导必胜态、必败态的方法所以别急着背结论把推导过程记牢才是真正的收获。最后再分享一个我自己的习惯遇到博弈题我会先在小本子上手写一张小表把剩余量从 0 到 2N2 的胜负状态列出来观察规律再推广到任意 M。这样做虽然比直接套公式慢几分钟但理解深度完全不一样。Public Sale 这道题就是最好的练手对象等你亲手推出M % (N1) 0这个结论时那种“原来如此”的感觉会远比看十篇题解来得扎实。