2023 年 1 月做题记录

得开始卷了！！！再不卷就寄了！！！！！

12.26

CF603E

首先你发现每个点度数都是奇数的话，连出来的所有连通块大小必须都是偶数。

然后你发现如果所有边连出来的连通块大小都是偶数的话，一定存在一种选边方案使得每个点度数是奇数。

然后问题就等价成了连最大价值最小的某些边，让连通块大小必须是偶数。

然后你观察到这个东西如果某一个时刻 ok 了，之后一定一直是 ok 的，因为偶 $+$ 偶 $=$ 偶。

然后你发现这个很像 kruskal 啊！但是我还要动态加边呢，暴力做肯定就寄了。

然后你发现随着时间流逝，答案一定是越来越小的，因为可选的边越来越多。

那么假如说一个边在最后一刻被选了，那么他一定从他出现的时刻一直到现在都被选了。

然后你可以倒着线段树分治，每到一个点就更新前面一批点的新存活时间，然后就做完了。

12.28

P3792

你发现区间内值域整数意义下连续相当于什么？

让人想到 Pudding Monsters 那题（

首先区间 $[l, r]$ 的 $\max - \min + 1$ 得等于 $r - l + 1$。

然后你发现跟 Pudding Monsters 不同的是这个不是排列，他可能会重复，所以区间内还不能有重复。

这个我们维护一下每个数上一次出现的位置，然后要求区间内的 lst 最大值必须在区间左端即可。

注意垃圾回收，$10^6$ 个 set 据说过不去。

P5278

P3792 的加强版。

发现加强版多了什么？多了公差。

说到等差数列想必正常人都能想到差分。然后你会惊奇的发现那个差分 gcd 的性质好像能直接用在这里，然后这题就做完了。

12.29

P3773

一堆组合数连乘是奇数，那这堆组合数每个都得是奇数。

根据 lucas 定理，组合数 $\binom n m$ 是奇数的充要条件是 $n \operatorname{and} m = m$。

然后你可以做一个 dp，观察转移的形状，是一个枚举子集。

然后因为 $a_i$ 是不重复的，所以复杂度正确。

P4562

发现有些地方是必要的，有些地方是无关紧要的。

然后对着这个直接计数就行了。

P3215

维护区间匹配括号的套路是考虑维护把该匹配的都匹配了之后，剩余的形如 ))))))((((( 的段。然后上平衡树就行了。

1.4

P1989

广为人知的三元环计数，考虑定向，度数小的向度数大的连边，如果度相等那就编号小的向编号大的连边。

然后他是个 dag，所以三元环一定形如 $(u, v), (v, w), (u, w)$。

枚举 $(u, v)$，枚举 $(v, w)$ 然后判断 $w$ 是否在 $u$ 的出边中即可。

时间复杂度 $O(m\sqrt m)$。

证明如下：

记原图度数为 $d_u$，新图入度 $in_u$，新图出度 $out_u$。

考虑先枚举了 $(u, v)$ 再枚举 $(v, w)$，复杂度相当于新图中

$$\sum_{(u, v) \in E} out_v$$

• $d_v \le \sqrt m$ 时，$out_v \le \sqrt m$。
• $d_v > \sqrt m$ 时，这样的点不超过 $\sqrt m$ 个，又因为度数小的向度数大的连边，所以 $v$ 在新图上最多向 $\sqrt m$ 个点连边，即 $out_v \le \sqrt m$。

综上得证。

1.5

P6617

考虑 P3792 维护前驱的套路。

但是你发现直接维护会爆炸。

不过有一个神秘性质，就是一段前驱一致的数，我们可以只保留第一个的前驱，其他的前驱设成 $0$ 就行了。

容易证明它是对的。

然后这时候修改的位置个数就是常数的了，很厉害。

细节有点多。

1.8

P4782

2-SAT 模板。

考虑对每个变量建两个点表示这个变量是 true 和 false 的情况，将完全确定的推出关系连有向边。

这样的话如果我选了一个点，这个点之后的后继路径就都得选了。

于是缩强连通分量，如果一个变量的 true 和 false 点在同一个强连通分量中则绝对无解。否则可以证明一定有解。

对于解的构造，考虑逆着强连通分量的拓扑序来，就是说对于一个变量，选择这个变量对应的两个点中强连通分量拓扑序更大的那一个，这样能保证这个点后继一定选不到与之矛盾的另一个点。

观察到 tarjan 算法的过程，我们弹出每个强连通分量是逆着拓扑序来的。所以强连通分量编号越小拓扑序就越大。

1.9

P2742

二维凸包模板。

以 $x$ 为第一关键字，$y$ 为第二关键字排序。然后从左往右求出下凸包，再从右往左做一遍上凸包。都是要求这个东西左转，用叉积判断即可。

P4688

人生第二道 Ynoi。

发现这个东西怎么着都不可能正常维护，然后看见询问是减去一个 $\min$ 出现次数的形式，可以考虑 bitset 维护。

然后在拿 bitset 当桶的时候，为了方便我们将颜色离散化的时候不去重，这样可以快速知道当前该在 bitset 上当第几位了。

然后发现直接做空间会炸，所以多做几次，卡一卡空间就行了。

1.10

P5069

第三道 Ynoi。

观察这个操作干掉一个点之后他两边的点也一定死了。

考虑线段树维护，这样合并区间时重要的只有两边的点，稍微讨论一下就可以得到合并的结论。

大概就是，如果至少一个区间的靠近中间的点没有被选，那么直接两个区间答案相加就是答案。

如果两个靠近中间的点都被选了，那就看谁更大，然后另一个区间用那个强制不选靠近中间的点的答案。

1.11

P4557

学习一下闵可夫斯基和。

首先看这个题，设这两个凸包为 $A, B$，对于 $B$ 移动一个向量 $d$ 的情况，如果

$$\exists a \in A, b\in B, a = b + d$$

即

$$a - b = d$$

那么这两个凸包移动后有交。

观察 $a - b$ 长什么样，我们知道 $A, B$ 的闵可夫斯基和是形如 $C=\{a + b | a \in A, b \in B\}$ 的凸包 $C$。

那存在 $a, b$ 使得 $a - b = d$ 这个问题就变成了 $A$ 和 $-B$ 的闵可夫斯基和 $C$ 中包含 $d$ 这个点。

求一下闵可夫斯基和，判断 $d$ 在不在凸包内即可。第一次做计算几何，踩了好多坑（比如不封装）。

1.13

P5073

是对珂学的信仰才让我坚持写完了这个题（

不想写简要题解。

1.14

P8074

为什么我要做垃圾题浪费时间？

P8026

首先看着就需要并查集。然后你发现两个点满足条件，就是这两个点需要在每个图中都属于相同的连通块，也就是这两个点在每个图的并查集上的根都相等。

这显然不好维护，考虑哈希，变成每个图上的根的哈希值之和相等，然后开个桶，做完了。

1.16

P3188

挺有意思的背包。

首先肯定要对于每种 $b$ 分别背包一次，然后考虑背包合并。

这里我们发现如果从高位到低位合并的话，可以方便地处理这个 $W$ 的限制。

具体来讲，我们存一下当前处理到的 $2^i$ 还剩下多少个，然后发现这个存到 $2000$ 就够了（因为 $1000 + 500 + 250 + \ldots \le 2000$），然后也能很方便地转移（就是看这位剩下多少乘以二再加上 $W$ 下一位是不是 $1$），然后直接 dp 就做完了，感觉有点像 noip2021 T2。

P8564

简易树上背包。

1.18

冬令营寄了。

CF1442D

首先需要注意一下这个每个数组不降的性质有啥用，使用调整法发现答案的形状一定是若干个完整数组再加上至多一个数组的前缀，否则一定不优。

然后枚举哪个数组选前缀，然后暴力前后缀背包合并肯定是不行的，套一个线段树分治复杂度就对了。

1.19

CF150E

首先一眼丁真，鉴定为二分。

然后点分治，先出一个很蠢的 $\log^3$ 做法，名字叫做线段树，显然过不去。

然后发现这是一个滑动窗口，但是直接做的话会寄，因为众所周知滑动窗口是 $O(n + m)$ 的，两个序列长度都要被考虑在内。

然后发现复杂度的瓶颈其实不在于窗口的滑动，而是在于初始化，因为滑动只有可能滑动每个子树的 size 次，但是初始化就是前面最大的子树的最大深度级别的了。

我们按照最大深度从小到大排序来做，这样初始化的复杂度就对了，相当于每个点又多来了一次。这个东西好像叫启发式合并滑动窗口。

很厉害。不看题解不会。

P3396

挺板的根号分治。

首先暴力就是直接改，然后暴力查询。这里修改是 $O(1)$ 的，但是查询是 $O(n)$ 的。

考虑平衡，如果模数 $> \sqrt{n}$，那暴力就是对的。

模数 $\le \sqrt{n}$ 时，把所有答案都存下来，这样一次修改只会改 $\sqrt{n}$ 种答案。

P2424

垃圾整除分块。

1.20

P3747

首先你发现，这个不好直接维护啊！然后你立马想到了两个题：上帝与集合的正确用法、上帝造题的七分钟 2。

然后你一眼丁真，鉴定为缝合怪。每个 $a$ 最多改 $\log$ 次，把这些次修改后的结果都预处理出来，然后线段树直接那么着做一下，就是可以的。

注意一个细节：

• 预处理的时候，扩展欧拉定理可不是随便用的，需要指数 $b \ge \varphi(p)$ 才能进入循环节。

然后这里看到很多题解都采用了一个递归下去，然后对于每次快速幂，看一下当前是不是乘炸了，依据此来判断下一回的指数要不要加上 $\varphi$ 值。

但是经过感受，这样可能会错，例如 $2^{2^4} \bmod 9$。这里 $\varphi(9) = 6, 2^{4} \bmod 6 = 2^{4 \bmod \varphi(6) + \varphi(6)} \bmod 6$ 倒是没问题，但是 $2^{4 \bmod \varphi(6) + \varphi(6)}$ 的过程中并不会乘炸出 $6$ 的范围，那在下一层的时候计算就出现了错误，也就是我本应该计算 $2^{2^4 \bmod \varphi(9) + \varphi(9)} \bmod 9$（因为显然 $2^4 \ge \varphi(9)$），但事实上我计算了 $2^{2^{4} \bmod \varphi(9)} \bmod 9$，少加上了 $\varphi(9)$。只不过这里 $2$ 和 $9$ 互质，导致答案是正确的，但是万一有别的地方会错呢？

事实上，并没有任何会导致错误的地方。考虑观察一下，会出错当且仅当 $c^{x \bmod \varphi(p) + \varphi(p)} < p$ 而且 $c^x \ge p$，它的一个必要条件是 $c^{\varphi(p)} < p$，也就是 $\varphi(p) < \log_{c}p$。众所周知， $\varphi$ 的增长比 $\log$ 快很多，具体来讲，经过暴力搜索发现，只有可能在 $c = 2$ 且 $p = 6$ 时出现 $c^{\varphi(p)} < p$，也就是刚刚我们举出的“反例”，但是由于满足 $\varphi(x) = 6$ 的 $x$ 值显然只有 $9$，而 $2$ 一定与 $9$ 互质，所以直接这么做一定不会出错。

然后回来，发现直接做的话是 $\log^3$ 的，过不去！

不过你发现这里底数都是一样的，所以考虑光速幂，然后就优化到了两只 $\log$，结束。

P6329

点分树板子。

注意到点分治相当于把所有路径按照中间的某个点分类。

而这里我们的询问长成这个样子，其实相当于找所有距离 $x$ 不超过 $k$ 的路径端点。

在点分树上，这样的路径问题可以很方便地暴力解决。具体来讲，枚举 $x$ 在点分树上的祖先（也就相当于点分治过程中被这个祖先劈开的经过 $x$ 的路径），然后发现需要统计距离这个祖先 $u$ 不超过 $k - \operatorname{dis}(u, x)$ 的点 $v$ 的权值和，可以写动态开点线段树（也可以 vector 开树状数组）。

但是还是根据点分治，这么直接做会算重 $u$ 下方包含 $x$ 的子树中的结果，那就再开一棵线段树容斥掉它即可。具体来讲，这棵新的线段树的下标维护的是点分树上一个点的子树中所有点，到这个点在点分树上父亲的原树上的距离。

感觉点分树这种东西好优美wwww

题外话：我本来倍增写的 f[17][N]，T 飞了。交换了一下变成 f[N][17]，就直接过了，不太明白，可能还是这么着写 cache miss 更少？

1.22

UVA1608

裸的扫描线，直接做就行了，比较容易。

但是不知道为啥，写挂了好多发，还老是多测不清空。

1.26

喵了个喵想了两天，不会。先去做别的了。

ARC104C

思维不行，该刷 ARC 了，不刷不是中国人。

这个题数据范围告诉我们是 dp。然后就是发现性质了。。。

想了一段时间，发现对于一段有交的东西，一定长成这样的形状：

这个是怎么发现的呢？考虑从边角开始看这个东西长什么样。假如说以 $1$ 为左端点的区间长得很长，那么以他中间的为左端点的首先不能被包含，然后还得长得和以 $1$ 为左端点的这个一样长。那就只能长成这样了。然后断掉之后，下一个又是一个完全一样的子问题，这样就可以预处理一下可以做到这个程度的区间们，然后直接 dp。

我蠢了，写了个区间 dp。事实上直接平方的一维 dp 就行了。

1.30

看了喵了个喵的题解，大受震撼。还没写代码。

1.31

ARC104D

首先一眼背包。然后复杂度炸了。

但是你发现平均值 $x$ 不同的情况居然可以化归成相同的问题！具体来讲，对于平均值为 $x$ 的情况，相当于 $-x+1, -x, \ldots, -1, 0, 1, \ldots, n - x$ 这些数里面选出个 $k$ 可重集和为 $0$ 的方案数。然后 $0$ 的个数随意，负的情况和正的情况的绝对值要相等。

枚举这个绝对值，问题就变成了只需要求 $1$ 到某一个数的一个多重背包。这里多重背包是方案数，所以直接用前缀和优化就行了。前缀和优化就是，先假装他是一个完全背包，然后再扣掉用了超过 $k$ 个的部分，很厉害。