JOI Open 2022 题解

写笔记时发现有三道连着的题！！！顺便发出来。 #### JOI Open Seesaw 在一个数轴上，初始 $a_1,a_2\dots a_n(a_1<a_2\dots <a_n)$ 的位置上有一个砝码。 每一次你可以拿走 $a_1$ 或 $a_n$。 令 $m_i$ 表示还剩 $i$ 个砝码时的 $\dfrac{\sum a_j}{i}$，最小化 $\max\{m_i\}-\min\{m_i\}$。 $n\leq 2\times 10^5$。 结论，答案区间 $[l,r]$ 合法当且仅当对于任何长度 $i$，存在一个长度为 $i$ 的区间的 $\sum\dfrac{a_j}{i}$ 在 $[l,r]$ 之间。 如果不存在，那么一定不合法。 否则，令 $a_j$ 为长度为 $i$ ，起点为 $j$ 的区间的平均值，$b_j$ 为长度为 $i+1$，起点为 $j$ 的区间的平均值，那么一定满足： $a_1<b_1<a_2<b_2\dots$。 那么可以通过调整，使得选的位置是可以由上一次变化而来的。 我们还知道，长度为 $n$ 的区间是一定被选的。 那么对于其他长度，可以贪心的选全局平均值在区间内的前驱后继，然后就枚举全局最小值，维护一下全局最大值。 总复杂度 $O(n\log n)$。 #### JOI Open Giraffe 给定排列 $p$，你需要构造排列 $q$，满足对于任意的一个区间 $[l,r]$，下面两个条件不能同时满足： $1.$ 存在 $l<x<r$ 满足 $q_x>q_l,q_x>q_r$。 $2.$存在 $l<x<r$ 满足 $q_x<q_l,q_x<q_r$。 最小化 $\sum [p_i\neq q_i]$，保证 $p$ 随机生成。 $n\leq 8000$。 可以发现最大值和最小值不能同时在中间，可以递归进一个子问题。 可以把点看成 $(i,p_i)$，假若最大化 $\sum [p_i=q_i]$，那么令 $f_{l,r,x}$ 表示区间 $[l,r]$，最大值为 $x$ 的答案，相当于平面上的一个矩形，转移容易 $O(1)$。 发现最终的 $\sum[p_i=q_i]$ 不是很大，实际上是 $O(\sqrt n)$ 级别的，可以考虑 LIS+LDS。 初始我们有矩形 $((0,0),(n+1,n+1))$，做 $ans$ 次，每次尝试扩展到一个新的，尽量大的被原来矩形包含矩形，满足其中的四个角存在至少一个有点。 可以维护 $f_{i,0/1/2/3}$ 表示第 $i$ 个点四个方向的矩形边长可取的最大值，直接这样递归就是 $O(n^2\sqrt n)$ 的。 crn 的小优化是时刻只保留前 $1000$ 大的矩形。 #### JOI Open Schoolroad 给定一个带权无向图，判断 $1\sim n$ 是否存在两条长度不同的简单路。 $n,m\leq 2\times 10^5$。 先假设 $1,n$ 同在一个点双里。 我们发现，若一个不为 $1,n$ 的点的度为 $2$，那么可以直接缩掉这个点。 如果缩出了重边显然若权值相同直接删去，权值不同那么一定不合法。 若最后的图剩下了除 $1,n$ 以外的点，那么一定存在形如，$S\rightarrow x_1,x_1\rightarrow T,S\rightarrow x_2,x_2\rightarrow T,x_1\rightarrow x_2$ 的子图，这显然不合法。 不在一个点双时可能在缩的时候出现不连通。 先求出最短路 DAG，定义从 $1$ 出发的最短路 DAG 和从 $n$ 出发的最短路 DAG 的交。 假如存在从 $1\sim n$，且不在这个最短路 DAG 上的路径，那么显然存在长度不同的路，判断这个只需要一个并查集，将每条不在 DAG 上的边在并查集上连接，如果有多于两个在 DAG 上的点连通那么一定有一条路。 否则，对于每一个在这个最短路 DAG 上的点，存在 $1\rightarrow x\rightarrow n$ 的路径，那么还是项上面点双的做法。 其实这个判定就是 二端串并联图。