# T1 给定 $N$ 条水平线段（“防壁”）和 $M$ 次竖直射线（“镭射”）的位置： - 第 $i$ 条防壁位于高度（行）$y=i$，初始覆盖横坐标区间 $[A_i,B_i]$。其长度固定为 $B_i-A_i+1$，只能沿水平方向移动。 - 第 $j$ 次镭射在横坐标 $x=P_j$ 处从上到下发射。要求：在**每次**镭射发射时，镭射都要**穿过每一条防壁**。等价地说，在第 $j$ 次发射时，每条防壁的当前覆盖区间都必须包含 $P_j$。允许的操作：在开始前以及任意两次发射之间，你可以把每条防壁在水平方向上移动若干格；每向左或向右移动 $1$ 格计为 $1$ 次移动。目标：**对每条防壁分别**计算为了满足上述要求所需的**最少移动次数之和**（从初始位置出发、跨越全部 $M$ 次发射的累计移动量）。 - $1\le N,M\le 2\times10^5$ - $0\le A_i\le B_i\le 10^9$ - $0\le P_j\le 10^9$ 3s, 256MiB ::::info[题解] # QOJ1215. Walls 题解首先显然贪心地移动区间（即每次移动步数最小）是不劣的，直接模拟可以做到 $O(nm)$ 第 $i$ 次攻击记为 $a_i$，把一个防壁叫做一个区间 $[l, r]$。我们先**只解决一个区间**的答案。先抛去麻烦的边界情况，即我们默认询问的区间的左端点与第一次攻击的位置相同。考虑直接做没有什么好的思路，考虑这类题常见的解题思路——优化 $a$ 数组的弱相关元素。但是 $a$ 数组与询问区间的长度息息相关，我们不妨暂时**把询问区间的长度看成极小**。略微思考一下发现，若对于满足 $\forall i\in [2, n-1], a_{i-1} < a_i < a_{i+1}$ 条件的攻击 $i$，从 $a_{i-1}$ 移动到 $a_{i+1}$ 时一定会经过 $a_i$——因为区间的移动时连续的。同理，对于 $\forall i\in [2, n-1], a_{i-1} > a_i > a_{i+1}$ 的攻击也可以忽略不计。那么在删去满足上面条件的元素后，显然剩下的 $a$ 数组形如 $a_1 > a_2 < a_3 > a_4 \ldots$ 或者 $a_1 < a_2 > a_3 < a_4 \ldots$。发现如果 $|a_i - a_{i+1}| 若既不存在 $a_{i-1}$ 也不存在 $a_{i+2}$，那么我们不删除 $a_i$ 和 $a_{i+1}$，此时只剩两个 $a_i$，可以暴力模拟。 > 若只存在 $a_{i-1}$，则删除 $a_{i+1}$，因为到达 $a_i$ 与到达 $a_{i+1}$ 等价，且从 $a_{i-1}$ 到 $a_i$ 时**左端点**必须经过 $a_i$。 > 若只存在 $a_{i+2}$，则删除 $a_i$，因为从 $a_{i+1}$ 到达 $a_{i+2}$ 时**左端点**一定经过 $a_i$。不能删除 $a_{i+1}$ 的原因是从 $a_i$ 到 $a_{i+2}$ 不一定满足**左端点**一定经过 $a_i$。现在问题变成了 $\forall i,|a_i - a_{i+1}|\geq r-l$，那么答案就是先将区间移到 $a_1$，然后答案加上 $\sum_i[|a_i - a_{i+1}|-(r-l)]$。我们对于一个区间做到了除了删 $a_i$ 部分的 $O(1)$。显然长度大的区间的删除点集合包含长度小的删除点集合，我们可以把询问按照长度排序然后每次删点继承上次删点即可做到均摊 $O(\log n)$。时间复杂度 $O((N+M)\log M)$。 :::: --- # T2 给定长度为 $N$ 的序列 $S=(S_1,S_2,\dots,S_N)$，每个元素满足 $1\le S_i\le C$。允许进行一次如下操作： * 选择一个子串区间 $(i,j)$（$1\le i\le j\le N$），将 $S_i,S_{i+1},\dots,S_j$ 按升序排序后替换原位置，得到新序列 $S'$。在得到的 $S'$ 中，计算其最长回文子串（连续）的长度。你的任务是：在所有可能的选择 $(i,j)$ 中，最大化该最长回文子串的长度，并输出该最大值。 $1\le N,C\le 3000$，$1\le S_i\le C$。 4s, 256MiB ::::info[题解] # QOJ1210. AAQQZ 题解选择某个排序区间后，我们围绕回文中心处理这部分。我们先 $O(n^2)$ 预处理出 `f[i][j]`，表示以 $i,j$ 为左、右端点，在原串上再向外扩展匹配能匹配多少位置。形式化地说，是最大的 $k$ 满足 $\forall x\in[0,k-1], S_{i-x}=S_{j+x}$。此时对于一个固定的回文中心分为 $6$ 种情况。 1. 回文区间和排序区间不交 2. 回文中心被包含在排序区间，且**不**在排序区间排序后的值最小/大段（也是排序区间中最左/右的相同值构成的连续段） 3. 回文中心被包含在排序区间，且在排序区间排序后的值最小/大段，且回文区间包含排序区间 4. 回文中心被包含在排序区间，且在排序区间排序后的值最小/大段，且回文区间**不**包含排序区间 5. 回文中心不被包含在排序区间，且回文区间包含排序区间 6. 回文中心不被包含在排序区间，且回文区间**不**包含排序区间情况 $1$ 时，答案就是在不排序下的最长回文子串。对于情况 $2$，发现答案就是该回文中心在同值连续段进行扩展，能扩展到的最大长度。这种情况可以通过将整个字符串排序，那么此时最长同值连续段的长度就是所有回文中心和排序方案在满足情况 $2$ 下的最长回文子串。对于情况 $3/4$，发现回文中心不在**排序区间排序后的值最小/大段**的中点是严格劣的。不妨令回文中心在排序区间最小段，排序区间其余部分在回文中心右部。先解决情况 $4$，先把中间的**排序区间排序后的值最小段**扔掉，发现对于已经排序完的右部分，能够匹配的合法的左部分只能是一个单调不增的连续段。先将这个连续段 $O(n)$ 暴力算出来，然后逐渐扩展右部。我们称左部为需求 `Lcnt`，右部为供给 `Rcnt`，`Lcnt[i]` 代表左部有几个 $i$，`Rcnt` 同理。设当前右部扩展到了 `k`，那么首先需要匹配**右部值域上的前缀区间**可用当且仅当满足 $\forall i,\text{Lcnt}[i]=\text{Rcnt}[i]$。发现一旦 $\exist i, Lcnt[i]i$ 的前缀部分都**没救**了，此时应当对值域进行截断操作。可以双指针维护**右部值域上的前缀区间**，做到 $O(n)$。再解决情况 $3$，发现这种情况的回文区间就是在【不存在**没救**的部分的】情况 $4$ 的回文区间 $[L,R]$ 接上【`f[L-1][R+1]` 所代表的回文部分】得到的回文区间。（如果存在**没救**的部分，那么【`f[L-1][R+1]` 所代表的回文部分】就因为中间的【**没救**部分所带来的未匹配空位】而无法接上）对于情况 $5/6$，这种情况就是先将回文中心的【`f[i][i]` 或 `f[i][i+1]`（取决于回文区间长度的奇偶性）所代表的回文部分】扔掉，再做一遍情况 $3/4$ 在 “先把中间的**排序区间排序后的值最小段**扔掉” 后的步骤。枚举完回文中心后，所有情况的分讨都是 $O(n)$ 的。总时间复杂度 $O(n^2)$。 :::: --- # T3 给定 $N$ 个区间事件与一扇门的开关规则，时间轴为 $[0,M]$。在时刻 $0$ 与时刻 $M$，所有人都在室内。 * 第 $i$ 个人在时刻 $S_i$ 离开，在时刻 $T_i$ 回来，满足 $0

最新文章

常用标签