10.24 京东笔试：2 的幂相邻子序列与质数拆分构造

《面试题目》

第一题：相邻和为 2 的幂的最长子序列

给定长度为 n 的正整数数组 a，选一个非空子序列 b₁…b_k，使任意相邻两项之和恰为 2 的幂（2⁰、2¹、2²…）。长度为 1 的子序列总满足条件。求最长子序列长度 k。子序列指删除若干元素后保持相对顺序得到的序列。

输入：第一行 T 组数据；每组第一行 n，第二行 n 个整数。所有数据的 n 之和不超过 10⁵。 输出：每组一行，最长长度。

输入            输出
3
5
1 2 3 5 4       3
4
3 5 11 21       4
6
1 1 1 1 1 1     6

第二题：把 n 拆成 m 个质数

给定正整数 n、m，找一组质数 p₁…p_m（可以重复）使和为 n；无解输出 -1。任意合法解均可。

输入      输出
3 1       -1
7 2       2 5
11 3      5 3 3

《参考解析》

第一题：不要建图。按顺序扫一遍数组，维护哈希表 best[v] = 以数值 v 结尾的最长合法子序列长度。处理到 a 时，枚举 k 从 a.bit_length() 到 31（因为数值不超过 10⁹ 量级，和不会超过 2³¹），看 2^k - a 是否在 best 里；在所有命中的前驱里取最大长度 L，则当前元素能接出长度 L+1，用它对 best[a] 取 max 后继续。每个元素只枚举约 30 个 k，复杂度 O(30n)，10⁵ 数据秒过。原帖最初把「能拼成 2 的幂的数对」建成有向图求最长路，边数是 O(n²)，必然超时——这里的关键是「值域只有 2 的幂这种稀疏关系」，用「值 → 最优长度」压缩状态，而不是把元素当点。

第二题：先筛出 10⁶ 以内的质数做判定表（也可用 Miller-Rabin）。构造思路是「先摆若干个 2，再把剩下的数拆成少数几个质数」：设先放 c 个 2，剩余 S = n - 2c，需要对 S 做 m-c 个质数的拆分。依次尝试 c = m-1、m-2、m-3……：

• m-c = 1 时，要求 S 本身是质数；
• m-c = 2 时，S 为偶数用哥德巴赫猜想拆成两个奇质数（10⁶ 以内可暴力配对），S 为奇数则拆成 2 与 S-2，要求 S-2 是质数；
• m-c = 3 时，S 为偶数拆成 2 + 哥德巴赫(S-2)，S 为奇数拆成 3 + 哥德巴赫(S-3)。

任一条命中即返回。注意先判边界：m = 1 时 n 必须本身是质数；n < 2m 时无解（质数最小是 2）。这题属于「构造题」而不是搜索题，回溯枚举质数组合在 10⁵ 规模下不可能通过，原帖 0% 也正是终止条件写坏导致的爆栈。

复盘要点：两道题都在考「换状态表示」——第一题把「序列」换成「以某值结尾的最优长度」，第二题把「搜索解空间」换成「用哥德巴赫把规模压到常数项」。笔试里遇到 n = 10⁵ 且问最优解，先想能不能用值域或少量分类讨论把复杂度降下来，再落笔。