Codeforces Round 968 (Div. 2)
| Problems | AC |
|---|---|
| A. Turtle and Good Strings | ○ |
| B. Turtle and Piggy Are Playing a Game 2 | ○ |
| C. Turtle and Good Pairs | ○ |
| D1. Turtle and a MEX Problem (Easy Version) | ○ |
| D2. Turtle and a MEX Problem (Hard Version) | ⊕ |
| E1. Turtle and Inversions (Easy Version) | ⊕ |
| E2. Turtle and Inversions (Hard Version) | ⊕ |
| F. Turtle and Three Sequences |
C
题意： $(i, j)$ 是好的当且仅当 $i<j$ 且存在 $k \in[i, j)$, 满足 $s_k \neq s_{k+1}$ 且 $s_i \neq s_k \vee s_j \neq s_{k+1}$ 。将 $s$ 重新排序, 最大化好的数对个数。
把字符串分为若干极长连续颜色段 $\left[l_i, r_i\right]$ （如 $a a a b b c c=[a a a][b b][c c]$）。
容易发现 $(i, j)$ 是好的的充要条件为 $i, j$ 所在颜色段不相邻。
令 $a_i=r_i-l_i+1$ ，那么好的数对个数等于 $\frac{n(n-1)}{2}-\sum a_i a_{i+1}$ 。
目标转化为最小化 $\sum a_i a_{i+1}$ 。
当字符集大小不为 1 时，可以证明 $\sum a_i a_{i+1} \geq n-1$ 并且这个下界是可以达到的。
如果存在 $a_k=1$ :
$$
\sum_{i=1}^{m-1} a_i a_{i+1} \geq \sum_{i=1}^{k-1} a_i+\sum_{i=k}^{m-1} a_{i+1} = n-a_k = n - 1
$$如果 $\forall a_k \geq 2, a_i a_{i+1} \geq a_i+a_{i+1}$ :
$$
\sum_{i=1}^{m-1} a_i a_{i+1} \geq \sum_{i=1}^{m-1} a_i+\sum_{i=2}^m a_i>n
$$
我们让前面所有 $a_i=1$ ，最后一个连续段放多出来的相同字母（如 $a a a b b c c=a b a b a c c$ ），显然有 $\sum a_i a_{i+1}=n-1$ 。
时间复杂度 $O(26 n)$ 。
D1
题意：给定 $n$ 个序列 $\left[a_i\right], f(x)$ 定义为 $x$ 经过若干次操作（可能不操作）达到的最大值。
一次操作定义为: 选定一个序列 $\left[a_i\right], x \leftarrow \operatorname{mex}\left(x \cup\left[a_i\right]\right)$ 。
在简单版中, 一个序列可以被重复选择。
给定 $m \leq 10^9$, 求 $\sum_{x=0}^m f(x)$ 。
定义 $u_i=\operatorname{mex}\left[a_i\right], v_i=\operatorname{mex}\left(\left[a_i\right] \cup u_i\right) 。$
我们发现不管是什么 $x$, 不管对 $\left[a_i\right]$ 操作几次, 能够达到且一定能达到的只有 $v_i$ 和 $u_i$ 。
因此 $f(x)=\max \left(x, \max v_i\right)$。
D2
多了的限制是每个序列只能用一次。
这意味着假如你在 $u_i$，向 $v_i$ 走了以后就不能回头。
考虑一次操作，相当于是在图上走一条边 $(x, y)$，并断掉 $y$ 的一个出边
在图上倒着 dp 可以求出每个点能到达的最大点的坐标 $f$。
考虑如何统计答案：
对于一个 $x$，他至少是 $f_x$ 和 $\max{u_i}$
对于一个 $i$，如果出边数量 $ > 1$，那么 $\forall x$ 可以走到 $f_i$
记 $k = \max{v_i}$，小于等于 k 的枚举；对于大于 k 的 $x$，一定不会再操作了， i.e. $f(x) = x$。
E1
nb 题
题意：给定 $m$ 个限制 $\left[l_i, r_i\right]$, 表示存在 $k \in\left[l_i, r_i\right]$, 记 $a_i=\max _{j=l}^k p_j, b_i=\min _{j=k+1}^r p_j$, 使得 $\max a_i<\min b_i$ 。
求长度为 $n \leq 5 \times 10^3$ 的符合限制的排列的最大逆序对数。简单版保证限制互不相交。
把所有数分为两类：小数 ($0$) 和大数 ($1$) ，满足 $\max{0} < \min{1}$。
条件 $i$ 被满足当且仅当 $[l, r]$ 内所有 $0$ 都在 $1$ 前面, 且 $0$,$1$ 都至少出现一次。
如果最后的排列有 $x$ 个 $0$, $y$ 个 $1$ , 贪心的使所有 $0$ 从大到小排, $1$ 从大到小排。
设有 $z$ 个逆序对形如 $(1,0)$, 称之 $10$ 对, 那么最后的总逆序对数等于 $\frac{x(x-1)}{2}+\frac{y(y-1)}{2}+z$ 。
设 $f(i, j)$ 表示填完前 $i$ 个数，其中 $j$ 个是 $1$ 的最大 $10$ 对数。
- 如果 $i$ 是某个限制的右端点, 枚举 $[l, r]$ 之间有多少个 $1$ 。
- 否则讨论 $i$ 填 $0$ 还是 $1$ 。
最后答案是 $\max f(n, i)+\frac{i(i-1)}{2}+\frac{(n-i)(n-i-1)}{2}$ 。
暴力转移看似是 $n^2$ 的, 但由于区间不相交, 第一种转移也是均摊 $O(n)$ 的。时间复杂度 $O\left(n^2\right)$ 。
E2
和 E1 相比多了区间相交的情况。
考虑对于一对相交的区间 $\left[l_1, r_1\right],\left[l_2, r_2\right]$ （不妨设 $l_1 \leq l_2$ ）， $\left[l_1, l_2-1\right]$ 一定全是 $0 ，\left[r_1+1, r_2\right]$ 一定全是 1。
然后可以删掉 $\left[l_1, r_1\right],\left[l_2, r_2\right]$，添加一个新区间 $\left[l_2, r_1\right]$ ，并记下有哪些数一定是 0，哪些数一定是 1 。
这样处理完后区间一定互不相交，就变成了E1。
时间复杂度：每个测试用例 $O\left(n^2+m \log m\right)$ 。
Codeforces Round 968 (Div. 2)