2024.11.20 模拟赛
Whitely
·
·
题解
2024.11.20 模拟赛
A
给定 a_{1\dots 2n} 和 m 满足 a_i\in [0,m-1]，你需要将这 2n 个数中每两个分一组分出 n 组，要求每组 (a_i+a_j)\bmod m 的最大值最小，求这个值，n\le 10^5,m\le 10^9。
Sol
先对 a_{1\dots 2n} 升序，对于一种匹配方式，一对匹配 (i,j) 若满足 a_i+a_j<m 则在 i,j 之间连蓝边，否则连红边，你想让红边尽量多。
你发现必定存在一种最优匹配方式满足所有同色边包含，异色边不交，证明可以调整法。这样相当于有一个分界点 i，分界点之左 (1,i-1),(2,i-2),\dots 均为蓝边，分界点及之右 (i,2n),(i+1,2n-1),\dots 均为红边。
你发现 i 越靠右越易于满足红边的要求，越靠左答案越优，则二分最左合法 i，O(n\log n)。
B
给定 n,m,a_{1\dots n},b_{1\dots n}，由此生成一个完全图，i\to j 边权 (a_i+b_j)\bmod m，求 1\to n 最短路，n\le 2\times 10^5,m\le 10^9。
Sol
特殊图最短路，考虑优化建图。这类由点权生成边权的特殊图，考虑对每个点建一个虚点，虚点按点权（本题中 b 值）升序排，保证虚点之间边权为正。虚点之间连点权差分，这样每个点向第一个虚点连对应边权，本题中 a_i+b'_1，这样可以表示出这个点到所有虚点的边，同时虚点向对应点连 0。
本题中还有 \bmod m，每个点再向首个 a_i+b'_j\ge m 的虚点 j 连 a_i+b'_j-m 即可，最后跑 dij 可以 O(n\log n)。
C
有 1\times n 棋盘，每个格子有颜色，颜色共 m 种。棋盘上有一个棋子，带有某种颜色，操作者每次可以将棋子向左移动若干格，或者在棋子颜色和其所在格子不同的前提下将棋子颜色改为格子颜色，不能操作者输。
#### Sol
设 $sg_{i,j}$ 表示当前处于 $i$ 格，棋子颜色为 $j$，这样状态的 $sg$ 值，则边界状态 $sg_{1,i}=[i=c_1]$，其余：
$$
sg_{i,j}=
\left\{
\begin{array}{**lr**}
\operatorname{mex}(sg_{1\dots i-1,j}) & j=c_i\\
\operatorname{mex}(sg_{1,\dots i-1,j},sg_{i,c_i}) & i\neq c_i\\
\end{array}
\right.
$$
所求即为所有棋子初始状态 $sg$ 值的异或，非 $0$ 则必胜。
模拟这个过程，发现 $sg_{i,j}$ 的值必定在 $i,i-1,x_i$ 三个数中取，且 $sg_{i,c_i}$ 总是会独占三者之一。其中 $x_i$ 是一个和 $i$ 相关的数。
观察发现结论：$\forall i,\exist S\subseteq\{1,\dots ,m\},x_i<i-1$，满足：
- $\forall p\in S,\{sg_{1\dots i-1,p}\}=\{0,\dots,i+1\}-\{x_i\}$。
- $\forall p\notin S,\{sg_{1\dots i-1,p}\}=\{0,\dots,i-2\}$。
证明考虑归纳法：
- 若 $c_i\in S_i$，$S_{i+1}=S_i-\{c_i\},x_{i+1}=x_i$。
- 否则，$S_{i+1}=\complement S_i-\{c_i\},x_{i+1}=i-1$。
利用这个可以在知道 $S_{i},x_i$ 的情况下 $O(1)$ 查询 $sg_{i,j}$，原问题线性。
### D
对于序列 $a_{1\dots 2n}$，对 $i\le n$ 定义 $rk_i=\sum_{j=i+1}^n[a_j\le a_i]$，$i>n$ 则 $rk_i=\sum_{j=n+1}^{i-1}[a_j\le a_i]$，定义 $a$ 合法当且仅当 $rk$ 回文，求给定序列 $a_{1\dots n}$ 的最大回文子段长度，$2|n,n\le 1\times 10^5$。
#### Sol
朴素 $O(n^2\log n)$ 是枚举子串中心在 $i$ 和 $i+1$ 之间，$O(\log n)$ 向外拓展每一位。考虑如何不拓展每一位判断一个串是否合法，考虑哈希，子串中心如上时设 $j$ 位哈希值为 $h_j$，则：
1. $j\le i$ 时 $h_j=\sum_{k=j+1}^{i}[a_k\le a_j]\cdot P^{i-j}$。
2. $j>i$ 时 $h_j=\sum_{k=i+1}^{j-1}[a_k\le a_j]\cdot P_{j-i-1}$。
对 $[i-j+1,i+j]$ 这一段判断，只需 $\sum_{k=i-j+1}^ih_k=\sum_{k=i+1}^{i+j}h_k$。
考虑快速计算这两个式子，想到对每一位 $k$ 将 $h_{k,i}$ 做一些处理使之和 $i$ 的关系减弱，考虑分块，可以做到 $O(B\log n)$ 求出一个式子，过程较为复杂，平衡复杂度可以 $O(n\sqrt{n\log n})$。
考虑进一步优化，从根号复杂度判断一个串是否合法入手，你尝试让不同的关于串是否合法的询问之间产生联系，考虑整体上先二分长度，再做滑动窗口判断这样长度的串是否存在合法，这样只需要每次删除一个字符加入一个字符，可以做到 $O(n\log^2n)$。