UNR #6

· · 个人记录

D1T1. 面基之路

当 hehe 蚤和网友面基成功时，网友可以跟着 hehe 蚤一起走。因此，任何面基方案必然可调整为最后一个时刻 hehe 蚤和所有网友处于同一位置的情况。

直接枚举每条边 (u, v)，检查它对答案带来的贡献。设第 i 个人到 u 的最短路为 d_{i, u}，则 i 在 (u, v) 这条边产生的贡献为左端为 d_{i, u}，右端为 d_{i, v} 的形如山峰（而非山谷）的折线 Z_i，我们希望求 \min\limits_{x \in [0, w_{u, v}]} \max\limits_{i = 0} ^ k Z_i(x)。

因为每条折线仅有至多一个顶点，所以 \max Z_i 被 \mathcal{O}(k) 个顶点划分成若干段，每一段形如若干斜率为 \pm 1 的直线的 \max，最小值容易求出。

时间复杂度 \mathcal{O}(nk ^ 2 + mk\log m)，可以扫描线将 n k ^ 2 优化至 nk\log k。代码。

D1T2. 机器人表演

你出的好，你出的好啊！

容易设计出状态 DP f_{p, i, j, k} 表示当前匹配到最终串 T 的第 p 位，使用了 i 个 0，j 个 1 且匹配到原串 S 的第 k 位的方案数。因为 p = i + j + k，状态仅有 \mathcal{O}(nt ^ 2) 种。

考虑转移。初始想法是 贪心匹配 S，即枚举 T_{i + 1} = 0 / 1，若 T_{i + 1} = S_{k + 1}，则 k \gets k + 1，否则若 T_{i + 1} = 0 且 i < t，则 i\gets i + 1，否则若 T_{i + 1} = 1 且 j < i，则 j\gets j + 1。

问题在于这样贪心匹配不一定最优，因为对于某个 T_{i + 1} = 0，我如果令 i\gets i + 1，就可以额外将 j 的限制放宽，放更多的 1，例如 n = t = 1，S = 0，则上述 DP 无法统计到 T = 010。

考虑 反悔，即撤销 S 已经匹配的一些位置用于补充 i 使得 i > j。考场上猜的结论是对每个 k，找到最大的 q 满足 S_{q + 1} = 0（用于填补 i 的空缺），S[q + 2, k] 是合法 01 串前缀，记为 lft_k，则可以在 k 处撤销匹配至 lft_k 处，且 S[lft_k + 1, k] 全部投进 01 串匹配。

不会证明，但后来发现和官方从另一种角度考虑的题解本质相同。先给出转移式，最后再说明这一点。对于 f_{p, i, j, k}，枚举 T_{i + 1} = 0 / 1，则

结论正确性的疑点在于： - 为什么 $S[lft_k + 1, k]$ 全部投进 $01$ 串匹配，而不是匹配到 $S$ 大于 $lft_k$ 的位置？ - 为什么 $S[q + 2, k]$ 是合法 $01$ 串前缀？因为 $S[q + 2, k]$ 是归并插入当前 $i = j$ 对应合法 $01$ 串，所以似乎不需要合法。 官方题解 $lft_k$ 的定义是最大的 $k' < k$ 且 $b_{k'} < b_k$ 的 $k'$，其中 $b$ 为将 $S$ 的 $0$ 看成 $1$，$1$ 看成 $-1$ 的前缀和，然后证明了 $S[lft_k + 1, k]$ 是合法 $01$ 串前缀，且 $lft_k$ 是 $S$ 新的最大匹配长度，即不存在 $K > lft_k$ 使得 $T[1, i + 1]$ 可以由 $S[1, K]$ 和合法 $01$ 串前缀归并得到，因而说明 $S[lft_k + 1, k]$ 需要全部投进 $01$ 串匹配。 考察两种角度，显然官方题解更加严谨和完备。我的做法属于是本末倒置，瞎猫碰上死耗子恰好正确了。 ### D1T3. [稳健型选手](https://uoj.ac/contest/77/problem/749) 不错的猫树分治练手题。 单组询问的 $\mathcal{O}(L\log L)$ 解法是经典问题，类似题目有 [UVA12260 Free Goodies](https://www.luogu.com.cn/problem/UVA12260)：设 $c_i$ 表示 $i$ 是否被选中，$b_i$ 表示 $c_i$ 的前缀和，则对于任意 $i\in [1, L]$ 均有 $b_i \leq \lceil \frac i 2 \rceil$。 因此，从前往后扫，每次往选中的数加入 $a_i$ 和 $a_{i + 1}$，但此时有 $\lceil \frac i 2 \rceil + 1$ 个数被选了，需要弹出最小的选中的数，容易证明反悔贪心正确。另一种思路是从后往前扫，每次往未被选中的数加入 $a_i$ 和 $a_{i + 1}$，并弹出最大的未被选中的数。两种思路分别支持开头扩展和结尾扩展，因此回滚莫队可以做到 $\mathcal{O}(n\sqrt n \log n)$，压位 Trie 可以通过。直接做的复杂度为 $\mathcal{O}(n ^ 2\log n)$，只有 [40 分](https://uoj.ac/submission/569175)。 既然支持开头插入和结尾插入，但无法快速合并，容易想到 **二区间合并** 即 **猫树分治**。 考虑合并两个区间 $[l, mid]$ 和 $[mid + 1, r]$ 时，左边没选的数必然不会重新选择，右边选择的数必然不会不选，但我们会取消选择左边一些选择的数，转而选择右边一些未选择的数。因此，维护左边选择的数集 $X$ 和右边未选择的数集 $Y$，二分找到分界点，即最大的 $k$ 使得 $X$ 第 $k$ 小的数小于 $Y$ 第 $k$ 大 的数，然后将 $X$ 前 $k$ 小的数删去，$Y$ 前 $k$ 大的数选上，即为答案。 主席树维护，离线询问将空间复杂度优化至 $\mathcal{O}(q + n\log n)$，时间复杂度 $\mathcal{O}((n + q)\log ^ 2 n)$。[代码](https://uoj.ac/submission/574669)。 ### D2T1. [小火车](https://uoj.ac/contest/78/problem/750) 非常好题目，英雄联盟，爱来自瓷器。 观察 $2 ^ n > p$ 的限制，容易想到用 $0/1$ 减去 $0 / 1$ 得到 $-1/0/1$。问题转化为找到两个 $0\sim n - 1$ 的子集 $S, T$，使得 $S \neq T$ 且 $\sum\limits_{i \in S} a_i \equiv \sum\limits_{i\in T} a_i \pmod p$，则 $b_i = [i\in S] - [i\in T]$ 即为一组合法方案。根据鸽笼原理，$2 ^ n$ 只鸽子飞进 $p$ 个笼子，必然存在两只鸽子飞进相同笼子，故必然有解。 问题在于如何找到这样的 $S, T$，赛时想了一年都没有想出来：如果要恰好找到 $S = T$，总枚举量为 $(2 ^ {40}) ^ 2$，无论如何 `meet-in-the-middle` 都无法减少枚举量到一个可以接受的范围。 那真的不能做了吗？当然不是。直接枚举 $S, T$ 没有用到 $2 ^ n > p$ 的性质，考虑利用这一性质优化算法。 设 $f_j$ 表示使得 $f(S) = \sum\limits_{i\in S} a_i = j$ 的 $S$ 的数量，问题即找出任意使得 $f_j \geq 2$ 的 $j$。若存在 $j \in [L, R]$ 满足 $f_j \geq 2$，称 $[L, R]$ 合法。 核心结论：对于任意 $[L, R]$ 的分割方式 $[L, mid]$ 和 $[mid + 1, R]$，必然存在至少一个区间 $[L, mid]$ 或 $[mid + 1, R]$ 合法。 因初始区间 $[0, p - 1]$ 合法，所以二分，每次将当前合法区间长度减半，$\log p$ 次后即可找到长度为 $1$ 的合法区间。故只需求使得 $f(S)\in [l, r]$ 的 $S$ 的数量。其相较于原问题枚举量减少了一半，总枚举量仅有 $2 ^ {40}$，mitm 可以快速求解。 求得 $j$ 后同样可 mitm 求出一组合法解，时间复杂度 $\mathcal{O}(2 ^ {n / 2}\log p)$。[代码](https://uoj.ac/submission/573542)。 ### D2T2. [神隐](https://uoj.ac/contest/78/problem/751) 这题出得很好，让人思维出新。 考虑最朴素的做法枚举每条边，询问次数 $n - 1$，很劣。 考虑 $n$ 较小时的做法，$n = 3$ 时我们必须询问每一条边，换言之，对于 $e_1, e_2$，必须： - 存在一次询问使得 $e_1\in E$ 但 $e_2\notin E$。 - 存在一次询问使得 $e_2\in E$ 但 $e_1\notin E$。 若不存在第一种询问，$e_2 = (u, v)$，剩下一个点为 $w$，则我们无法确定 $w$ 连向 $u$ 还是 $v$。 对任意 $n$ 运用上述结论，可知还原整棵树的必要条件为对于任意相邻两条边 $e_i, e_j$，存在一次询问使得 $e_i\in E$ 但 $e_j\notin E$，存在一次询问使得 $e_j\in E$ 但 $e_i\notin E$。因为我们不知道每条边的相邻情况，所以对于任意不同的两条边均需满足上述性质。 设第 $i$ 条边属于集合 $S_i$ 的询问，即 $S_i = \{q\mid e_i\in E_q\}$，则上述性质可表述为对于任意 $i\neq j$，$S_i\subsetneq S_j$ 且 $S_j\subsetneq S_i$。如果构造出 $E_1\sim E_k$，也容易通过询问结果得到 $T$。将所有无序点对 $(u, v)$ 按照它们连通的次数 $cnt_{u, v} = \sum\limits_{i = 1} ^ k [E_i : u\rightsquigarrow v]$ 从大到小排序，做最大生成树即可：根据性质，非树边 $(u, v)$ 的权值严格小于 $u$ 到 $v$ 简单路径上所有边的权值。 尝试构造 $n - 1$ 个两两互不包含的集合。如果限制了 $X$ 次询问，最优方案为选择 $0\sim 2 ^ X - 1$ 所有 $\mathrm{popcount} = \dfrac X 2$ 的数。$\dbinom {14} 7= 5040 \geq 1999$，$\dbinom {20} {10} = 184756 \geq 131071$，可行。瓶颈在于 $n ^ 2\log n$ 的时间复杂度。 考虑利用构造出的 $S_i$ 的性质优化复杂度：每条边仅出现 $\dfrac X 2$ 次。 还原树的交互题有一个非常好用的技巧：**剥叶子**。每个叶子恰在 $\dfrac X 2$ 次询问中为孤立点，且条件充要，据此可不断剥掉 $T$ 的叶子。 设最后一个被剥掉的节点为 $R$，上述过程给予我们 $T$ 在以 $R$ 为根时的拓扑序，考虑按拓扑序还原每个点的父亲。 设 $x$ 的父亲为 $fa$，容易发现恰有 $\dfrac X 2$ 次 $x$ 与 $fa$ 不连通，即所属连通块其它点拓扑序均在 $x$ 之后；同时恰有 $\dfrac X 2$ 次 $x$ 与 $fa$ 连通，且根据性质，$x$ 所属连通块 $C_1, C_2, \cdots, C_{X / 2}$ 的交恰好仅包含 $x$ 和 $fa$。 关于树上连通块，有一个很好的性质是若干连通块相交，若交集非空，则交集深度最小的点为某连通块深度最小的点：若非，考虑交集深度最小的点 $u$，因其不为任何连通块深度最小的点，故 $u$ 的父亲同样属于交集，矛盾。 因此，只需求出 $C_1\sim C_{X / 2}$ 每个连通块深度最小的点中深度最大的那个，即为 $x$ 的父亲。容易维护。 时间复杂度 $\mathcal{O}(n\log n)$。[代码](https://uoj.ac/submission/574945)。 ### D2T3. [Border 的第五种求法](https://uoj.ac/problem/752) 咕了，如果进集训队就更。 UPD：来写了。 感觉思想挺简单的，但是是未曾设想的道路。 对 $s$ 建出 SAM，则 $B$ 是 $s[l, r]$ 的 border 当且仅当： - $B$ 是 $s[l, r]$ 的前缀。 - $B$ 在 link 树上是 $s[1, r]$ 的祖先。 因为 $s[l, r]$ 的所有前缀形成 DAWG 上一条路径，考虑 DAG 剖分将路径拆成 $\log n$ 条时间戳连续的重链，则问题转化成 $\mathcal{O}(q\log n)$ 次询问 $s[1, r]$ 到根的路径上时间戳落在某区间的节点的权值和，而 $i$ 的权值即 $f_{|\mathrm{endpos}(i)|}$。 - 如何拆重链：容易求出当前节点 $i$ 到重链末尾形成的字符串在原串上的任意对应下标 $[l, r]$。不妨设当前要匹配 $s[x, y]$，则当前重链匹配长度即 $|lcp(s[l, r], s[x, y])|$，容易 SA 或者 SAM 求出。 二维数点，离线后在树上扫一遍，用 BIT 维护单点修改区间查询。时间复杂度 $\mathcal{O}(n\log n + q\log ^ 2 n)$，[代码](https://uoj.ac/submission/579867)。