CFの题 Ⅰ

摘要：2022年9月和10月做的一些题。

CF193D

首先把问题转化成值域上有多少个区间映射到原数列上形成的连通块数量不大于 $2$（当然要求区间大小不为 $1$）。枚举右端点，然后考虑有多少个左端点合法。考虑右端点挪动时对每个位置的变化量，首先可以把新点看成一个新连通块，也就是所有点都加一；然后寻找哪些点会变化，也就是当前点可能合并哪些区间。直接看这个点原数列上左右的数值，如果是前面已经出现过的点（也就是值较小的点），那么这个点以及更小的点连通块都会少一个，左右各判一次即可。查询上是一个经典的问题，$1$ 和 $2$ 显然在正整数域上是最小值和次小值，分别维护数量即可。整体上线段树，复杂度 $O(N\log N)$。

CF258B

主要是这道题的根号分治式的预处理可以提一下。这种方法下要注意 $0$。

CF258C

考虑枚举最大的数是谁，然后找出所有因数（可以证明所有数因数个数和是 $N\log N$级别的），把原数列排序之后二分查找每个数能赋值为多少个因数即可。由于需要保证至少有一个数刚好去到了最大值，需要容斥一下，即减去不要这个数本身的因数集合的方案即可。复杂度三只 $\log$，但快速幂那只很小。

CF258D

这种题有个套路，用 $f_{x,y}$ 代表 $x$ 比 $y$（位置）大的概率，显然对于当前交换的 $x,y$，有 $f_{x,y}=f_{x,y}=0.5$。然后考虑此次交换可能影响到其它的哪些值，发现对于 $f_{t,x},f_{t,y}$，有 $f_{t,x}=f_{t,y}=\frac{f_{t,x}=f_{t,y}}{2}$，毕竟这两个位置已经可以看成是完全等价的了。注意初值和答案统计即可。

CF258E

转化题意，每次给定两个子树，使得这两个子树内节点两两间连边，求最后每个点和多少点有连边。首先转成 dfn 序，于是就成了两个连续区间的关系。可以看成是纵坐标一段区间内都和横坐标有联系，求每个纵坐标对应的横坐标数量，可以抽象成矩形（每次操作就有了四个矩形），扫描线维护即可。复杂度 $O(N\log N)$。

CF176E

有一个重要结论，虚树的边权和等于相邻（按 dfn 排序）点的距离之和的一半，把虚树画出来很好证。有了这个结论之后就很好做了，按 dfn 序维护一个 set，每次插入的时候更新这个点两边的距离即可。删除也是一样，可以考虑先删点再减去贡献，复杂度 $O(N\log N)$。

CF261B

转换思路，考虑每种情况（变相地枚举贡献）可能的概率，然后就是一个 01 背包问题了。由于希望背包容量不够，故而还需要额外枚举到底是哪个人超出了容量限制，这样一来需要的人数就有了概念。明白了这两点就很简单了，是一道比较综合的题目。

CF261D

好暴力的题。重点在 $n\times maxb\le 2\times 10^7$，$maxb$ 是值域，故而正解应该是在 $n$ 上做文章。然而当 $k$ 很大时直接 szsz 维护比较麻烦，想到当 $k$ 大到一定程度时答案应该就是数列的元素个数，而当 $k\le maxb$ 时，根据题目的限制，暴力也能过。

CF261E

一道比较卡常的题。首先理解这个过程的本质是什么样的，显然最后的 $a$ 是由许多个数乘起来得到的，而第二个参数要尽量小，就只能恰好等于最大的那个因数。注意，这个分解并不一定是按质因数分解，比如 $1024$ 分解成 $4$ 的幂就会比分解成 $2$ 的幂要优。而由于有操作数量的限制，因数不能太大，也就是说这些数只可能有 $\le k$ 的质数因子，这些数不会太多，搜索一下即可。最后就是 DP 了，用 $f_{x,y}$ 代表第二个参数为 $x$，第一个参数是 $y$ 时的最少步数，决策只有两个，即当前 $y$ 是乘过来的和当前 $x$ 是加过来的。

然后就是一些卡常的东西。搜索的时候要用线性筛一样的方法，不能用 set 只能用数组记录；动态规划的时候第一维应该滚掉；判断当前 $x$ 和 $y$ 的整除关系时要用乘法，不能用除法；判断 $\frac{x}{y}$ 的位置时，由于这个式子不减，所以可以用指针维护，不能二分查找；不能初始化（特别是 memset）；不能开 long long；等等等等。

CF286C

告诉我们遇到问题可以转变方向，比如这道题从左往右不好做，从右往左维护就可以豁然开朗：因为右括号是消耗品，所以当某个时间没有右括号了，左括号就只能充当右括号，这个贪心是正确的；而从左往右时，左括号变成消耗品了，假如不够了就没办法了，所以不能从左往右。

CF280D

涉及到一个叫做模拟费用流的知识点，也就是用费用流的思路去思考，然后用线段树来实现。考虑用费用流来解决这个问题，可以把一个区间拆分，那么对应的费用就是一个加和一个减，于是可以给源点到每个点连一个前缀相反数的边，然后每个点往汇点连一个前缀的边，中间部分单向连 $0$ 边，这样一来每条水流就对应了一个路径，而费用流反向边就相当于是一个反悔机制。然而复杂度太高，考虑用线段树实现这一过程。发现一条最大的水流本质上就是找最大子区间，而所有费用取反的过程也可以看成是区间内所有元素取反。手动模拟一下发现这样的思路是正确的，所以我们需要维护一棵支持最大子段及位置查询、支持单点修改和区间取反的线段树，和板子其实差不多，虽然码量大了一点（不过也没到 4k），但其实还好。

CF241D

神仙结论题。通过一些不知名的方式可以得到结论如下：只需要不大于 $24$ 的数们凑在一起就可以满足模数的一切需求。应该可以通过枚举来得出结论，这样一来就只需要 $2^S$ 搜索判断即可。

CF241B

粽子的加强版。粽子由于求的 $rank$ 比较小，故而可以直接用堆维护；这道题由于对 $rank$ 没有限制，所以只能先二分出 $k$ 大之后按位贡献。二分的 check 部分就是一个 Trie 上的 DP，在每个节点处判断当前二分值对应位是 $0$ 还是 $1$，如果是 $0$ 就累加 $1$ 的子树大小跳到 $0$ 子树，否咋直接跳到 $1$ 子树即可。至于后面的求和部分，可以按照相似的方法，用 $num_i$ 来记录当前字数内第 $i$ 位是 $1$ 的数的个数，这样一来要计算 $x$ 和一个子树内所有数的异或值之和就只需要考虑每一位能贡献多少个 $1$ 即可。上面两个部分由于我的写法求的都是答案不小于某个值的答案，所以当遍历到叶子节点的时候要额外统计一下。

CF297C & CF297D

两个构造题。第一题由于 $s$ 数组元素互不相同，故而一定有解。具体构造方法就是题解里那幅图，非常言简意赅。而第二题的突破点在 $\frac{3}{4}$ 这个要求上，可以想到先构造一个 $01$ 矩阵使得横向或者竖向的方向上符合条件，另一个方向可以通过是否取反来把满足率提高到一半以上即可。注意强制满足条件的方向应该是格子较多的那个方向。

CF300D

显然可以用 $f_{x,k}$ 代表还可以分解 $x$ 层时用了 $k$ 次机会的方案数，然后转移就是 $f_{x,k}=\sum\prod\limits_{i=1}^4f_{x-1,a_i}\ \ (\sum a_i=k-1)$，复杂度是 $O(N^4\log S)$。然后有个技巧就是由于后面四个东西事实上是等价的，所以可以把这四个东西从中间斩断分成两个部分，分别转移然后用一样的方式合并即可。这样的复杂度可以做到 $O(N^2\log N)$，有些细节但不重要。

CF300E

显然问题就变成了对于每个 $p$ 求 $\sum\limits_{i=1}^k\sum\limits_{j=1}\lfloor\frac{a_i}{p^j}\rfloor$，即它在这个阶乘中的指数大小。直接算肯定会超时，所以有个妙的方法，由于本题中值域不大，故而可以在值域上给 $a$ 求个后缀，在统计的时候把柿子掰开，具体做法是对于每个 $p^j$，考虑有多少个数贡献至少一个，有多少个数贡献至少两个，差分一下就可以了。复杂度比较复杂，计算次数大概是 $\sum\limits_{i=1}^{num_p}\frac{Max}{p_i}\times t,t<2$ 的这样一个柿子，反正不会太大，所以能过。

CF22E

给定一片内向的基环树森林（内向不等于孤僻！），希望加一些边让图强连通。如果只有一个内向的基环树，从根往每个叶子连边即可；如果有很多基环树，显然需要通过一些方式把他们串连起来，于是可以把一棵树的根连在另一棵树的叶子上就可以了。要注意处理一些细节，比如整棵树就是一个环等。还是比较好写。

CF1707E

神仙题，真的神仙，估计喝了嘎子的假酒才能想出来。思路自然是倍增，因为如果一个区间已经到了 $[1,m]$，那么它再跳无论多少步都不会再变化，具有单调性。但如何倍增呢，状态数是平方级别的，肯定是存不下的。然后有个神仙结论，即对于区间 $A=B_1\cup B_2\dots\cup B_n$ 并且满足 $\forall i\in[1,m-1],B_i\cap B_{i+1}\ne\varnothing$，那么 $A$ 的映射应该是这些 $B_i$ 的映射的交集，并且刚好等于。原因是对于两个有交集的区间，他们必然会有相同的数，所以他们映射出来的值域也应该有交集。然后显然大区间不可能跃出小区间的范畴，所以假如只跳一次这个结论是正确的，推广开来跳任意次这个结论也是正确的。有了这个之后就可以像 ST 表一样把一个区间拆成两个区间，通过把两个区间倍增值合并起来得到自己的答案。于是就可以做了，由于需要保证两个相邻的集合有交集，所以状态定义的时候会有一个溢出的值用于维持性质，这就导致有许多细节需要注意，然后就没了，复杂度 $O(N\log N\log S)$，$S$ 是可能的最大步数，感性理解应该和 $N$ 同级。

CF283D

一道妙的结论题。首先分析小括号的性质，即何时 $(x,y)$ 合法。考虑把数 $a$ 分解成极大二的幂和一个奇数相乘，即 $a=2^pv$。上面合法当且仅当存在整数 $r$，满足 $\frac{y(2t+y-1)}{2}=x$，即是 $2t-1=\frac{2x-y^2}{y}$，即是后面那一堆是奇数。拆开，原式即是 $\frac{2x}{y}-y=\frac{v_x}{v_y}2^{p_x-p_y+1}-y$，显然要求 $\frac{v_x}{v_y}$ 是整数，然后对 $y$ 的奇偶性分类讨论。若为奇数，那么希望 $p_x-p_y+1>0(p_y=0)$，相当于没有要求；若为偶数，那么希望 $p_x-p_y+1=0$，即 $p_x+1=p_y$。把结论推广到区间上，两个距离为 $len$ 的数 $x,y$ 如果可以同时保留，那么首先说明 $v_y|v_x$，然后可以具象化前面的条件，即从前往后低看，元素的 $2$ 的次幂要么加一要么归零，这样就可以推出区间上的结论了。统计答案时有些东西需要注意。

CF283C

一道比较巧妙的背包题。首先题目中有一个特殊性质，即每个点的出度不超过 $1$，入度也不超过 $1$，也就是说判掉环之后只会剩下链。于是可以先对每条链计算出最少的代价（就贪心的买 $0,1\dots$ 个），减去这些值之后有一个方法是考虑买一个物品的时候也捆绑着买所有比它多的物品，这样就维护了数量上的性质，而且也不会重复统计。这样一来就只需要做一次暴力的完全背包就可以了。

CF283E

正难则反，考虑有多少个三元组是不合法的。会发现不合法的三元组应该有一个性质，即有一个点的出度为 $2$，那么我们只需要统计进行那么多次操作之后有多少点的出度比较多。用增量法来考虑，假设用线段树已经维护好了点（值） $x$ 的出边情况，那么对于 $x+1$ 的只会有两种询问有影响，即右端点刚好为 $x$ 的和左端点刚好为 $x+1$ 的，用指针维护一下区间取反即可。最后答案会是 $C_m^2-\sum C_{d_i}^2$，复杂度 $O(N\log N)$。

CF311B

板子的斜率优化，但由于有段时间没写过了调了很一会。猫希望人出发的时间是 $a_i=T_i-D_i$，只能晚不能早，所以问题变成了给定一个长度为 $m$ 的序列，砍成 $n$ 段，最小化个元素到本段第一个元素的差之和。显然令 $f_{x,y}$ 代表 $[1,y]$ 分成了 $x$ 段之后的最小代价，有

$f_{x,y}=\min\limits_{i=0}^{y-1}f_{x-1,i}+a_y\times(y-i)-(s_y-s_i)$

$g_i+s_i=(g_y+s_y-a_y\times y)+a_y\times i$

对于上面的柿子，查询方面，$k$ 单增；插入方面，点是 $(i,g_i\dots)$，单调向右，所以整体维护一个单调队列即可。然后就可以转移了。

CF340C

比较基础的题目。答案应该是：

$\frac{\sum\limits_{i=1}^ma_i(m-1)!+\sum\limits_{i=1}^m\sum\limits_{j\ne i}|a_i-a_j|(m-1)!}{m}=\frac{\sum\limits_{i=1}^ma_i+\sum\limits_{i=1}^m\sum\limits_{j\ne i}|a_i-a_j|}{m}=\frac{\sum\limits_{i=1}^ma_i+\sum\limits_{i=1}^msum_x-a_x(m-x)}{m}$

CF340E

首先有个性质就是说所有没有数的位置都可以分成两类，一类是这个位置对应的数已经被使用过的，另一类是没有被使用过的，显然同类之间的元素是可以看成没有差异的，所以就可以大大地简化状态。令 $f_{x,y}$ 是第一类有 $x$ 个，第二类有 $y$ 个时的合法方案数，然后考虑当前的转移。默认先转移前面的，于是又有两种可能，一种是这个位置使用了第二类的位置对应的数，那么就有一个第二类的位置变成了第一类，有 $y$ 种可能，转化出的问题是 $f_{x,y-1}$，否则说明没有任何影响，有 $x$ 种可能，转化出的问题是 $f_{x-1,y}$。边界方面，$f_{x,0}$ 不说了，而 $f_{0,x}$ 是经典的错排问题也没什么好说的。然后就没了。

CF362E

一种相当于是网络流中思想层面的东西，一条边的容量是可以动态增加的，增加了之后重跑增广路就可以找出这次增加对最大流的影响。这个过程底层上是贪心的，所以可以保证最后找出来的流是最大的（即费用被完全利用）。

CF213E

一道哈希题目。有一个技巧是假如要给一个序列中的所有元素都加上一个值，那么这个过程是可以做到 $O(1)$ 的，于是在 $x$ 的变化过程中 $A$ 的哈希值就是可以维护的。然后可以把在 $A$ 中的那些元素按在 $B$ 中的顺序拎出来哈希，比较是否相同即可。$B$ 的哈希由于每次只会拿进来一个数踢出去一个数，所以可以用线段树单点修改整体查询（虽然区间修改区间查询目测也是可以实现的）。复杂度 $O(N\log N)$。

CF321E

显然用 $f_{x,y}$ 代表前 $x$ 个人用 $y$ 条船的最小代价。按船转移，简写一维是：

$f_{x}=\min\limits\{g_i+cost(i+1,x)\}$

其中代价函数可以用二位前缀和来表示，斜率优化是不可能了，于是考虑决策单调性。四边形不等式满足得非常显然，考虑把二位前缀和对应的矩阵范围画出来，会发现对于 $a<b<c<d$，$cost(a,d)+cost(b,c)$ 对应的矩形可以完整覆盖 $cost(a,c)+cost(b,d)$ 的矩形，甚至会多出来一部分，于是就可以用决策单调性了。还有一个 CF868F 也是差不多的，只是那道题的代价不能直接计算，要在每一层里动态第计算（计算次数可以控制在 $N\log N$ 级别）。