华为 10.21 校招机考：连通块统计、数字拼接最小差与区间染色

《面试题目》

1. 图论题（BFS）：给定一张图，求一共有几个连通块，以及每个点所在连通块内某个统计量的最大值；对同一块内的重复查询要能直接复用结果，不提前计算并缓存会超时。
2. 数字拆分题：给你几个数字，把它们划分成两部分后拼接组合（是拼接不是相加，顺序可以打乱），让两个整数的差值最小，只考虑非负的情况；差值相同时按第一个整数的大小排序。
3. 区间染色题：一个长度为一维坐标轴，长度为 N，第 i 个位置的颜色为 i（1-based）；给出一串操作，每个操作由 l、r、c 构成，表示把 [l, r] 区间内的坐标染成颜色 c，求每次操作之后的最长连续相同颜色长度。

《参考解析》

1. 连通块 + 块内聚合。 第一步建图（注意重边与自环不影响可达性），用 BFS/DFS 遍历所有未访问节点，每个连通块打一个编号，同时在这个块内累计题目要求的统计量（最大值/求和），把「块编号 → 聚合值」存进数组或哈希表。之后每个查询 O(1)：先查点属于哪个块，再取该块的聚合值。整体 O(n + m + q)。面试里要主动说出为什么不能每次查询都重新 BFS——单次 BFS 是 O(n + m)，q 次查询就退化到 O(q(n + m))，在大数据量下必然超时；预处理 + 记忆化是把「重复计算」换成「一次遍历」。实现上用邻接表而不是邻接矩阵，避免 O(n²) 空间。

2. 数字拼接的最小差。 关键是要先意识到「拼接」和「相加」完全不同：把数字分成两组后，组内可以任意排列，所以一个组能拼出的整数集合是所有排列对应的数，搜索空间是「子集划分 × 排列」。数据量小的时候可以二进制枚举子集（每位数分到 A 或 B），对每组枚举全排列拼数，比较差值并记录所有最优解；注意左右对称的划分只算一次，重复数字要去重避免重复枚举。剪枝：① 两个数的位数越接近越可能差小，可以先按位数分组；② 当前差已经为 0 或 1 时可以提前结束；③ 组内首位不能是 0（若题目允许前导零则另说）。如果 n 较大，这个暴力不可行，需要 DP：把数字排序后从大到小依次分配到当前较小的那个数（贪心 + 局部搜索），或者用「meet in the middle」把集合拆半。这道题在考场上没思路，本质是没有先写清楚「状态是什么」——建议先写暴力拿部分分，再想优化。

3. 区间染色 + 最长同色段。 暴力每次操作后扫一遍是 O(nq)，必然超时；自己维护「色段列表 + 每次合并」在边界处理上极易出错，且最坏仍是 O(nq)。标准解法是线段树 + 懒标记：每个节点维护 len、左端点颜色 lc、右端点颜色 rc、前缀同色长度 pre、后缀同色长度 suf、区间内最长同色长度 best，以及覆盖标记 tag。合并两个子节点时：pre = 左.pre（若左区间全同色且左.rc == 右.lc，则 pre = 左.len + 右.pre），suf 对称，best = max(左.best, 右.best, 左.suf + 右.pre 当左.rc == 右.lc)。区间染色时整段打 tag，lc = rc = c、pre = suf = best = len；下推时把 tag 传给子节点。每次操作 O(log n)，总复杂度 O((n + q) log n)。手写时最容易错的是 pushup 里「整段同色」的判断条件（左.best == 左.len），以及查询根节点的 best 而不是重新合并。

4. 这场机考的复盘。 三道题都不算偏题，但容错低、测试用例直接拉满规模，暴力分很少。教训有两条：① 先判断数据规模再选算法——看到 n、q 到 1e5 就该直接排除 O(nq)，不要抱着「先写暴力试试」的心态耗掉时间；② 复杂数据结构要在草稿上把 pushup 的合并规则和边界写清楚再敲代码，区间染色这类题边界条件（单点、整段、颜色相同相邻段）比主体逻辑更容易错。平时练习建议按「题型 → 模板 → 边界」三遍过，而不是只刷通过率。