360 笔试 10.10 记录：赛码网技术综合 D 卷 Java 卷

《面试题目》

1. 单选 40 道：前端、后端、大模型、Linux、排序算法、SQL、加密算法（其中出现了一道凯撒密码）混着出。
2. 编程题 1（20 分）：给定 a1、b、c、d，递推式 a_i = (a_{i-1} × b × c + c) mod d，求 MEX 值。
3. 编程题 2（20 分）：给一个嵌套数组，每轮消除一个连续回文子串，问最少要多少次消除才能删空。

《参考解析》

递推取模求 MEX 这道题卡在哪。递推式本身很朴素：由 a1 依次算出 a2…an，再把序列当作一个集合求最小未出现的自然数。模拟思路没问题，但只过 18% 通常意味着三种情况之一。第一是超时：如果 n 给到几百万甚至上亿，逐项计算本身可能就不够，需要发现序列的周期性——递推是确定性的、状态空间只有 d 种取值，所以序列必然在不超过 d 步后进入循环，用「值 → 首次出现的下标」记录访问过的元素，一旦碰到重复值就说明后续是循环的，可以停止计算，环内的值也已经在集合里了，这一步能把复杂度从 O(n) 降到 O(min(n, d))。第二是溢出：a_{i-1} × b × c + c 在 64 位下也可能溢出，尤其是 b、c 都在 1e9 量级时，要么用 Python 这类大整数语言，要么在乘法时取模（(a * b) % d 再乘 c 取模，模运算对乘法封闭，可以分步取模），分步取模是标准做法。第三是 MEX 的求法本身：把出现过的值放进布尔数组或哈希集合，然后从 0 开始递增寻找第一个没出现过的值，注意负数与超过 d 的值不会出现（因为取了模，值域就在 [0, d) 内），因此布尔数组开 d 大小即可，天然是 O(d) 的。

MEX 的通用求法要记牢。MEX 是「最小排除值」，求法取决于值域：值域在 [0, n] 内时，用长度 n+1 的标记数组从 0 扫到第一个未标记值，O(n) 时间 O(n) 空间；如果要求 O(1) 额外空间，就用原地交换把值 v 换到下标 v 上，最后扫第一个 nums[i] != i 的位置；元素稀疏、值域很大时改用哈希集合。这道题因为取模后值域被限制在 [0, d)，用标记数组最自然，但如果 d 到了 1e9，就不能开那么大的数组，必须换哈希集合并且只记录出现过的值，同时把循环检测和 MEX 计算合用一份数据结构。这个「先看值域再选数据结构」的判断，是面试官和判题系统都很容易区分出候选水平的地方。

每轮消除一个连续回文子串，求最小次数。这是个区间 DP：设 dp[l][r] 表示把区间 [l, r] 删空的最少步数。基础转移是枚举分割点 k，dp[l][r] = min(dp[l][k] + dp[k+1][r])；如果 s[l] == s[r]，那么把两端并进同一次消除里通常更优，可以写成 dp[l][r] = min(dp[l][r], dp[l+1][r-1])（两端单独成一次消除），或者更一般地枚举与 l 相同字符的位置 m，把 [l+1, m-1] 删空后让 s[l] 与 s[m] 一起消除：dp[l][r] = min(dp[l][r], dp[l+1][m-1] + dp[m][r])，递归边界是 dp[i][i] = 1、空区间为 0。复杂度是 O(n^3)，n 在几百以内可用，更大就要考虑优化或者确认数据范围。

写的时候要注意两点：「嵌套数组」需要先摊平成序列或建树，摊平时要确定消除是否允许跨层（题面若限定同一层内连续，就不能简单摊平）；以及 P 回文串的判断要预处理或边算边比，否则常数会很大。帖主说「每次消除最长回文子串」的想法是贪心，而贪心在这题上不成立——最长回文不一定让剩余部分最好删，必须用 DP。

这场卷子暴露的备考重点。40 道选择题混考前端、后端、大模型、Linux、排序、SQL 与加密，其中加密只考了凯撒密码这种古典替换密码，说明选择题考的是广度与常识而不是深度，复习时把「编码 / 加密 / 哈希的区别」「对称与非对称加密的典型算法」「常见排序的稳定性与复杂度」这些基础结论过一遍就够。编程题共 40 分，两道题都没拿到分往往不是因为不会，而是节奏：先花 20 分钟把两道题的暴力版本写出来提交，往往能拿到比「精雕一道、放弃另一道」更高的总分。复盘时建议把「思路对但用例不过」的题单独归档，逐个定位是超时、溢出、还是边界，这三类是笔试失分最集中的地方。