寒武纪测试开发笔试：博弈选择与四道编程

《面试题目》

1. 单选：考了很多拿石子的题目，各种变种——几堆石头，一次拿几颗，谁能先拿完或者后拿完，求必胜策略。
2. 多选：考了很多树和图的计算题，给出节点、度、边之类的条件，求有多少节点、多少边。
3. 编程第一题：给一个 n 的排列，例如 n=5、排列为 2 3 1 5 4，一次交换一对数，使排列有序（变成 1 2 3 4 5），最少需要多少次交换？
4. 编程第二题：a、b、c 三个数，要求让 b > a > c，需要一共给 a 和 b 加上多少？例如现在的 a b c 是 3 4 5，就得补成 6 7 5，一共加了 6。
5. 编程第三题：在直角坐标系中给一堆点坐标，点之间两两连线，穿过 x 轴加一分，穿过 y 轴加一分，一次性穿过 x 和 y 加 2 分，问连线后最高得分。
6. 编程第四题：最长上升除数子序列——最长上升子序列的变体，上升的条件改成「这个数字是前面数字的整数倍」才算上升。

《参考解析》

取石子博弈的两大套路：这类题先分清是「拿完最后一个赢（正常博弈）」还是「拿完最后一个输（反 Nim / misère）」。最基础的是 Nim：n 堆石子，每堆任意取，把各堆数量异或起来，异或和非零先手必胜——因为非零局面总能一步走到异或为零，而零局面无论怎么拿都会变成非零。变种基本都在改「一次能拿多少」：如果一次最多拿 m 颗（或每次 1~m 颗，只有一堆）就是巴什博弈，n % (m+1) != 0 先手胜；如果是「每次只能从一堆里取，且取的数量有上下界」，就用阶梯 Nim / 差分思路，把每段差值异或起来判断。多选题里常见的「谁能先拿完 / 后拿完」就是在考你区分正常与反 Nim：反 Nim 的判定是「所有堆都是 1 时看堆数的奇偶，否则仍看异或和」。备考时把 Nim、巴什、威佐夫（两堆，取差值倍数，必败态是黄金分割比）、阶梯 Nim 这四个模板吃透，绝大多数变种都能现场推。

树和图的节点、度、边计数：核心公式是握手定理——无向图所有节点度数之和等于 2 倍边数（Σdeg = 2E），树还多一条 E = V - 1。常见问法有三类：① 给一棵树各节点的度，求叶子节点数：设度为 1 的节点有 n1 个、度 ≥2 的节点数为 n2，则 n1 = 2 + Σ_{deg≥3}(deg-2)·count，本质是「每条分叉要多消耗一个叶子」；② 给完全二叉树 / m 叉树的节点总数求叶子数与高度（2^h - 1 那套）；③ 给度数序列问是否可简单图化（用 Havel-Hakimi 算法逐次减去最大度并排序判断）。多选容易在「树的度数之和 = 2(n-1)」和「边数 = 节点数 - 1」这两个式子上做文章，列方程前先把已知量标清楚。

置换最少交换次数：把排列看成置换，分解成若干个环，长度 k 的环需要 k-1 次交换才能归位，所以答案是 Σ(k_i - 1) = n - 环的个数。实现上开一个 visited 数组，从每个未访问位置出发沿着 i → p[i] 走完整个环并标记，统计环数即可，时间 O(n)。这道题（力扣 765 那类「交换使序列有序」）还有一个常见变体：如果只允许交换「相邻」两个元素，最少次数就变成逆序对的个数（用归并排序或树状数组统计）。审题时务必确认交换是否要求任意两个位置可换——这是两种完全不同的解法。

三数加和凑大小关系：原帖例子是 3 4 5 补成 6 7 5，总共加 6，说明规则是「只能往 a、b 上加，加完要满足 b > a > c，且 c 不变」。从约束反推：最终必须 a ≥ c+1、b ≥ a+1，为了总增量最小，两个不等式都取等号最优，即 a' = max(a, c+1)、b' = max(b, a'+1)，答案是 (a'-a) + (b'-b)，注意先算 a 再算 b（b 的下界依赖于修正后的 a）。检查例子里 c=5：a' = max(3,6) = 6、b' = max(4,7) = 7，增量 3+3 = 6，与原帖一致。这类题的通法是「把约束写成不等式 → 按依赖顺序逐个取满足条件的最小值 → 求总和」，属于贪心，正确性来自每个变量都取到了下界。

连线穿轴得分：把每个点按象限分类：x>0 且 y>0 是第一象限，x>0 且 y<0 是第四象限，以此类推。两个点的连线穿过 x 轴 ⟺ 它们的 y 异号；穿过 y 轴 ⟺ 它们的 x 异号；同时穿过两轴（得 2 分）⟺ x 异号且 y 异号，也就是两个点位于对角象限。于是每条线段的得分等于「y 异号」+「x 异号」的指示之和，总得分等于所有点对求和。问题问「最高得分」，而点集固定时每条线段的得分也就固定了，因此关键在于「连线」是否指任意配对（即把点两两配对、每个点只用一次，求配对方式的最大得分）——若是配对问题，就变成最大权匹配：把点按象限计数，对角象限之间配对得 2 分（例如一象限配三象限、二象限配四象限），相邻象限或跨轴配对得 1 分，用贪心先配对角、再配相邻，剩余的同侧点之间连线得 0 分。原帖没有保留题意细节和 n 的范围，这里给出的是通法思路；做题时先写一个 O(n²) 枚举点对的版本，再根据「是否允许重复配对」决定要不要上匹配。

最长上升除数子序列：设 dp[i] 为以第 i 个数结尾的最长合法子序列长度，转移条件是 a[i] % a[j] == 0 && a[i] > a[j]，即 dp[i] = 1 + max{dp[j]}，朴素做法 O(n²)。关键前提是序列里都是正整数（除数关系才有意义），如果有 0 要单独处理（任何数都是 0 的倍数，而 0 不能做除数）。优化方向有两条：一是把数排序后按值域建树状数组 / 线段树，对每个数的所有倍数（2a, 3a, ... 在值域内）查询历史最优 dp 值再更新，复杂度 O(M log M)；二是如果重复元素多、且允许取相同值（题目要求严格上升则不允许），需要按同一值的分组批量更新，避免同值之间互相转移。