Shannon’s Channel

总览#

A. Recall#

题意： 有一个初始为空的栈。记录下来的操作有 + x（把 $x$ 入栈）、T x / F x（查询 $x$ 是否在栈中，分别表示在、不在），但所有出栈操作都没有被记录。需要补上若干个出栈操作，使得任意时刻栈内元素互不相同，且所有查询结果都成立，输出任意一种合法的操作序列。

思路：

关键是为每一次入栈确定它的存活期，也就是它最晚可以留在栈中的时刻。

1. 预处理。 对每一次入栈 $i$，用 lst[i] 记录这次入栈的存活期末尾，初始为入栈时刻 $i$；再用 act[x] 记录值 $x$ 当前对应的那次入栈时刻。按时间扫描记录：
   • 遇到 + x，记下这次入栈的时间，并把它写入 act[x]；
   • 遇到 T x：此刻 $x$ 一定还在栈中，因此代表 $x$ 的那次入栈（入栈时刻为 act[x]）至少要一直存活到当前时刻，于是把 lst[act[x]] 更新为当前时刻（与已有值取较大者）；
   • 遇到 F x，说明 $x$ 此刻已经不在栈中，清除 act[x]，之后不会再延长它。
2. 模拟。 用一个栈维护 (元素, 存活期末尾)。逐条处理记录的操作，只要栈顶元素的存活期已经结束，就输出 - 并弹出：
   • 遇到 + x：先弹出已经过期的栈顶；再不断弹出栈顶直到 $x$ 不在栈中（保证栈内互异），然后压入 $x$ 并输出 +；最后再弹出存活期在当前时刻结束的元素。
   • 遇到查询：输出 ?，再弹出过期元素。

这样补出的操作序列既保证栈内元素两两不同，又能让每个查询在其存活期内得到正确的答案。

复杂度： 每个元素至多入栈、出栈一次，时间复杂度 $O(\sum n)$（用 map 实现则为 $O(\sum n \log n)$）。

C. Permutation Inversions#

题意： 给定一个长度 $n$ 的未知排列，以及若干条「某区间内这些下标对应数值的大小顺序」的约束，求满足所有约束且逆序对最少的排列，无解输出 $-1$。

思路：

每个约束给出的是一组下标之间的相对大小，把 $p_u < p_v$ 看成一条边，就能把问题转化为在偏序限制下给每个位置赋 $1 \sim n$ 的值。

要让逆序对最少，等价于尽量把大的数值放到靠后的下标。于是从大到小分配数值：使用优先队列（大根堆）维护当前入度为 $0$ 的点，每次取出编号最大的下标，赋上当前最大的剩余数值。编号越大的下标越优先拿到大数值，就越能避免前面的位置放过大的数，从而减少逆序对。

具体地，对约束内相邻的两个下标 $q_{j-1}, q_j$（已知 $p_{q_{j-1}} < p_{q_j}$），连一条从 $q_j$ 指向 $q_{j-1}$ 的边，表示 $q_j$ 应该比 $q_{j-1}$ 先被赋到更大的值。入度为 $0$ 的点就是当前没有「更大的数还未安排」的点，可以赋当前最大值。

若约束中出现环，则有点无法被拓扑排序、最终值仍为 $0$，说明不存在合法排列，输出 $-1$。

复杂度： 拓扑排序带堆，时间复杂度 $O(n \log n + \sum (r_i-l_i+1))$。

D. Sequence#

待补充。

F. 50 Years of Excellence#

签到题。先把每一年的得分算出来，即该年 $m$ 个评分求和，然后逐年前后比较：用变量记录上一年的得分（第一年之前视为 $0$），若当前年得分严格小于上一年，则答案加一。复杂度 $O(nm)$。

M. Check in#

用 set 存下花名册中的所有队伍名，再开一个 map 记录每个有效名称已经被查询（签到）的次数。每次查询：名称不在 set 中说明队伍无效，输出 WRONG；否则把它的计数加一，若计数为 $1$ 说明是首次签到，输出 OK，否则输出 REPEAT。总复杂度与所有名称的总字符数相关。

L. Longest Common Prefix#

待补充。