企业官网建设流程全解析

我一直觉得蓝桥杯省赛的Java A组第6题是最会起名字的一道题。“砍柴”这两个字，听起来像某个游戏里的生活技能，结果它在赛场上直接把我从“模拟题”的惯性思维里拽了出来。考场上我盯着题面看了大概两分钟，才意识到这根本不是求“怎么砍最省力气”，而是一个典型的公平组合游戏：两个人轮流拿刀，砍到所有人都动不了为止，谁先没得砍谁就输了。这篇文章就把我对这道题从纯暴力到SG函数、再到最终一行结论的完整推导记录下来。如果你是备战蓝桥杯Java组的同学，或者想搞懂博弈论里SG函数的实际用法，这篇应该能帮你省不少时间。

1. 先别急着“砍”：题目里的三个关键约束

题目大意是这样描述的：给定若干根木柴，每根长度是一个正整数a_i。两个人轮流操作，一次操作必须选择一根长度大于1的木柴，把它砍成两段长度均为正整数的木柴。当桌面上所有木柴长度都是1时，当前玩家不能操作，判负。给定多个测试用例，每个用例给出木柴数量和每根长度，问先手是否有必胜策略。

第一眼看到“砍柴”两个字，我的第一反应是“这题怕是让求把所有木柴都砍成1的最少刀数”——毕竟日常砍柴当然是越快越好。但题目里“轮流”“不能继续操作的人输”直接把我拉回博弈论。只要出现这两个词，就要警惕：这是一个公平组合游戏，不能用贪心或者最短路径的思路去套。

这道题有三个非常关键的限制条件，决定了它不能用普通模拟去做：

• 操作对象是一根长度至少为2的木柴，长度1的木柴是“死局”，不能再动；
• 砍出来的两段长度都是正整数，等价于把整数x拆成a+b，其中a和b都大于等于1；
• 双方都绝对聪明，都会按最优策略走，不能假设对手“失误”。

这三个限制让状态空间变得非常大。如果直接用递归搜索整棵树，指数爆炸是必然的。就拿一根长度30的木柴来说，一次可以砍成1+29、2+28……29+1共29种方式，后面局面又会继续分叉。这个复杂度根本撑不住，更别说还要处理多根木柴同时存在的情况。

这就是为什么它能在省赛Java A组占据第6题的位置：如果没有一点博弈论基础，很多人会卡在“怎么模拟最优决策”上出不来。蓝桥杯很喜欢出这种“规则简单，背后有数学结论”的题，看起来是模拟，实际考的是你有没有建立过SG函数的思维模型。

1.1 一个容易跑偏的方向：把“砍柴”当成搜索题

我身边有同学拿到这道题之后，第一反应是写记忆化搜索：定义状态为所有木柴长度组成的列表，然后在里面枚举每一根、每一种砍法，用哈希表缓存已经算过的局面。听起来很通用，但两个致命问题：

• 长度列表作为key会爆炸，因为不同长度组合太多了。两根木柴长度[2, 3]和[3, 2]算不算同一种状态？要不要排序？m重复几次？每根长度范围稍微大一点，状态数就指数增长。
• 即使记忆化，也没有利用博弈状态本身的数学结构，数据一大照样超时。

我试过用这种思路写N=100的情况，跑了很久都没跑完。后来才悟到：这种题不能从“物理过程”去模拟，要从“游戏论”去抽象。每一根木柴都是一个独立的子游戏，整局的胜负可以通过SG函数和异或操作合并出来。

1.2 公平组合游戏的判断标准

怎么判断一个游戏是不是公平组合游戏？公认的三条标准很简单：

1. 两个玩家能做的操作完全相同；
2. 不能行动者判负；
3. 游戏一定在有限步内结束。

“砍柴”完美满足：两个人都能选同一根木柴、用同样的方式砍；全是长度为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)：只能砍成1+1。1的SG是0，0^0=0，所以可达到的SG值集合只有{0}，mex({0})=1，因此SG(2)=1。
• SG(3)：可以砍成1+2或2+1。1的SG=0，2的SG=1，0^1=1；两种砍法异或结果都是1，可达集合是{1}，mex({1})=0，因此SG(3)=0。
• SG(4)：能砍成1+3、2+2、3+1。SG(1)=0，SG(3)=0，0^0=0；SG(2)=1，SG(2)=1，1^1=0。所以可达集合是{0}，mex=1，因此SG(4)=1。
• SG(5)：任何拆法都是一奇一偶，SG异或永远是1，可达集合是{1}，mex=0，因此SG(5)=0。

算到这里，0、1、0、1、0的规律已经很明显了：奇数长度SG=0，偶数长度SG=1。但注意，这只是前5个数，撑死算“猜测”。想拿分，要么继续打表到几十个看规律，要么用数学归纳法证明。考场时间紧张，我会选择先写个暴力打表程序，把1到20甚至50的SG值列出来。如果规律稳定，再回头去证明。

2.2 打表代码怎么写得又快又准

直接用转移式记忆化搜索，Java写起来很直接：

import java.util.*; public class SgTable { static int[] sg = new int[105]; static int mex(Set<Integer> 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]; Set<Integer> 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)，对N=30、50这种小规模完全够用。

我实际跑出来的前11项是：SG(0)=0，SG(1)=0，SG(2)=1，SG(3)=0，SG(4)=1，SG(5)=0，SG(6)=1，SG(7)=0，SG(8)=1，SG(9)=0，SG(10)=1。看到这个表格，规律几乎写在脸上：奇数全是0，偶数全是1。当时我心里就有底了。

3. 为什么SG值只跟奇偶有关：一个简单的归纳证明

打表只是“猜”，竞赛题里最好给出让人信服的证明。尤其是这种能把O(N^2)降到O(1)的结论，如果不证明，总担心题目里有隐藏的例外。这里我写一下完整的归纳证明。

要证明的命题是：对任意正整数x，SG(x) = x mod 2，也就是奇数SG=0，偶数SG=1。

使用数学归纳法，假设所有小于x的正整数都满足这个结论，然后分两种情况讨论：

• x是奇数：任何拆分a+b=x，a和b必然一奇一偶。根据归纳假设，奇数的SG=0，偶数的SG=1。所以SG(a)^SG(b) = 0^1 = 1。也就是说，所有可达局面的SG值都是1，可达集合只有{1}，那么mex({1})=0，因此SG(x)=0。

• x是偶数且x≥2：任何拆分a+b=x，a和b必须同时为奇数或同时为偶数。如果同为奇数，两个SG都是0，异或0；如果同为偶数，两个SG都是1，异或0。所以从直觉看，可达集合只是{0}，mex=1，因此SG(x)=1。

这里可能有人会问：偶数x拆分出来的子局面SG异或真的全是0吗？举个例子，x=4，拆成1+3，SG(1)=0，SG(3)=0，0^0=0；拆成2+2，SG(2)=1，SG(2)=1，1^1=0。确实都是0。x=6时，1+5：0^0=0；2+4：1^1=0；3+3：0^0=0。也都是0。所以偶数长度的SG值就是1。

这个证明的核心洞察是：长度x砍成两段后，两段的奇偶关系完全由x的奇偶决定。奇数只能拆出“一奇一偶”，偶数只能拆出“同奇同偶”。而归纳假设告诉我们在小范围里奇数的SG=0、偶数的SG=1，于是偶数的拆分异或永远是0，奇数的拆分异或永远是1。这个对称性实在太漂亮了。

3.1 多根木柴不能只看单根

单根木柴的SG值确定了，多根木柴的总SG值怎么算？用Nim和，也就是把所有木柴的SG值异或起来。

原因是每根木柴都是一个独立子游戏，砍这根不会碰那根，总局面就是这些子游戏的组合。SG定理直接告诉我们：整体SG = SG(a1) ^ SG(a2) ^ ... ^ SG(am)。

又因为奇数长度的SG=0、偶数长度的SG=1，异或时奇数的贡献永远是0，只有偶数参与异或。于是结论可以进一步简化为：

• 偶数长度的木柴数量是偶数时，总SG = 1^1^...^1（偶数个1）= 0，先手必败；
• 偶数长度的木柴数量是奇数时，总SG = 1，先手必胜。

这个结论可以浓缩成一句话：先手能否获胜，只取决于长度为偶数的木柴数量是奇数还是偶数。奇数则胜，偶数则负。长度为奇数的木柴完全不影响结果，全是干扰项。

这种“干扰项做得越多，结论越显眼”的题，在蓝桥杯里很常见。它考察的就是你愿不愿意把题目往数学上抽象，能不能从一堆看似复杂的数据里提取出真正影响胜负的量。

3.2 用样例验证一下

假设一组数据是m=3，木柴长度是1 2 3。偶数长度只有2一根，计数为1，所以总SG=0^1^0=1，先手必胜。

实际走一遍：先手应该直接把长度为2的木柴砍成1+1。此时局面变成1、1、1、3，四根木柴里没有偶数长度，总SG=0，轮到后手面对一个必败局面。后手只能去砍长度为3的木柴，砍成1+2或2+1，于是新的偶数长度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快不少。这个习惯建议提前养成，竞赛里有时候就差这几百毫秒。
• 如果m=0（理论上不会给，但万一），even=0，输出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，都要砍成1+1，先手再砍另一根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只能砍成2+2，SG(4) = mex{SG(2)^SG(2)} = mex{0}？这里SG(2)=1，1^1=0，所以SG(4)=1；长度为5只能砍成2+3，SG(2)=1，SG(3)=0，异或=1，所以SG(5)=0。好像还是奇偶？但继续往下算，可能会和原本的结论出现差异。这种变体不能直接套结论，必须重新打表，重新证明。

6.2 变体二：允许“不砍整根”

如果每次操作允许从任意一根木柴中“抽走”一节，那就变成了经典的取石子游戏（可能是Bash博弈或Nim），SG函数和“砍柴”完全不同。这种规则下，每根木柴长度会直接变成剩余长度，而不是分成两段。所以看到“拿走/移除”和“拆成两段”要马上区分开，它们是两种截然不同的状态转移。

6.3 变体三：给砍柴次数加限制

如果加入“最多只能砍k刀”，那就不再是纯公平组合游戏，而是有限步数限制的搜索，通常要用DP或博弈树剪枝。复杂度会比原题高不少，这时候SG函数依然可用，但需要额外记录剩余刀数，状态维度会增加。这类题在竞赛中偶有出现，套路没有SG那么统一，需要具体问题具体分析。

6.4 从一道题到一类题

后来我养成一个习惯，不管是蓝桥杯还是日常练习，只要看到“轮流操作、不能动者输”这种规则，我都会先花两分钟写一个长度为50的SG表看看。很多时候规律比你想象中来得更快。砍柴这道题，就是靠这个习惯拿下的。希望这篇文章也能帮你把这条思路刻进脑子里。