荣耀 9 月 30 日机考笔试题与题解（护队演练、双廊同序）

《面试题目》

1. 操场护队演练：初始有一列 n 个互不相同的代号（站位不按代号大小）。每轮给出护挡者指向的站号 guard 和追逐者指向的站号 attack，都从 1 起算。若两者指向同一站则本轮扑空、无人离列；若两站不同且 attack 仍在当前人数范围内，则第 attack 站的人离列、右侧的人依次左移；attack 越界则本轮无人离列；guard 越界时护挡不算数，但只要 attack 有效，该站的人照样离列。某一轮结束后人数小于等于 1 即立刻失败、后续轮次不再进行；全部轮次做完人数仍大于 1 则成功。输出成败标记（成功 sheng、失败 bai），成功时按代号数值升序输出剩余代号，失败时保持当时从左到右的顺序。
2. 双廊同序展数：给定东廊与西廊两条展品编号序列（小写字母，同一条廊里可重复），从每条廊里按原有先后各挑出若干件，要求两条挑出的编号序列完全相同——可以跳过不选，但不能对调已选展品的左右次序。求最多能挑出多少件，只输出件数。

《参考解析》

第一题是纯模拟，得分点全在分支顺序和两个细节上。 按「当前人数」维护一个数组或列表，每轮先取当前长度 len：如果 len ≤ 1 就直接跳出整轮循环（不是跳过本轮，而是后面的轮次全作废）；接着判 attack，越界（小于 1 或大于 len）则本轮无人离列，直接进下一轮；attack 有效时再看 guard——guard 越界或 guard ≠ attack，都执行「删掉当前第 attack 个元素」，只有两者都落在列内且相等才扑空。两个容易翻车的点：一是别把 guard 的判断放在 attack 之前，题干明确写了「护挡不算数时追逐仍然有效」；二是输出格式分流，成功要把剩余代号排序后再输出，失败必须保持删除过程中形成的位置顺序，这里搞反了逻辑正确也会错。删除操作用 list.erase(begin + attack - 1) 或 pop(attack - 1) 都是 O(n)，最多删 n 次，总复杂度 O(m + n²)，n 不大时完全够用；若想更稳可以换成链表或树状数组在 O(n log n) 内完成，但机考时间有限时不必上。

第二题是标准的最长公共子序列（LCS），识别出来就基本拿满。 设 dp[i][j] 表示东廊前 i 件、西廊前 j 件最多能挑出的件数：若第 i 件与第 j 件编号相同，dp[i][j] = dp[i-1][j-1] + 1；不同则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])，含义是丢掉其中一边的当前展品再继续。任一边件数为 0 时前缀答案都是 0，最终输出 dp[n][m]。时间 O(n·m)，空间可以用两行滚动数组压到 O(m)——这在 n、m 上千时很关键，完整的二维表虽然也能过，但滚动数组是面试官愿意看到的加分项。题干给出的样例（a b c b d a b 与 b d c a b 答案为 4，对应 b c a b）可以用来验证转移式：两条序列里都能按顺序取到这四个字母，而取不到更长的。

这道题真正的坑在输入解析，不在算法。 题干明确写了「若件数为 0，则这一行为空行」，也就是说读完件数之后要用整行读取（C++ 的 getline 配 cin.ignore()、Java 的 readLine、Python 的 input()），不能一路 cin >> token 或 StringTokenizer 逐 token 取——一旦遇到空行，逐 token 读法会把下一行的件数当成展品编号吃进去，后面全部错位。C++ 那版实现里先 cin >> eastCount 再 cin.ignore() 再 getline，顺序不能反，否则换行符会留在缓冲区里导致第一行读到空串。另外件数给 0 时不要试图 split 空串（会得到长度为 1 的空数组），要先判 count > 0 再解析，这一点在给的样例里测不出来，属于典型的边界用例。

关于这份记录的完整性说明。 原帖按「第 1 题 / 第 2 题」组织，每道题都配了 C++、Java、Python 三份参考实现，但帖子在第二题的 Java 代码中途被截断，后面的题号和实现没有留下来。上面只整理已能确认的两道题的题意与思路，未出现的部分不做推测；两道题的题面、样例与复杂度分析对备考机考的参考价值是完整的。