2023 年 3 月做题记录

三月份后面做的题都没写在这里了，写在了某日志上（有的被搬到这了）。

3.1

ARC106D

很无聊的简单推式子，暴力展开就行了。

ARC108D

分类讨论题。

先假设 $c_\texttt{AB} = \texttt{B}$，如果是 $\texttt{A}$ 则同理。

假如 $c_\texttt{BB} = \texttt{B}$，那么最终的串只有可能有一种，即为 $\texttt{ABB}\ldots\texttt{B}$。

否则 $c_\texttt{BB} = \texttt{A}$，此时，若 $c_\texttt{BA} = \texttt{A}$，那么所有以 $\texttt{AB}$ 起始、$\texttt{B}$ 结尾的串都可以被取到，答案为 $2^{n - 3}$；若 $c_\texttt{BA} = \texttt{B}$，那么所有以 $\texttt{AB}$ 起始、$\texttt{B}$ 结尾的满足 $\texttt{A}$ 不连续的串都可以被取到，答案即为 $\texttt{Fib}_{n - 2}$。

其中 $\texttt{Fib}_i$ 表示斐波那契数列的第 $i$ 项，$\texttt{Fib}_0 = 1, \texttt{Fib}_1 = 1$。

AGC002F

很有教育意义的 dp 题。

注意到，一个序列合法的条件是每种颜色第一次出现的位置之前的白球数量足够。

发现，“一个白球”和“某种颜色剩下的 $k - 1$ 个球”地位一致，可以设 $f_{i, j}$ 表示已经放下 $i$ 个白球和 $j$ 种颜色的方案数。

转移的时候，要么把白球放在第一个空位，要么放下一整种颜色（钦定它一定占了第一个空位）。

3.2

AGC019F

去看粉兔题解吧，那个图就是题解。

3.3

CF1260E

首先，如果编号最大的人不是朋友，那一定得贿赂他。

他可以管住 $n / 2 + 1 \sim n$ 这么多人，所以如果 $n$ 在这个范围内就不用管了。

否则的话就得考虑下一个来管住 $n / 4$ 个人，这里直接用 $n / 2 \sim n - 1$ 这些人中的最小代价即可。以此类推。

CF527E

题面看起来就很欧拉回路。

我们先把奇点两两连接，然后如果边数是奇数的话一定不行，于是还得加个自环。

然后跑一遍欧拉回路，把欧拉回路上的边交替定向即可。

3.8

CF1707E

首先有一个很厉害的结论，$f((l, r)) = \bigcup\limits_{i = l}^{r - 1} f((i, i + 1))$。

然后它居然对于嵌套 $k$ 次也有效！！$f^k((l, r)) = \bigcup\limits_{i = l}^{r - 1} f^k((i, i + 1))$

然后就倍增一下，每一层查询用一下 ST 表。复杂度是两只 $\log$。

3.10

CF1239E

首先有一个非常厉害的观察，就是最优解一定满足第一行递增，第二行递减。

这样的话，两种可能的最长路径一定是从第一列换行或者从第 $n$ 列换行。

然后发现，让最小的两个值待在左上角和右下角能使它们的贡献最多，剩下的就跑一个背包就行了。

CF1270H

让人大受震撼的一个题。

首先有一个性质，如果 $l$ 和 $r$ 连通，那区间 $[l, r]$ 一定连通。

因此这些连通块一定长成一堆区间的样子。

什么时候 $l$ 和 $l - 1$ 会不连通呢？是在 $\min\limits_{i = 1}^{l - 1}a_i > \max\limits_{i = l}^{n}a_i$ 的时候。

问题变成了求满足这个式子的 $l$ 的个数。

然后又是一个非常神秘的转化。考虑枚举这个后半部分的 $\max$，设为 $k$，将 $\le k$ 的赋值为 $0$，$> k$ 的赋值为 $1$，那么只有在这个序列形如 $111\ldots 11000\ldots 00$ 的时候才会合法。

换句话说，假如在开头补上 $+\infty$，末尾添一个 $0$，对于每对 $a_i, a_{i + 1}$，跨越枚举到的这个 $k$ 值的 $a_i, a_{i + 1}$ 对只能有一个。

然后！你考虑题目为什么给你的数不重复，肯定是想让你在值域上搞事情。

具体来讲，在值域上建一棵线段树，然后考虑对于相邻的 $a_i, a_{i + 1}$，将线段树上的区间 $\left[\min\{a_i, a_{i + 1}\}, \max\{a_i, a_{i + 1}\}\right)$ 加一。这意味着如果你枚举的 $\max$ 在这段区间内的话，那么你的 $10$ 切换次数会增加 $1$。然后你发现你需要知道值为 $1$ 且下标在 $a$ 中出现过的数的个数。

由于你在开头补上了 $+\infty$，在末尾添了 $0$，那它就能保证两个正确性。第一个是他不会多数 $000\ldots 00111\ldots 11$ 的情况了，因为开头那个 $+\infty$ 让它开头多出了一个 $10$。

然后末尾的 $0$ 保证了你一定至少会出现一次 $10$ 的切换，所以最小值一定是 $1$（在下标 $0$ 处），那么你维护一下最小值出现次数就可以了。

另外，怎么维护下标在 $a$ 范围内的最小值出现次数呢？这比较容易，单点改一下当前点会不会被统计成最小值（其实就是单点的最小值出现次数变量 $0$ 和 $1$ 改一下）就可以了。

3.11

CF1495E

不能正常想这个题，正常想就完蛋了。首先容易发现总卡牌数较少的那边一定会打完所有的牌，然后考虑统计另一边每个人打了多少。

接下来就是个很神秘的观察，大概就是说后手打牌的先后顺序事实上不重要了。

然后直接随便给一个好做的序，暴力模拟一下就行了，恐怖如斯。

3.12

P9070

好恐怖啊。

先考虑 $\mathrm{subtask}\ 2$。因为每个人只能有一种不同的卡牌，所以我们把所有人的这种卡牌放到最后一个，写成一个矩阵的形式，每行是一个人手上的牌，然后你发现每一列都是符合要求的。这启发我们（怎么想到的？？？）使用转置，即让每一列都满足要求后，最后将整个矩阵转置即可。

怎么让每一列的每种颜色都恰好出现了 $n$ 种呢？你可以随便安排每个人手上的牌的顺序，那么这个问题就变成了一个匹配问题（怎么想到的？？？）。具体来讲，先做第一列，每个人向他手上有的牌的颜色连边，跑一个最大匹配，然后把匹配边放到第一列身上，然后继续一列一列做就行了。

根据 $\mathrm{Hall}$ 定理，每一步匹配都一定有解，因为这个二分图上每个点都连出去了 $n - i$（$i$ 是循环变量）条边，然后左部点的某个点集 $S$ 的邻域大小一定 $\ge |S|$。因为如果邻域大小 $< |S|$，根据抽屉原理，这个点集向右连出的 $(n - i)|S|$ 条边连到了 $< |S|$ 个右部点上，那么一定存在一个右部点的度数 $> (n - i)$，矛盾！因此每步匹配都能找到解，所以这个题事实上一定是有解的。

ARC154E

给排列 $P$，每次操作形如翻转一个区间 $[l, r]$。现在你需要随机做 $M$ 次这种操作。求最终状态下所有 $\sum\limits_{i < j}[P_i > P_j](j - i)$ 的和。

首先将那个式子化简一下，让 $i, j$ 独立。

$$\begin{aligned} & \sum\limits_{i < j}[P_i > P_j](j - i) \\ = & \left(\sum_{i < j}[P_i > P_j]j\right) - \left(\sum_{i < j}[P_i > P_j]i\right) \\ = & \sum_{i = 1}^{n}i\left(\sum_{j < i}[P_i < P_j] - \sum_{j > i}[P_i > P_j]\right) \\ = & \sum_{i = 1}^{n}i\left(i - 1 - \sum_{j < i}[P_i > P_j] - \sum_{j > i}[P_i > P_j]\right) \\ = & \sum_{i = 1}^{n}i\left(i - 1 - \sum_{j = 1}^{n}[P_i > P_j]\right) \\ = & \sum_{i = 1}^{n}i(i - 1 - (P_i - 1)) \\ = & \sum_{i = 1}^{n}i(i - P_i) \end{aligned}$$

于是我们只需要求最后所有可能 $\sum\limits_{i = 1}^{n}iP_i$ 的和。

但是对于一个初始的 $P_i$，它未来处在位置的方案不好求。

观察操作性质，对于一次操作，恰好将 $i$ 位置的数与 $j$ 位置的数交换的方案数为 $\min\{i, j, n - i + 1, n - j + 1\}$。

这个式子长得非常对称，然后你惊奇地发现，将 $i$ 位置和 $j$ 位置交换和将 $i$ 位置和 $n - j + 1$ 位置交换的方案数是完全一样的！

所以在进行了包含 $i$ 的交换操作后，任意 $i$ 的新位置期望都是 $\frac{n + 1}{2}$。换句话说，只需要求 $\frac{n + 1}{2}$ 乘上 $i$ 被交换过的方案数。如果没被交换过，那 $P_i$ 就留在了 $i$ 这个位置上，位置一定是 $i$。

可以对于每个 $P_i$ 最终的贡献求和。对于一个 $P_i$，它没有被操作到过的方案数就是 $(i(i - 1) + (n - i)(n - i + 1))^M$，此时最终位置一定是 $i$，贡献是 $iP_i$。剩下的情况下它被操作过，它的位置期望是 $\frac{n + 1}{2}$，贡献是 $\frac{(n + 1)P_i}{2}$。

对每个数算一次即可。