中国电信笔试三题：许可模拟、构造与前缀和

《面试题目》

1. 有一批带次数与有效期的许可，以及一串按顺序到来的操作，需要按规则逐条判定这些操作能否执行：能执行就累计一次通行、不能就累计一次拒绝。全部处理完之后，再统计仍有效的许可个数，以及这些许可剩余次数的总和，四个结果一起输出。
2. 构造一个 1~n 的排列，要求奇数全部放在一侧、偶数全部放在另一侧，并且同一组内任意相邻两数之和都是大于 2 的偶数（即合数）；同时两组交界处的相邻两数之和也必须是合数。n=1 直接输出 1，n=2、3、4 不存在合法排法。
3. 把序列从左到右依次轮流分给 p 个组，求最长的一段连续区间，使得这段区间内每个组累加到的数值完全相同。

《参考解析》

第一题是纯模拟，考点在「状态怎么存」和「四个统计量的口径」。 正确做法是用哈希表按许可 ID 记下当前仍有效的许可及其剩余次数，操作按输入顺序一条条处理：先判断该操作引用的许可是否存在且仍有效（没过期、剩余次数大于 0），能执行就扣减次数并使通行计数加一，不能执行就使拒绝计数加一。处理完再遍历哈希表，统计剩余有效许可数与剩余次数总和。这里有两个容易丢分的细节：一是「有效期」需要按操作发生的时间判断，而不是在最后统一判断，否则会把已经过期的许可算进剩余数量；二是次数扣到 0 的许可是否还算「仍有效」要按题意区分——通常应从有效集合里移除，但如果它还有未到期的属性，就要分清「有效许可数」和「可继续使用的许可数」是两回事。时间 O(n)、空间 O(许可数)，瓶颈在哈希操作常数；如果许可量大且 ID 是连续整数，用数组代替哈希表能再快一档。

第二题的关键是意识到「组内相邻和为偶数」只是一个充分构造，不是题目的必要条件。 两个奇数的和是偶数，两个偶数的和也是偶数；只要和大于 2，就一定是合数。所以最简单的构造是：奇数段内部任意排列、偶数段内部任意排列，组内条件自动成立。难点全在交界处——交界处必然是一个奇数和一个偶数相加（奇数段端点与偶数段端点），和是奇数，就必须靠具体取值让它成为合数，最省事的组合是 5 + 4 = 9。由此推出解的存在条件：n 必须至少覆盖 4 和 5 之外的数，n ≤ 4 时凑不出这样的交界对，n = 1 就是平凡的「1」。实现上按 n 分段处理：n = 1 输出 1；n ≤ 4 输出无解；n ≥ 5 时把 4、5 拿出来摆在交界，其余奇偶各排一侧。还有两个容易踩的坑：数字 1 与偶数相邻会产生奇数（1+2=3 是质数），所以 1 必须放在奇数段内部且不与偶数直接相邻；以及要按题意确认输出的是排列本身还是 YES/NO 加方案。

第三题是「归一化前缀和 + 差值首次出现位置」的标准套路。 设第 k 组的前缀和为 s[k][i]，考察区间 [l, r] 内各组增量是否相同：条件是 s[k][r] - s[k][l-1] 对所有 k 都相等，等价于把每组都减去第 0 组后得到的差向量，在 l-1 和 r 两个位置完全相同。于是从左往右扫一遍，把当前差向量（s[k] - s[0] 组成的元组）作为哈希键，记下它第一次出现的下标；每次遇到已见过的键，就用当前下标减去首次下标更新最长区间长度。要保证正确性，键必须是「相对量」而不是绝对值——直接存 (s[0], s[1], ..., s[p-1]) 只有在全组一起变化时才等价，用差值才能把「各组增量相同」这个条件精确表达出来。复杂度是 O(n·p) 的哈希操作，p 较小时很快；如果 p 很大，可以用滚动哈希或排序后比较的方式把元组比较的常数降下来。

这三题合起来给的信号很清楚：笔试的区分度不在算法难度，而在边界与建模。 第一题没有难点，丢分只会丢在有效期口径和计数定义上；第二题考的是「构造题先想必要条件、再想充分构造，最后补小数据特判」的习惯；第三题考的是把「区间性质」转成「前缀量相等」的直觉，这是区间类问题最通用的一招。平时练习时建议对每道题强制做三件事：写出小数据的手工枚举（n ≤ 5 全部枚举一遍）、把「无解」「全零」「单元素」这些边界单独写成分支、以及估算最坏数据量下的常数。至于输入输出，ACM 模式下一律先确认是单组还是多组测试数据——这类笔试里因为读错输入格式而零分的情况比算法写错更常见。