2023 年 2 月做题记录

被 whk 毒打后来做点题颓废一下。

2.12

P7518

首先这个排列把它反映射到 $1 \sim c$，然后可以倍增维护每个数的下一个是谁。

但是从上往下难以维护，于是可以从下往上维护上一个是谁。

而且答案满足可二分性，这样我就知道终点处从哪里开始跳了。

现在问题就变成了需要知道某个点上方第一个某种颜色的点在何处出现。可以用主席树维护。

CF1572C

首先有个显然的三次方区间 $dp$，然后大胆猜测一定让最终颜色变成某一个端点。

然后看见同种颜色出现次数有限制，大胆猜测只会从这些地方转移。

然后就过了。

2.13

CF1375F

rui_er 讲的一道题，rui_er 太强了。

先手三步必杀。第一步把选的强制变成最大值，第二步保证构成一个等差数列，第三步终结比赛。

P4099

一道经典的容斥 dp。

$\mathbf{Lemma.}$ $n$ 个点的子树，要求儿子大于父亲，符合要求的排列数有 $\frac{n!}{\prod sz_i}$ 个。

简要证明：从上到下考虑，首先在 $n!$ 种排列中有 $\frac{1}{n}$ 能使得根合法，然后对于根的直接儿子，在这 $n! \times \frac{1}{n}$ 种中又有其中的 $\frac{1}{sz_{son}}$ 这么多是合法的，以此类推。

然后把大于号容斥掉，变成随意减去小于号。

跑一个树上背包维护除了多少就行了。

好像还有另一种做法，$f_{i, j}$ 表示 $i$ 子树内 $j$ 的拓扑序是多少，然后摁转移。还没想。

2.14/2.15

在学 FWT。

upd：没学会。

2.20

ARC070D

rui_er 神仙讲的神秘题。

首先如果 $b \ge a$，那么一定无解，因为这样可能有一些坏人会伪装好人，这样无法判断哪一拨是好的。

$b \le a$ 时，用类似摩尔投票的方式，最终一定可以抓住一个好人。然后让这个好人问一圈所有人即可得到答案。

P8100

蛮不错的题。

首先观察到如果两个数差 $\ge 2$，那他们的相对位置就再也不会改变了。

考虑按奇偶性划分序列，这样只有可能奇偶性不同的数乱动。

设 $f_{i, j}$ 表示前 $i$ 个偶数，前 $j$ 个奇数组成序列的方案数。

不妨设第 $i$ 个偶数在原序列上的位置比第 $j$ 个奇数要靠后。

转移有两种：

1. 第 $i$ 个偶数不动，这样的方案数是 $f_{i - 1, j}$。
2. 第 $i$ 个偶数与前一个奇数交换，这样的方案数是 $f_{i, j - 1}$。预处理一下能不能交换即可。

2.21

CF1198C

首先找一组极大匹配，如果 $\ge n$，直接结束。

否则，剩下的点之间一定没有连边，要不然这个匹配就不是极大的了！这样就找到了一个大小为 $n$ 的点独立集，结束。

P4211

将深度的贡献转化为 $z$ 到根的路径上，LCA 到根的路径整体 $+ 1$。

然后问题就变成了到根的链 $+ 1$，到根的链查询和。树剖或者全局平衡二叉树都行。

2.22

ARC104E

挺厉害的。

如果暴力枚举钦定 LIS 是谁的话，看似可以容斥，但是会数重。

正确的做法是发现 $n$ 实在是很小，因此甚至可以把整个序列的序都钦定出来，这样是 $O(n^n)$ 的。

然后钦定出序来了之后统计这个序的方案数，可以再 dfs 一次枚举每个作为序的数在哪个值域区间内，这样就很好统计答案。如果是多个数在同一个区间内，用组合数即可。

这启发我们，$n$ 如果真的非常非常小，那不仅仅可以往与 $2^n$ 或 $3^n$ 的方向想，它还有可能是 $n^n$。

P8097

时间倒流，这样加边操作虽然变成了删边，但是没有意义了。

ARC105C

首先枚举排列，然后对于每一个区间都能知道这段区间至少要多长。

然后进行一个贪心，每次尽可能让靠前的段较小，这样可以让后面大的贡献更多。看起来这个贪心很对，不知道怎么证。

2.24

ARC106E

首先二分，然后根据 Hall 定理可以得出一个判定条件。

然后你是可以知道每个时刻恰好是哪些人在你家的。现在你想知道包含某个集合 $S$ 内部的任意元素的情况的天数，即与 $S$ 有交的天数。转化总天数减去恰好 $U - S$ 的子集在你家的天数。

然后做一个高维前缀和，就搞定了。

ARC116D

怎么着瞎 dp 都是对的，好像我的做法很蠢。

2.25

CF1534D

首先问一下 $1$，问出所有深度。

然后看深度奇数的和深度偶数的哪个少，就把哪些全问了，得到每个点的父亲。

AGC030D

对于每一对位置分别统计它成为逆序对的方案数。

考虑 dp，设 $f_{i, j}$ 表示最后 $a_i > a_j$ 的方案数，那么转移就是全局 $\times 2$，被交换的行列方案数变成一个加法。考虑全局 $\times 2$ 变成标记，仅将重要的行、列变成乘上 $2$ 的逆元，这样每一个交换操作就能 $O(n)$ 转移。

2.26

P7077

倒序操作，这下就可以知道每个操作相当于被操作了几次。

2.27

CF364E

二维分治。巨大难写，浪费了一个上午和一个中午。

P5202

挺好的一道 dp。

考虑暴力 dp 是平方的，长得像 $f_i = \min\limits_{\max\{0, i - k\} \le j < i} \{ f_j + [s_j - s_i \ge 0] \}$。

其中 $s$ 是前缀和。

注意到，转移的时候最多只会 $+1$，所以相当于我只需要知道可能的状态里的 $f_{\min}$ 以及 $f_{\min}$ 中最小的那个前缀和。

用单调队列维护即可。

2.28

CF555E

首先缩边双。然后就变成了森林。

森林上面，树上差分一下，最后查一下有没有边被两种方向都覆盖过即可。

AGC033C

操作相当于以选定的点为根，剥掉所有除了它以外的叶子。

这样如果直径被剥完了，其他点肯定也都被剥完了。

直径可能一次减少 $1$（取端点），也可能一次减少 $2$（取其他）。

那么就是一个直径长度 $\bmod\ 3$ 的问题。

（我居然瞪了好久都没看出来要考虑直径。。。我该退役了。。。）

ARC107D

$f_{i, j}$ 表示 $i$ 个数，和为 $j$ 的方案数。

考虑暴力转移，在 $i$ 处看 $i$ 用了啥，复杂度是 $O(n^2\log n)$。

但是这蠢了，实际上可以如果要缩小一个量级，直接从 $f_{i, 2j}$ 转移过来即可。复杂度 $O(n^2)$。

P4514

经典二维差分。

令差分数组 $b_{i, j} = a_{i, j} - a_{i - 1, j} - a_{i, j - 1} + a_{i - 1, j - 1}$。

那么 $a_{i, j} = \sum\limits_{x = 1}^{i}\sum\limits_{y = 1}^{j}b_{x, y}$。

因此

$$\begin{aligned} \sum_{i = 1}^{n}\sum_{j = 1}^{m}a_{i, j} &= \sum_{i = 1}^{n}\sum_{j = 1}^{m}\sum_{x = 1}^{i}\sum_{y = 1}^{j}b_{x, y} \\ & = \sum_{x = 1}^{n}\sum_{y = 1}^{m}b_{x, y}(n - x + 1)(m - y + 1) \end{aligned}$$

维护四个二维树状数组表示 $b_{i, j}, i\times b_{i, j}, j \times b_{i, j}, ij \times b_{i, j}$ 即可。