[SWTR-9] NFLSPC #6 重现赛自测

## 题解： ### A. 所以 k 小生成树怎么做？ 首先求出最小生成树。 已知次小生成树可由最小生成树加入一条非树边并删去一条树边得到。枚举非树边 $(u, v)$，求出 $u, v$ 在最小生成树的简单路径上权值最大的边，如果加入 $(u, v)$，则删去这条边。对每条非树边求出加入它对权值的影响是多少，取权值增加量最小的方案。 对最小生成树求出权值增加量最小的非树边，则有两种选择：强制选择这条边，和强制不选择这条边。对于前者，给出了一棵新的生成树；对于后者，没有给出新的生成树，但边的状态改变了。 如果强制不选择这条边，那么接下来就是决策权值增加量次小的边是否强制选择，依次类推。于是最小生成树给出了若干棵新的生成树，其中第 $i$ 棵生成树钦定了权值增加量前 $i - 1$ 小的非树边不选择，且第 $i$ 小的非树边强制选择。将所有生成树加入优先队列。 不断从优先队列取出权值最小的生成树 $k$ 次做上述扩展，注意已经钦定状态的边不可被改变。一条边有四种状态：树边且可被替换；非树边且可加入生成树；树边且不可被替换；非树边且不可加入生成树。在枚举所有非树边时需要跳过所有不可加入生成树的非树边，求一条非树边能替换掉哪条树边时不能替换不可被替换的树边。 为什么这样做是对的：钦定权值增加量最小的非树边是否选择，本质是将当前生成树可扩展到的生成树集合分裂为了两半，一半含这条非树边，另一半不含这条非树边。每棵可扩展到的生成树恰属于其中一半。对于含非树边的，替换后的生成树一定是这些生成树的权值最小值，因为替换后的生成树是相对于当前生成树而言的次小生成树，即不存在可扩展到的生成树的权值小于替换后的生成树（否则和替换后的生成树为次小生成树矛盾了）。对于不含非树边的，对应集合的最小值依然是当前生成树，但一条非树边的状态从可加入变成了不可加入。 如果将每棵生成树抽象为一个点，用一棵有根树描述整个扩展过程（根节点是最小生成树），那么每个非叶子结点有两个儿子，一个是实点，从当前点向下走到实点表示用一条非树边替换了一条树边得到新的生成树；另一个则是虚点，从当前点向下走到虚点表示当前生成树的一条非树边从可加入变成了不可加入。由于实点一定是当前生成树能扩展到的最小生成树，所以整个过程是不重不漏的。 支持对一个 “点” 求权值增加量最小的非树边：直接求树链最值需要倍增，但我们只需求 $\mathcal{O}(k)$ 次权值增加量最小的非树边。考虑对每条可被替换的树边求出能替换它的权值最小的非树边，操作方式为按权值从小到大的顺序枚举可以加入的非树边，将对应路径上所有还没被标记的边标记。可以用并查集实现该过程。 优先队列中不需要存储生成树的具体形态，只需记录每棵生成树由哪棵生成树如何替换一条边扩展得到，以及权值。等到真正取出这棵生成树之后再对其 DFS 预处理相关信息（以支持求权值增加量最小的非树边）。 此外，为了避免从优先队列中不断取出虚点导致求了 $\mathcal{O}(m)$ 次后继状态（相当于去掉了所有虚点，将二叉树变成了多叉树），考虑只扩展一次且只维护实点，并在取出实点后加入它的 “兄弟虚点” 的实儿子。 - 使用倍增，并将所有后继状态全部加入优先队列的复杂度为 $\mathcal{O}(mk\log (mk))$。由于卡不满，常数很小，可以通过。 时间复杂度 $\mathcal{O}(m\log m + mk\alpha(n) + k\log k)$。 ### B. Power of Three（不属于重现赛） 使用光速幂预处理并计算两组询问的答案大约需要 200ms。 因为 $T\leq 20$，考虑每次计算两组询问，并利用运行时间直接求出这两组询问的答案，如强制运行 240ms，280ms，320ms，360ms 分别表示这两组询问的四种可能。只需提交 $\lceil \frac T 2 \rceil$ 次即可获得测试点对应的输出。 而且，由于我们可以看到每个点的运行结果，可以同时套所有的点，一共只需提交 $10$ 次。 有一些更好的套数据方法是用消耗的空间甚至 main 函数返回值来套取信息，这样一次可以套三组数据。 ### C. 真理祭坛 本题解法灵活, 题解仅供参考. $n \leq 4$ 时可以直接类 Dijkstra: 共 $2^{2^n} \leq 65536$ 种本质不同的真值表, 每次找出未确定答案的真值表中对应公式最小的, 让它与之前已经确定的所有真值表进行 $\land$ 和 $\lor$ 的松弛, 贡献其他真值表, 时间复杂度 $\mathrm O(2^{2^{n + 1}})$. 初始时只有 $P_i$ 和 $\lnot P_i$ 是确定的, 这样松弛时并不需要考虑 $\lnot$ 运算, 因为由 De Morgan 律可知任何一个命题公式总可以把所有 $\lnot$ 符号移到最内层. $n = 5$ 时可能能有一些结合 $n = 4$ 所打出的表的做法, 或其他奇怪的做法, 请选手自显神通. #5 $n = 7$, 观察可知真值表与某两个变量无关, 从而转化为 $n = 5$. #6 $n = 9$, 观察可知在翻转真值表的某两位后, 与某五个变量无关, 从而转化为 $n = 4$. #7 和 #9 的答案中 $0 \sim n - 1$ 每个变量恰好各出现了一次, 故答案较小, 从而可能有面向命题公式搜索之类的做法. #8 和 #10 请选手自显神通. 值得一提的是, 有一个效果比较好的算法: 直接按某个变量分治, 递归下去, 再花费三个运算符的代价整合, 这样可以将答案大小控制在 $3(2^{n - 1} - 1)$ 内, 实际表现远优于此, 在本题中能直接获得小几十分. ### D. 来点不那么魔怔的题面 对于 $n\leq 20$，枚举所有子序列检查，$10$ 分。 对于 $k = 2$，找 $a_i < a_j$ 即可，$10$ 分。 --- 将满足 $p_{i_j}$ 是第 $j$ 大的 $p_{i_j}$ 依次列出得到 $q_{1\sim k}$，则 $q$ 是 $p$ 的子序列且 $q$ 单调递增。于是有解的必要条件是 $p$ 有长度为 $k$ 的上升子序列。 如果 $p$ 有长度为 $k$ 的上升子序列，则直接取子序列为该上升子序列即可。 于是只需求最长上升子序列即可。想到 LIS 可以直接做 $k = 3$，如果会 $n ^ 2$ DP 求 LIS 可以做 $n\leq 10 ^ 3$。 时间复杂度 $\mathcal{O}(n\log n)$。 ### E. 挑战大数因子分解 首先可以利用 $S_3$ 和 $S_5$ 解出 $S_4P$ 和 $S_6$。 我们发现，然后 $C$ 可以写成 $kS_4P+MS_6$ 的形式，其中 $k$ 是未知的整数。 于是我们得到同余方程 $S_6M=C \mod S_4P$。由于数据合法，方程显然有解，两边除掉 $\gcd(S_6,S_4P)$ 后用 exgcd 解方程可得 $M\bmod \frac{S_4P}{\gcd(S_6,S_4P)}$ 的结果。下面我们证明 $\frac{S_4P}{\gcd(S_6,S_4P)}>p^{2/3}>M$，即解出来的东西就是答案： 由于 $0<S_6\bmod P<P^{1/3}$，$\gcd(S_6,P)<P^{1/3}$，于是 $\frac{S_4P}{\gcd(S_6,S_4P)}\geq \frac{P}{\gcd(S_6,P)}>P^{2/3}$。 ### F. 1064 病毒 对于 $x < 10 ^ 9$，$g(x')$ 的长度总是为 $3$。 对于 $x < 10 ^ {999}$，$g(x')$ 的长度不超过 $9$，于是 $g(g(x'))$ 的长度总是为 $3$。 对于 $x < 10 ^ {10 ^ 5}$，$g(x')$ 的长度不超过 $16$，于是 $g(g(g(x')))$ 的长度总是为 $3$。 对数字串 $|x'| = 3$，$g(x')$ 只有四种可能：$\texttt {033}, \texttt{123}, \texttt {213}, \texttt {303}$，再迭代一次就只有 $\texttt {213}$ 一种可能。 对 $x\geq 10 ^ 9$ 显然 $f_k(x) = 213$。 对 $10\leq x < 10 ^ 9$，此时 $k\geq 3$，于是 $f_k(x) = 213$。 对 $1\leq x < 10$，此时 $k \geq 2$。观察到 $g(x') = \texttt {ab1}$，其中 $a, b$ 恰有一个为奇数码，于是 $f_2(x) = 213$，即 $f_k(x) = 213$。 对 $x = 0$，$k = 1$ 时 $f_1(x) = 11$，否则同理可知 $f_k(x) = 213$。 综上，当 $n = 0$，$k = 1$ 时，输出 $11$，否则输出 $213 \times 10 ^ n$。 时间复杂度 $\mathcal{O}(n)$。 ### G. 挑战停机问题 注意到 $a > 0$, 也就是 $A$ 总是不降的, 所以我们只需要快速地模拟 $A$ 从 $0$ 增加到超过 $\max r$ 的过程, 此后 `I` 类语句的跳转也就固定了, 只要简单地判环即可. 现在我们来考虑如何快速地模拟 $A \leq \max r$ 的过程. 先考虑 $\sum \max r \leq 10^5$ 的子任务, 这就是说我们可以对每个 $A_0 \in [0, \max r]$, 都去处理 $A = A_0$ 的时间段. 在 $A = A_0$ 固定时, 所有的 `I` 类语句的跳转也是固定的, 如果能够快速知道在当前局面下遇到的第一个 `A` 类语句 (或陷入循环), 问题便迎刃而解. 容易想到用并查集维护: 对跳转类语句进行连边, `A` 类和 `E` 类不连边, 并查集可以得到从某个点出发一直沿唯一的出边走会停在哪里 (再记录加边失败的信息即可判环). 而 `I` 类语句的贡献可以拆成 $A_0$ 所在的三个区间, 每个区间内的连边情况是固定的, 使用线段树分治 + 可撤销并查集 (按秩合并优化) 即可. 时间复杂度 $\mathrm O(n + \max r \log n \log \max r)$. 再来考虑正解. 虽然不再能对每个 $A_0 \in [0, \max r]$ 依次处理, 但注意到所有 `I` 类语句的跳转情况只有不超过 $2n$ 种本质不同的局面, 且对应 $A_0$ 的不超过 $2n$ 个区间, 于是考虑对每个区间依次处理, 求出在哪行进入下一个区间 (或陷入循环), 以及在过程中 $A$ 增加了多少. 注意到任意局面下跳转情况是一个基环树和树的混合森林, 考虑用 LCT 维护 (对于基环树, 随意断掉环上的一条边), 在链所对应的 Splay 上二分即可. 对于基环树的没有被加入的那些条边, 采用懒惰加入法, 即加入失败 (成环) 的时候就不加, 等到在 LCT 上跳到未将出边加入到 LCT 的跳转语句节点时再加入. 这样每条语句至多被加入 $\mathrm O(1)$ 次, 由势能分析法可知总复杂度为 $\mathrm O(n \log n)$. ### H. 树 考虑列出整棵树的欧拉序，对于每个颜色 $c$，设它出现了 $m_c$ 次，那么它将欧拉序划分为 $2m_c$ 个区间，每个区间答案相同。于是我们把问题转化为，有若干个有序数组，它们的长度之和为 $O(n)$，每次查询在其中一个数组中求 lower_bound。直接对每次询问二分即可做到 $O(n+q\log n)$，可以获得约 $30$~$40$ 分。 对每个数组，设数组中元素个数为 $m$，我们对欧拉序以 $\frac{n}{m}$ 为块长分块，然后对块的端点预处理出 lower_bound 的结果。查询时，找到查询位置所在块的端点，然后在此基础上暴力计算块内的部分。 由于颜色经过随机打乱，dfs 进栈序和出栈序都可视为均匀随机（尽管它们两个之间不独立），而欧拉序是进栈序和出栈序的某种归并，所以每块内期望有 $O(1)$ 个元素。于是复杂度为 $O(n+q)$。 接下来还可以加一些常数优化，例如： - 不要使用 vector，存图用前向星，按颜色归类用桶排。 - 特判链，此时不需要存图和 dfs 求欧拉序。 - dfs 到最后一个叶子之后，后面的欧拉序就不需要存了。 - 当 $m$ 很小时，不做分块预处理。 ### I. 9.pop_book(); 由于速度至多变化 $n$ 次，所以路程关于时间的函数是一个至多 $n$ 段的分段函数，且每一段都是线段。如果能求出每一段线段两端的坐标，就可以快速回答询问。基于此，有两种维护方式。 --- **解法一** 因为 A 只会跟着经过他的速度最快的人移动，所以只要一个人被超越，他就一定不产生影响。 使用平衡树维护所有人的相对位置。一旦某两个人的相对位置发生改变，那么一定有一个人被删除。 按照时间顺序模拟，平衡树上二分算出加入的人插入的位置，以及他和相邻两个人什么时候会撞在一起，将两个时刻加入优先队列。不断取出最小的相邻两个人撞在一起的时刻，判断事件是否会发生（因为其中一个人已经和其他人撞起来了），以及发生时刻是否小于下一个人加入的时间。将速度较慢（相撞时在前面）的人删除，加入速度较快的人和新的在他前面的人相撞的时间。 模拟过程中容易计算 A 在每个时刻的总移动距离。 时间复杂度 $\mathcal{O}(n\log n)$。 --- **解法二** 解法一需要平衡树，写起来很麻烦。 换一种思路，断环成链，将操场视为一条数轴。数轴上的位置 $x$ 表示 A 从起点出发移动 $x$ 单位距离。于是，加入一个人时，可以根据他加入的位置和 A 当前的位置算出他在数轴上的位置，于是他在数轴上的位置关于时刻 $t$ 可以写成一条射线 $kt + b$（$t\geq t_i$），其中 $k$ 是他的速度。由于加入一个人之后不会涉及到 $t_i$ 之前的时刻，于是可认为射线就是直线。 查询 A 的位置相当于查询若干条直线在某个点处的最大值，使用李超线段树维护即可。 时间复杂度 $\mathcal{O}(n\log n)$。 ### J. 绝不能忘记的事…… 枚举 `NFLSPC#6QIDONG` 在记录串三段中的位置，将问题分为两类：前面和中间。 关于后面，将所有复制串翻转，交换前后两部分并将 `Q` 和 `Z` 反转，做 `N` 在前面的问题即可。 --- **前面** 对于 `N` 出现在记录串前面的情况，`N` 也必须出现在记录串前面。 如果记录串恰等于某个复制串 `NAB`，那么与之匹配的复制串形如： - 恰等于 `NAB`。数量用 `map<string, int>` 计算。 - 等于 `NC*`，其中 `C` 是 `AB` 的 **非空真前缀**，即 `C` 非空且不等于 `AB`。数量用字典树计算。 - 等于 `N*D`，其中 `D` 是 `AB` 的 **非空真后缀**。类似使用字典树计算。 - 等于 `N**`。 否则，记录串的 `A` 可以取使得 `NA*` 数量最多的 `A`，记录串的 `B` 可以取使得 `N*B` 数量最多的 `B`。 --- **中间** 中间比前面相对简单一些。 因为记录串和复制串的每一段均非空，所以复制串的 `N` 只能在中间，这给前后两部分带来较大的自由。 如果记录串恰等于某个复制串 `ANB`，那么与之匹配的复制串形如： - 恰等于 `ANB`。数量用 `map<pair<string, string>, int>` 计算。 - 等于 `AN*` 或 `*NB`。数量用 `map<string, int>` 计算。 - 等于 `*N*`。 否则，记录串的 `A` 可以取使得 `AN*` 数量最多的 `A`，记录串的 `B` 可以取使得 `*NB` 数量最多的 `B`。 时间复杂度 $\mathcal{O}(L\log n + L\Sigma)$，其中 $L$ 是字符串总长，$\Sigma$ 是字符集大小。 ### K. 啊，忘记了。 首先考虑记录串未匹配任何前、中、后均确定的复制串的场合。此时，将与其匹配的复制串分类（其中，小写字母表示其是确定串，大写字母表示其忘了）： - `qZH`、`qzH`：这两类限制了记录串拥有某个前缀，称作 `a*` 的前缀类。 - `QZh`、`Qzh`：这两类限制拥有某个后缀，称作 `*b` 的后缀类。 - `qZh`：这类限制同时拥有某个前缀和某个后缀，称作 `a*b` 的前后缀类。 - `QzH`：这类限制拥有某个中缀，称作 `*m*` 的中缀类。 - `QZH` 完全没有限制，可匹配任何记录串。 - `qzh` 是前中后均确定的复制串，在这种场合不需考虑。 于是我们只需考虑 `a*,*b,a*b,*m*` 四类即可。 然后发现，对于前后缀的限制，我们只需确定记录串中最长的前缀 `A` 和最长的后缀 `B`，然后所有 `a*`（其中 `a` 是 `A` 的前缀）、`*b`（其中 `b` 是 `B` 的后缀）、`a*b`（其中 `a` 是 `A` 前缀、`b` 是 `B` 后缀）都能产生贡献。同时，我们可以将所有 `*m*` 塞在 `AB` 之间。此时所有的 `*m*` 都可以产生贡献。 于是我们只需找到最优的 `A,B` 即可。 对于 `a*,*b,a*b` 三类，建立前缀 trie 树和后缀 trie 树，一对 `AB` 对应了前缀树上的一条路径和后缀树上的一条路径，`a*` 是前缀树上一个点、`*b` 是后缀树上一个点、`a*b` 是前缀、后缀上一对点。`AB` 对应路径上所有点都能产生贡献。 考虑对于前缀树上每个点，维护以其作为 `A` 时，后缀树上每个点作为 `B` 时的答案。这可以通过在前缀树上扫描，并维护一棵以后缀树上点为下标的线段树进行。 `a*` 意味着在前缀树上一棵子树内的答案全体增加一，`*b` 意味着后缀树上一棵子树的答案全体加一：这两个是容易的。`a*b` 相当于在前缀树上扫描到某个点时，在它的子树中的流程有后缀树上一棵子树的答案全体加一。其可以被拆成在进入子树时增加、在离开子树时减少，而增加、减少就可以用上述的线段树维护。 ------ 然后就要考虑匹配了前中后均确定的串的场合。我们可以枚举这个串（记作 `s`），仍然考虑分类讨论每类串的贡献： - `a*`：如果 `a` 是 `s` 前缀则产生贡献。 - `*b`：如果 `b` 是 `s` 后缀则产生贡献。 - `a*b`：`a` 是前缀、`b` 是后缀产生贡献。需要注意的是，`a,b` 不能重叠。 - `*m*`：`m` 是子串。 - `QZH` 仍然直接算答案。 - `qzh` 要用哈希或 trie 算出 `s` 出现几次。 于是我们仍然只需考虑前四类。 前两类直接在前缀 trie、后缀 trie 上统计即可。第三类介绍两种方法： - 法一：直接使用前述的线段树，但是这样 `a,b` 出现重叠的场合也会被计算。因此，还要扣除这种情况：但这是简单的，我们可以枚举 `a*b`，然后找到出现重叠的场合（此时有 `a` 的一个后缀等于 `b` 的一个前缀，也即其是 `b#a`（其中 `#` 是占位符）这个串的 `border`，可以使用 KMP 或哈希找到），然后用哈希表示出此时的串的哈希值扔到桶里，然后对于 `s` 寻找这个桶里的计数即可。 - 法二：对于 `s`，枚举 `s` 的一个前缀作为 `a`（其为前缀 trie 上一个节点），然后考虑其对应的 `b`（为后缀树上一条路径）。在前缀树上的这个节点处，挂了很多 `a*b` 的对，所以应该把此处挂着的 `a*b` 扔到线段树上作子树加，然后后缀树上单点求和即可。这个做法需要把询问离线，在前缀树上每个节点处统计所有与它有关的答案。 最后，第四类涉及到这样一个问题： - 给定若干模板串。给定若干询问，每次给定询问串，询问有多少个模板串在询问串中至少出现一次。 存在一种比较复杂的后缀数组解法，但是这里我们使用一种比较简洁的 AC 自动姬解法： - 将模板串建 ACAM，然后询问串在上面跑，其跑的流程中访问了若干节点。这些节点在 fail 树上形成的虚树内部节点，统计其中包含多少个模板串即可。 - 这可以通过按照 dfn 序排序后，求出相邻节点 LCA 来统计答案。 令 $S=\sum s_i$，则复杂度 $S|\Sigma|+S\log S$，其中 $|\Sigma|$ 是字符集大小。 ### L. 等差数列 将 $(i, a_i)$ 抽象成点，则等差数列对应的直线需要在所有点的非严格上方，也就是所有点形成的上凸包上方。 可以用直线上所有点的纵坐标减去 $\sum a_i$ 计算答案，后者是定值，需要最小化前者。 如果直线没有经过任何点，那么将它向下平移 $1$ 依然合法。于是直线一定经过至少一个点。如果这个点偏左，那么斜率越小越好，相当于它的右切线；如果这个点偏右，那么斜率越大越好，相当于它的左切线，但注意斜率不能超过 $0$，以及并不一定能取到切线：公差必须为整数。 时间复杂度 $\mathcal{O}(n)$。 代码更短但复杂度更劣的解法：容易证明答案关于斜率单谷，于是对斜率三分即可。时间复杂度 $\mathcal{O}(n\log V)$。