小红书笔试复盘：子序列整除 k 计数与双人路径联合代价

《面试题目》

1. 编程题一：子序列整除 k 计数——统计数组中能被 k 整除的非空子序列个数
2. 编程题二：双人路径时间金钱联合——时间和钱必须绑在一起算，两人到会合点的时间取较晚者，求从各自起点经会合点到终点的最小总代价
3. AI 题 1 道
4. 选择题 20 道

《参考解析》

1. 子序列整除 k 计数：把它看成「余数背包」：维护 dp[r] 表示当前已扫过的元素中，余数为 r 的非空子序列个数。每读入一个数字 d，它对每个旧状态有三种去向——不要它（状态不变）、自己单开一个子序列（余数为 d % k）、接在旧子序列后面（新余数 (r * 10 + d) % k）。因为每个元素只贡献一次转移，用滚动数组从后往前或用临时数组更新即可，避免同一元素被重复使用。扫完答案就是 dp[0]，全程对 1e9+7 取模。核心识别点是「状态只需要余数」和「接尾时按十进制拼接更新余数」。

2. 双人路径题：时间与金钱不能分开跑最短路：题目的关键约束是两人的会合时间取 max，而每条边耗时都是 1，所以可以枚举最多走 L 步的限制，先分别算出两个起点到各点的最小金钱开销；对每个候选会合点，会合时间就是两人到达时间的较大值。之后再从会合点到终点跑一次最短路，边权按「时间 + 金钱」的联合代价合并。整套做法的关键词是分层图（把时间作为一层）、双源会合、以及在合并点上取 max 而不是求和——一旦把时间和金钱拆成两条独立的最短路，答案就会偏小。

3. 两道题共同的方法论：笔试里这类「状态不好直接表示」的题，先想清楚状态里必须携带什么（余数、时间预算），再决定转移；把复杂的联合目标拆成「先预处理一部分、再在关键节点合并」是常见套路。写完之后用小数据对拍一遍暴力解，能挡掉绝大多数边界错误。

4. 笔试构成与备考节奏：这场是 1 道 AI 题 + 2 道编程 + 20 道选择，选择题量大、占比不低，别把时间全压在编程题上。合理的分配是先快速扫完选择（不会的先标记，别卡），再按分值做编程题，最后回头补。AI 题通常考提示词设计或对模型输出的判断，提前熟悉用 AI 辅助写代码、验证结果的流程。