Codeforces Round 1024 (Div. 1) 部分题解

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

A. Mex in the Grid

题意

构造一个 $n\times n$ 的矩阵，填入 $0$ 到 $n^2-1$ 各一次，最大化“所有子矩阵的 $\operatorname{mex}$ 的和”。 $n\leq 500$ 。

题解

转而考虑统计“ $\operatorname{mex}\geq i$ 的子矩阵个数”，最大化的目标即为这个东西求和。这个个数可以考虑 $<i$ 的数的 Bounding box，个数为其上下左右各自空白宽度的乘积。不难猜想这个 Bounding box 在增长时需要维持接近正方形、并放在网格中心，具体证明略。构造之一是螺旋形排数。

B. Quartet Swapping

题意

给定一个长度为 $n$ 的初始排列，一次操作可以选定 $i$ ，交换 $a[i]$ 和 $a[i+2]$ 、 $a[i+1]$ 和 $a[i+3]$ 。问操作能得到的字典序最小的排列。 $n\leq 2 \times 10^5$ 。

题解

每次操作维持逆序对奇偶性不变、维持原来在奇数位的数在奇数位、偶数位的数在偶数位。对于奇数位和偶数位分别排序，得到的可能不符合逆序对奇偶性的要求，此时交换最后一个数和倒数第三个数即可。时间复杂度 $O(n\log n)$ （实际可以优化到 $O(n)$ ）。

C. 23 Kingdom

题意

给定序列 $a$ ，要求序列 $b$ 满足 $b_i\leq a_i$ ，求【对于每个数，其在 $b$ 中最后出现的位置减在 $b$ 中第一次出现的位置的和】的最大值。 $n\leq 2\times 10^5$ 。

首先，每个数只有其第一次出现和最后一次出现需要关心。为了最优，每个数的这个区间必须两两相交（否则不妨设 $x\leq y$ ， $x,x,y,y$ 可以被优化为 $x,\cdot, \cdot, x$ ）。因此会存在一个分界点，分界点之前填入 $1$ 开始的尽可能多的连续的数（位置尽可能靠前），分界点之后填入 $1$ 开始的尽可能多的连续的数（位置尽可能靠后），分界点两边的优化是独立的。两边的问题是一样的（只需要翻转序列），我们只考虑分界点之前的部分，尝试对每个前缀都求出答案。

从前往后扫前缀里的元素，同时维护当前能放进去的最大数、位置的和。一个数 $x$ 能放进去，要求大于等于 $1$ 的数至少有 $x$ 个、大于等于 $2$ 的数至少有 $x-1$ 个、……、大于等于 $x$ 的数至少有 $1$ 个。用线段树维护每个数的出现次数，将 $1$ 到 $x+1$ 的位置全都加 $-1$ ，查询最小后缀和，这个最小后缀和若大于等于 $0$ ，则说明可以放入 $x+1$ ，再进一步把 $x+2$ 的位置加 $-1$ 。

题解有个用 set 的高妙做法。

D. Mani and Segments

题意

给定排列 $a$ ，求其有多少子段满足最长上升子序列的长度加上最长下降子序列的长度等于子段的长度加一。 $n\leq 2\times 10^5$ 。

题解

题目的要求即：LIS 和 LDS 有一个公共元素，剩下的每个元素都要么在 LIS 中，要么在 LDS 中。考虑每个位置作为公共元素的情况，不妨考虑往左侧的延伸，往左侧 LIS 的延伸和 LDS 的延伸各自都是单调栈，于是扫序列、在维护两个单调栈的同时记录最近的一个被 pop 的位置（单调栈覆盖的位置的第一个空，或者说无法进入 LIS 或 LDS 的位置），在这个位置之后都可以作为区间左端点；往右侧的延伸同理且独立。

但这样计数会重复（可能有多个点都可以作为公共元素），我们希望只在公共元素已经尽可能靠左的情况下计数。下面的讨论假设当前位置不是序列开头：

先统计这个位置是子段左端点的情况（这时左边显然不能有公共元素的候选）：
考虑它左边相邻的数，不妨设它比当前数小。我们要让左边相邻的数不能作为候选，为此我们考虑当前数右边第一个比它小的数，如果构成了 2 3 ... 1 关系，则左边相邻的数始终可以作为候选，排除掉这种情况；
此时当前数、左边相邻的数、右边第一个比当前数小的数的大小关系一定是 1 3 ... 2（省略号部分是单增的），为了让 1 不作为候选，子段必须把 2 包含进来。即左端点在 1 及其左侧、右端点在 2 及其右侧。

E. Kia Bakes a Cake

题意

给定一棵树，点有黑白。求从每个黑点出发，每次选择一个黑点作为目的地（不能重复），每次走的长度至少是上一次的两倍，至多选几次黑点。 $n\leq 7\times 10^4$ 。

题解

首先，“每次走的长度至少是上一次的两倍”会自然地导致选择的黑点不重复。其次，答案是 $\log$ 级别，我们转而将答案记录进状态，DP， $f[i,j]$ 表示从点 $i$ 出发、接下来要能走 $j$ 轮，第一轮的最大长度是多少。 $f[k,j+1]\gets^{\max} \operatorname{dist}(i, k) \quad (\operatorname{dist}(i, k)\leq f[i,j]/2)$ ，按 $j$ 从小到大 DP。

直接转移是 $O(n^2)$ 的，考虑点分治，考虑 $k \to i$ 的路径最高经过当前分治重心的转移。 $f[k,j+1] \gets^{\max} \mathrm{dep}[i] + \mathrm{dep}[k] \quad (f[i,j] - 2 \mathrm{dep}[i] \geq 2 \mathrm{dep}[k])$ ，这个东西可以树状数组维护，因此在每个分治重心处正反各树状数组扫一遍就可以统计完这一分治重心的转移。做 $\log$ 次点分治即可 $O(n\log^3 n)$ 。

有 $O(n\log^2 n)$ 的做法。