MOCK NOIP 20221112 日志

仍然是中规中矩的一场模拟赛。前两题正解，第三题暴力，第四题不会。

简略题解

A – 激光

考虑是否有两条及以上双向连边，若是则无解，若有一条则枚举要将哪一侧的发射器旋转到哪一方向。简单模拟即可。

B – 碰撞

这类数轴上带标号小球相撞的题目都有一个经典套路：两球相撞调转方向时，我们不认为是球本身转向，而认为两球仍然保持原方向运动，而其编号交换。

先不考虑标号。固定一数 $t=\frac{t_0}{2}\space(t_0\in \mathbb{N})$。对于每个球，我们自然可以计算出在上述转化下经过 $t$ 单位时间后它与对向球的相撞次数 $c_t$。找到使得 $c_t\geq l$ 的最小的 $t$。可以计算每个“无标号球”在 $t-1$ 时刻的绝对位置。同时易知，所有“编号”的相对位置是固定的，故而可以根据相对位置为每个 $t-1$ 时刻后的“无标号球”赋上标号。接下来采用“多路合并”的方法，以每个向右运动的“无标号球”为据点，逐个模拟相撞事件即可。

时间复杂度 $\newcommand\bigO{\operatorname{O}}\bigO(n\log n)$。

C – 消失

D – 排列

这题还真没法写暴力。

考虑二分答案 $k$。我们逐位填写排列 $p$。记一个动态更新的值 $\newcommand\lmt{\operatorname{lmt}}\lmt_i$，表示编号为 $i$ 的区间从目前已经填好的 $p$ 来看应当在第 $\lmt_i$ 位或以前填入 $p$。换句话说，当已经填写完成的 $p$ 的前缀中，没有任何区间和 $i$ 号区间有交，则 $\lmt_i=n$；否则，记与它有交的区间中，处在 $p$ 的最靠前的位置的那一个的位置为 $q$，则恒有 $\lmt_i=\min\{q+k,n\}$；如果目前填了前 $\newcommand\pos{\operatorname{pos}}\pos$ 位，我们决定在 $p$ 的下一位 $p_{\pos+1}$ 填写 $i$ 号区间，则令 $\lmt_i=\pos+1$ 且不再变化。

引理

给定 $k$，存在一个答案不大于 $k$ 的合法排列，当且仅当逐位填写 $\pos=1,2,\cdots,n$ 的任何时刻，均有 $\forall q\in\{1,2,\cdots,n\},q\geq\sum_{i=1}^{n}[\lmt_i\leq q]$，且完成 $p_{\pos}$ 填写的一瞬，有 $\pos=\sum_{i=1}^{n}[\lmt_i\leq \pos]$。

这条引理是很容易理解的：由上面的定义可以看出，$\lmt_i$ 是只减不增的。因此对于同一个位置 $q$，在填写的过程中，$\sum_{i=1}^{n}[\lmt_i\leq q]$ 是只增不减的；一旦某个位置 $q$ 出现了“要求在 $q$ 及之前填写完第 $i$ 个区间”的要求超过 $q$ 条，则显然没有合法排列。否则，如果最终填写完$\pos=1,2\cdots,n$ 时，均满足引理的最后一条要求，那么显然有合法排列。

接下来讨论怎么合理地选择在 $\pos$ 填写的区间。假如我们填写区间 $i$，那么有 ${\lmt_i}’=i$，则有 $\forall q\in [\pos,\lmt_{i}),(\sum_{j=1}^{n}[{\lmt_j}’\leq q])’=(\sum_{j=1}^{n}[\lmt_j\leq q])+1$（多了一个区间，它的 $\lmt$ 跑到了 $q$ 的前头）；同时，所有还未填写的与其有交的区间 $j$，都将有 ${\lmt_j}\leftarrow\min\{n,\pos+k\}$。

则一定存在一个位置 $t\leq n$，满足 $\forall q\in [\pos,t),q>\sum_{j=1}^{n}[\lmt_j\leq q]$，且 $t=\sum_{j=1}^{n}[\lmt_j\leq t]$。（当然，要是现在已经存在一个位置 $q$，满足 $q<\sum_{j=1}^{n}[\lmt_j\leq q]$，那自然可以判断无合法解。）于是乎，根据上一段提到的“$\lmt_i$ 前移”造成的后果，我们只能选择区间 $i$，满足 $\lmt_i\in[\pos,t]$，否则一定会出现一个位置 $q\geq t$，在 $i$ 号区间填进 $p$ 以后，$q<\sum_{j=1}^{n}[{\lmt_j}’\leq q]$。

在所有满足这一条件的区间里，我们选择的区间 $i$ 应当满足以下条件：

• 不存在未填写的区间 $j$，满足 $r_j<l_i$；
• 尽可能使得与 $i$ 有交的未填写的区间 $j$ 的数量更少（前移更少的 $\lmt_j$），使得随后的填写过程有更宽松的约束。

可以发现，总是选择右端点最小的区间，是满足上述条件的最优解。简单证明：对于所有位置都采用这一策略，条件一立刻得到满足；而在同一坐标 $\pos$ 上，满足条件一的所有可用区间应当是两两有交（否则有一前一后两个没有交的区间）且左右端点最小的，无论选择其中哪个，所有其他未选的可用区间通通执行 $\lmt_j$ 左移操作。于是选择右端点最小的，可以与更少的不可用区间产生交集，进而对后续决策产生更积极的影响。

使用线段树在 $q=1,\cdots,n$ 处记录 $q-\sum_{i=1}^{n}[\lmt_i\leq q]$，同时维护上式的（线段树）区间最大值，可以利用线段树上二分的技巧找到上文所述的 $t$；同时将（题目所指）区间 $i$ 挂载到 $\lmt_i$ 处，就可以（线段树）区间查询 $r_i$ 最小的（题目所指）区间。

复杂度 $\bigO(n\log^2n)$，实现时及时判掉无解、采用优先队列延迟删除等技巧，可以提升效率。