我一直觉得蓝桥杯省赛的Java A组第6题是最会起名字的一道题。“砍柴”这两个字听起来像某个游戏里的生活技能结果它在赛场上直接把我从“模拟题”的惯性思维里拽了出来。考场上我盯着题面看了大概两分钟才意识到这根本不是求“怎么砍最省力气”而是一个典型的公平组合游戏两个人轮流拿刀砍到所有人都动不了为止谁先没得砍谁就输了。这篇文章就把我对这道题从纯暴力到SG函数、再到最终一行结论的完整推导记录下来。如果你是备战蓝桥杯Java组的同学或者想搞懂博弈论里SG函数的实际用法这篇应该能帮你省不少时间。1. 先别急着“砍”题目里的三个关键约束题目大意是这样描述的给定若干根木柴每根长度是一个正整数a_i。两个人轮流操作一次操作必须选择一根长度大于1的木柴把它砍成两段长度均为正整数的木柴。当桌面上所有木柴长度都是1时当前玩家不能操作判负。给定多个测试用例每个用例给出木柴数量和每根长度问先手是否有必胜策略。第一眼看到“砍柴”两个字我的第一反应是“这题怕是让求把所有木柴都砍成1的最少刀数”——毕竟日常砍柴当然是越快越好。但题目里“轮流”“不能继续操作的人输”直接把我拉回博弈论。只要出现这两个词就要警惕这是一个公平组合游戏不能用贪心或者最短路径的思路去套。这道题有三个非常关键的限制条件决定了它不能用普通模拟去做操作对象是一根长度至少为2的木柴长度1的木柴是“死局”不能再动砍出来的两段长度都是正整数等价于把整数x拆成ab其中a和b都大于等于1双方都绝对聪明都会按最优策略走不能假设对手“失误”。这三个限制让状态空间变得非常大。如果直接用递归搜索整棵树指数爆炸是必然的。就拿一根长度30的木柴来说一次可以砍成129、228……291共29种方式后面局面又会继续分叉。这个复杂度根本撑不住更别说还要处理多根木柴同时存在的情况。这就是为什么它能在省赛Java A组占据第6题的位置如果没有一点博弈论基础很多人会卡在“怎么模拟最优决策”上出不来。蓝桥杯很喜欢出这种“规则简单背后有数学结论”的题看起来是模拟实际考的是你有没有建立过SG函数的思维模型。1.1 一个容易跑偏的方向把“砍柴”当成搜索题我身边有同学拿到这道题之后第一反应是写记忆化搜索定义状态为所有木柴长度组成的列表然后在里面枚举每一根、每一种砍法用哈希表缓存已经算过的局面。听起来很通用但两个致命问题长度列表作为key会爆炸因为不同长度组合太多了。两根木柴长度[2, 3]和[3, 2]算不算同一种状态要不要排序m重复几次每根长度范围稍微大一点状态数就指数增长。即使记忆化也没有利用博弈状态本身的数学结构数据一大照样超时。我试过用这种思路写N100的情况跑了很久都没跑完。后来才悟到这种题不能从“物理过程”去模拟要从“游戏论”去抽象。每一根木柴都是一个独立的子游戏整局的胜负可以通过SG函数和异或操作合并出来。1.2 公平组合游戏的判断标准怎么判断一个游戏是不是公平组合游戏公认的三条标准很简单两个玩家能做的操作完全相同不能行动者判负游戏一定在有限步内结束。“砍柴”完美满足两个人都能选同一根木柴、用同样的方式砍全是长度为1时无法操作每砍一刀虽然木柴数量多了一根但总长度不变能砍的“大木柴”数量最终会减少所以一定能在有限步内结束。符合这三条就可以用SG函数这套理论。很多同学一听“SG函数”就害怕其实它就是一个用来压缩局面的工具把无数种复杂的局面映射成一个非负整数然后通过异或直接判断胜负。后面我会一步一步拆开讲。2. 从递归到SG把无数局面压缩成一个整数SG函数Sprague-Grundy函数是处理公平组合游戏的最经典工具。它的定义形式化一点就是终局没有合法操作的SG值为0非终局的SG值 mex({所有下一步可能局面的SG值})。mex是一个数学记号意思是“集合中未出现的最小非负整数”。比如集合是{0,2}mex就是1集合是{1,2}mex就是0。这个定义初看有点绕但它是整座大厦的地基。对于单根木柴长度x它的下一步局面是“把x拆成a和x-a然后出现两根木柴”。在SG理论中一个局面由两根木柴组成时整体SG值等于这两根木柴SG值的异或xor。所以砍柴游戏的SG转移式是SG(x) mex({ SG(a) ^ SG(x-a) | 1 a x })这里为什么是异或而不是加法因为把几个互不影响的子游戏放在一起时整个局面的SG值是每个子游戏SG值的异或。这个结论叫SG定理是博弈论里最核心的定理之一。简单理解异或能把“子游戏的胜负信息”叠加在一起Nim游戏里已经验证过无数次了。2.1 先别背公式手工推导前几个值我一开始也觉得这个公式抽象所以建议大家拿到这种题先别急着写代码亲手算前几个SG值。算一遍比背十遍公式都有用SG(1)长度为1不能砍终局SG(1)0。SG(2)只能砍成11。1的SG是00^00所以可达到的SG值集合只有{0}mex({0})1因此SG(2)1。SG(3)可以砍成12或21。1的SG02的SG10^11两种砍法异或结果都是1可达集合是{1}mex({1})0因此SG(3)0。SG(4)能砍成13、22、31。SG(1)0SG(3)00^00SG(2)1SG(2)11^10。所以可达集合是{0}mex1因此SG(4)1。SG(5)任何拆法都是一奇一偶SG异或永远是1可达集合是{1}mex0因此SG(5)0。算到这里0、1、0、1、0的规律已经很明显了奇数长度SG0偶数长度SG1。但注意这只是前5个数撑死算“猜测”。想拿分要么继续打表到几十个看规律要么用数学归纳法证明。考场时间紧张我会选择先写个暴力打表程序把1到20甚至50的SG值列出来。如果规律稳定再回头去证明。2.2 打表代码怎么写得又快又准直接用转移式记忆化搜索Java写起来很直接import java.util.*; public class SgTable { static int[] sg new int[105]; static int mex(SetInteger set) { int g 0; while (set.contains(g)) g; return g; } static int getSG(int x) { if (x 1) return 0; if (sg[x] ! -1) return sg[x]; SetInteger reachable new HashSet(); for (int a 1; a x; a) { int b x - a; reachable.add(getSG(a) ^ getSG(b)); } return sg[x] mex(reachable); } public static void main(String[] args) { Arrays.fill(sg, -1); for (int i 0; i 30; i) { System.out.println(SG( i ) getSG(i)); } } }这里有个非常重要的细节getSG(a)和getSG(b)递归时一定已经被算出来了因为a和b都小于x所以不会出现循环调用。用HashSet保存所有下一步的SG异或值mex函数从0开始往上找第一个不在集合里的数返回即可。这个打表代码的时间复杂度是O(N^2 logN)对N30、50这种小规模完全够用。我实际跑出来的前11项是SG(0)0SG(1)0SG(2)1SG(3)0SG(4)1SG(5)0SG(6)1SG(7)0SG(8)1SG(9)0SG(10)1。看到这个表格规律几乎写在脸上奇数全是0偶数全是1。当时我心里就有底了。3. 为什么SG值只跟奇偶有关一个简单的归纳证明打表只是“猜”竞赛题里最好给出让人信服的证明。尤其是这种能把O(N^2)降到O(1)的结论如果不证明总担心题目里有隐藏的例外。这里我写一下完整的归纳证明。要证明的命题是对任意正整数xSG(x) x mod 2也就是奇数SG0偶数SG1。使用数学归纳法假设所有小于x的正整数都满足这个结论然后分两种情况讨论x是奇数任何拆分abxa和b必然一奇一偶。根据归纳假设奇数的SG0偶数的SG1。所以SG(a)^SG(b) 0^1 1。也就是说所有可达局面的SG值都是1可达集合只有{1}那么mex({1})0因此SG(x)0。x是偶数且x≥2任何拆分abxa和b必须同时为奇数或同时为偶数。如果同为奇数两个SG都是0异或0如果同为偶数两个SG都是1异或0。所以从直觉看可达集合只是{0}mex1因此SG(x)1。这里可能有人会问偶数x拆分出来的子局面SG异或真的全是0吗举个例子x4拆成13SG(1)0SG(3)00^00拆成22SG(2)1SG(2)11^10。确实都是0。x6时150^00241^10330^00。也都是0。所以偶数长度的SG值就是1。这个证明的核心洞察是长度x砍成两段后两段的奇偶关系完全由x的奇偶决定。奇数只能拆出“一奇一偶”偶数只能拆出“同奇同偶”。而归纳假设告诉我们在小范围里奇数的SG0、偶数的SG1于是偶数的拆分异或永远是0奇数的拆分异或永远是1。这个对称性实在太漂亮了。3.1 多根木柴不能只看单根单根木柴的SG值确定了多根木柴的总SG值怎么算用Nim和也就是把所有木柴的SG值异或起来。原因是每根木柴都是一个独立子游戏砍这根不会碰那根总局面就是这些子游戏的组合。SG定理直接告诉我们整体SG SG(a1) ^ SG(a2) ^ ... ^ SG(am)。又因为奇数长度的SG0、偶数长度的SG1异或时奇数的贡献永远是0只有偶数参与异或。于是结论可以进一步简化为偶数长度的木柴数量是偶数时总SG 1^1^...^1偶数个1 0先手必败偶数长度的木柴数量是奇数时总SG 1先手必胜。这个结论可以浓缩成一句话先手能否获胜只取决于长度为偶数的木柴数量是奇数还是偶数。奇数则胜偶数则负。长度为奇数的木柴完全不影响结果全是干扰项。这种“干扰项做得越多结论越显眼”的题在蓝桥杯里很常见。它考察的就是你愿不愿意把题目往数学上抽象能不能从一堆看似复杂的数据里提取出真正影响胜负的量。3.2 用样例验证一下假设一组数据是m3木柴长度是1 2 3。偶数长度只有2一根计数为1所以总SG0^1^01先手必胜。实际走一遍先手应该直接把长度为2的木柴砍成11。此时局面变成1、1、1、3四根木柴里没有偶数长度总SG0轮到后手面对一个必败局面。后手只能去砍长度为3的木柴砍成12或21于是新的偶数长度2又出现了先手接着砍那根长度为2的。这样循环下去后手永远无法扭转局势。这个模拟也解释了为什么偶数长度数量是奇数时先手能赢每一轮后手只要创造出一个“偶数”先手就能把它消灭掉。这是一种“镜像策略”和Nim游戏里维持平衡的思路一模一样。4. 最终AC代码不要把所有数据都装进数组有了结论代码就可以写得非常简洁。但蓝桥杯Java组经常有大数据量输入这时候一个漂亮的结论也抵不过低效的IO。这道题如果按正常输入规模用Scanner勉强能过但既然能优化不如一步到位。最终Java实现如下import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer st new StreamTokenizer(br); st.nextToken(); int T (int) st.nval; StringBuilder sb new StringBuilder(); while (T-- 0) { st.nextToken(); int m (int) st.nval; int even 0; for (int i 0; i m; i) { st.nextToken(); long x (long) st.nval; if ((x 1L) 0L) { even ^ 1; } } sb.append(even 1 ? Yes : No).append(\n); } System.out.print(sb); } }这里我特意用even只保存奇偶性遇到一个偶数就even ^ 1最后even是1说明偶数数量为奇数输出Yes反之输出No。这样连计数器都不需要整型一路异或过去即可。代码量少也不容易写错。4.1 几个容易踩的细节长度可能比较大题目没给上限但保险起见用long读取。x 1L判断奇偶比x % 2 0快一点点更重要的是这种写法在竞赛里更“专业”。输出用StringBuilder统一攒着最后一次性print避免System.out.println调用次数太多造成性能损耗。如果T是10万级别println就要执行10万次输出慢是真实会发生的。如果T特别大StreamTokenizer读取数字比Scanner快不少。这个习惯建议提前养成竞赛里有时候就差这几百毫秒。如果m0理论上不会给但万一even0输出No符合逻辑没有木柴先手也不能操作必败。4.2 复杂度分析时间复杂度是O(总木柴数量)也就是读一个数处理一个数与T和m的总规模线性相关。空间复杂度是O(1)因为核心结论就是“偶数数量奇偶性”连数组都不用开。你可能会觉得这种结论太简单会不会题目有更隐蔽的坑我在考场上也反复确认了题面有没有“每次必须砍成两段长度相等”或者“砍断后必须丢掉一段”之类的限制。一旦条件变化结论立刻失效。所以读题阶段多花30秒比代码写错再改要划算得多。5. 考场上的“破题三招”暴力打表、归纳验证、代码收口很多同学不是不会SG函数而是拿到题后不敢往博弈论上想。这里分享一下我平时做博弈题的三板斧也是这次“砍柴”题的实际解题节奏。希望你能把这套流程内置到自己的解题体系里。5.1 第一招先别证明先把小范围打表跑出来不管题目多奇怪只要规则是“两个人轮流操作”我就会立刻在草稿纸上算小规模状态。最好直接写一个不超过30行的暴力递归把前20个状态的SG值打出来。这道题打表后奇偶规律非常明显一眼就能看出来。即使你最后不会证明凭借“偶数数量奇数则胜”的结论也能AC。竞赛考试不是论文答辩先拿到分比什么都重要。所以打表这个动作一定要快不要在一个暴搜上磨蹭太久。5.2 第二招把规律变成策略反过来检验规律不是打印出来就完事。我会拿具体例子验证比如一根长度4的木柴先手应该怎么赢按结论4是偶数先手必胜。实际策略把4砍成2和2后手无论动哪根2都要砍成11先手再砍另一根2最后所有木柴都是1轮到后手没得动。这个过程中先手每一步都“跟着后手操作”很像Nim游戏里的镜像策略。验证之后再想多根情况两根长度2和3偶数长度只有1个先手胜两根长度2和2偶数长度2个先手败三根长度1、2、3偶数长度1个先手胜。手工模拟一遍结论成立。这一步能过滤掉九成打表出现的假规律。5.3 第三招把O(N^2)的转移式压缩成O(1)再写代码很多博弈题的SG转移式看起来是O(N^2)但数据范围可能是10^9或者单组数据大到无法枚举拆分。这时候一定要停下来找规律而不是硬写DP。“砍柴”的规律是奇偶其他题的规律可能是周期、可能是二进制按位异或但找法都一样列出前几十项然后对着特点猜再用归纳法或者反证法验证。我经常看到有人把SG函数背得很熟但一遇到新题就开始套模板。真正的考场技巧是把模板当成一种“破题工具”用它快速暴推出前几项再根据前几项反推数学结构。5.4 蓝桥杯Java组的提分细节这里额外说点Java组特有的东西蓝桥杯官方OJ支持JDK 8或更高版本BufferedReader、StreamTokenizer都是可用的建议平时就固定用这套IO模板不要临场换。代码开头不需要package外部类名必须是Main否则编译报错。不要用Scanner读取大量数据我用它吃过超时的亏读者千万别踩。输出内容要严格匹配题目样例的格式Yes/No的大小写、换行都别错哪怕答案对也会白扣分。6. 这道题还能怎么变砍柴、拆数、还是取石子“砍柴”表面上是一个劈木头的故事背后本质是“把整数x拆成两个正整数”的拆数游戏。这类问题有很多变体这里列几个我在刷题时见过的变体供大家举一反三。6.1 变体一限制拆分结果相等如果规则变成“每次必须把一根木柴尽量砍成两段相等的长度长度差不能超过1”那SG函数就没有“奇偶”这么简单了。因为长度为4只能砍成22SG(4) mex{SG(2)^SG(2)} mex{0}这里SG(2)11^10所以SG(4)1长度为5只能砍成23SG(2)1SG(3)0异或1所以SG(5)0。好像还是奇偶但继续往下算可能会和原本的结论出现差异。这种变体不能直接套结论必须重新打表重新证明。6.2 变体二允许“不砍整根”如果每次操作允许从任意一根木柴中“抽走”一节那就变成了经典的取石子游戏可能是Bash博弈或NimSG函数和“砍柴”完全不同。这种规则下每根木柴长度会直接变成剩余长度而不是分成两段。所以看到“拿走/移除”和“拆成两段”要马上区分开它们是两种截然不同的状态转移。6.3 变体三给砍柴次数加限制如果加入“最多只能砍k刀”那就不再是纯公平组合游戏而是有限步数限制的搜索通常要用DP或博弈树剪枝。复杂度会比原题高不少这时候SG函数依然可用但需要额外记录剩余刀数状态维度会增加。这类题在竞赛中偶有出现套路没有SG那么统一需要具体问题具体分析。6.4 从一道题到一类题后来我养成一个习惯不管是蓝桥杯还是日常练习只要看到“轮流操作、不能动者输”这种规则我都会先花两分钟写一个长度为50的SG表看看。很多时候规律比你想象中来得更快。砍柴这道题就是靠这个习惯拿下的。希望这篇文章也能帮你把这条思路刻进脑子里。