又一场春招笔试完美落幕啦，总体来看这场在线编程题难度不大，更多考察的是代码的基本能力。

各位解题高手是不是仍意犹未尽呢？但与此同时你也会想要知道答案吧，这里就有出题官给大家分享的解题思路哦。快来看看你的思路有没有跑偏呀！

Prob. A- 两数组找相同的元素

题目大意

给定两个无序数组求交集，时间复杂度要求 O(nlogn) 或 O(n)。

题解

简单题。排序二分、Tree set/map 都可以实现 log 级别的快速查找，也可以利用 hash 实现 O(1) 的查找复杂度。

值得注意的是，各个语言的一些基于无序查找的 List find 方法都是线性复杂度的（例如 c++ 的 vector::find，javascript 的 Array.indexof 等），不满足要求。

Prob. B - DAU 统计

题目大意

给定一堆 64 位 ID，根据题目规则求 distinct ID 的数量。

题解

简单题，本质上就是实现一个 unique 方法。做法很多，一个简单的实现方法就是排序之后进行相邻比对即可。尽管时限上卡得不严，但由于读入的数据量很大，在 IO 上也有些优化的余地。例如对于 C++ 的用户，更推荐使用 scanf 而不是带 IO 同步的 cin（也可以采用 getchar/fread 进一步优化）；对于 java，stream buffered input method 在性能上也比裸的 scanner 更好。当然即便不加这些优化，上述算法也能顺利通过测试数据。

作为一个在线笔试题，这个题目是非常简单的。一个留给各位思考的 meta problem 是，如果应用于更大规模的场景下，又应当如何实现这个问题？

Prob. C - 形式化算式

题目大意

根据题目格式，对一个算式（包含数字和加减乘除）进行点阵输出。

题解

代码实现题。先将各个字符的点阵存起来，然后确定最后要输出的所有字符（例如 sprintf），接下来模拟输出就可以了。整体实现上没什么难度，一些 corner case 包括小数点，末尾 0 等，小心处理即可。

Prob. D - 任务执行策略

题目大意

给定一个任务依赖的下三角矩阵，每个任务依赖于它在矩阵中下方的两个子任务，当且仅当子任务都执行完成之后才能执行当前任务。求执行恰好 k 个任务的最大权值之和。

题解

动态规划。

如图，如果我们选择了 Job(i, j)，除了要同时选中 Job(i + 1, j)之外，也意味着 Job(i + 1, j + 1), Job(i + 2, j + 2) … Job(i + d, j + d) 这一条链全部都要选中。既然每条斜线都是选择一个后缀，因此可以据此划分阶段进行动态规划。

考虑 f[i, j, m] 表示前 i 条斜线，总共选择了 m 个任务，其中第 i 条斜线自下往上选择了 j 个任务时的最大权值和，那么转移时只需要保证第 i - 1 条斜线需要选择的任务个数 >= j - 1 即可。状态转移方程为

f[i, j, m] = max(f[i - 1, j2, m - j]) + sum[i, j] (j - 1 <= j2 <= i)

这里 sum[i, j] 表示第 i 条斜线的最下面 j 个任务的权值之和。这个转移的复杂度是 O(n) 的，总复杂度会达到 O(n^3 * m)，不符合要求。问题的关键在于如何快速地获得 max(f[i - 1, j2, m - j]) 这一项，这里的优化方式很多，简单举两个方法：

1. 用另一个数组维护每条斜线的 f 数组的后缀的最大值，那么 max(f[i - 1, j2, m - j]) 这一项就可以 O(1) 得到；

2. 将 f 的定义改为，第 i 条斜线自下往上 至少 选择了 j 个任务的最大权值和，那么转移时就不需要枚举 j2 了。具体的转移方程留给各位重新推导一下。

优化之后可以得到 O(n^2 * m) 的时间复杂度。

当然这个题目也可以有另外的状态划分方式。注意到 Job(i, j) 选中时，除了 Job(i + 1, j + 1) 这个任务之外，Job(i + 1, j), Job(i + 2, j) … Job(n, j) 这一条链也必须选中，那么也可以用和上述对称的方式来构造转移方程。时间复杂度同样也是 O(n^2 * m) 的。

笔试题解已经诚意满满地奉上，

我们也同样满怀诚意地期待与你在头条相见！