CF2100题口胡记录

本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16736191.html

打*表示看题解后才懂

打^表示想错了

可能有些题和题解不一样，也许是口胡错了（？）

有些题你发现这里没有可能是以前做了，这里就不补了

CF1734E*

首先整行整列加没影响，于是可以构造任意合法矩阵后满足对角线性质

对于每个 $a_{i,j}$ 考虑用 $i,j$ 表达式表达出来，根据上面的性质，如果只对 $i,j$ 单独操作是没影响的，于是必须对同时含有 $i,j$ 的项进行操作，考虑 $i\times j$，由于 $n$ 为质数，所以符合条件

CF1729G

首先暴力kmp一下（我在说什么？）

然后设 $f_{i,0/1}$ 表示以 $i$ 结尾且 $i$ 这个位置（以其末尾）取或不去的最小段数

假如 $i$ 这个位置不能完全匹配 $f_{i, 0/1}=\min(f_{i-1,0},f_{i-1,1})$

可以匹配就是 $f_{i,1}=min{f_{i-|t|,0},f_{i-|t|,1}}$，$f_{i,0}=min_{j=1}^{|t|-1}f_{i-j,1}$

方案那个数组顺便统计就行

CF1725F

显然，对于每个 $w_j$，我们可以令它每一步长度都为其二进制下1的最低位（因为更大的步数必然可以由小步数组成），现在我们相当于只有30种步了（$\log_2w_j$）

考虑对于每种步处理。设当前二进制最低位1为 $2^k$，若 $R_i-L_i\geq 2^k$，则无论在哪一列都能走到。

然后考虑 $R_i-L_i<2^k$，可以发现一个性质，就是无论怎么走，$L_i,R_i$ 对 $2^k$ 取模不变。因此我们可以让他们全部走到最前面。

为了方便处理，我们把范围当做是 $[0,2^{k+1}]$，设当前区间为 $[x,y](x-y<2^k)$

• 若 $x\bmod 2^k>y\bmod 2^k$，此区间为 $[x,y],[x+n,y+n]$

排序后就是个区间覆盖问题

• 若 $x\bmod 2^k\leq y\bmod 2^k$，此区间为 $[x,y+2^k]$

CF1684E

考虑贪心

假如每次操作，我们考虑使对 $\text{DIFF}$ 变小或让 $\text{MEX}$ 变大

而 $\text{DIFF}$ 每次最多减小1， $\text{MEX}$ 每次最少增加1，所以显然对 $\text{MEX}$ 操作更优，那么 $\text{MEX}$ 值就已定了

考虑对 $\text{MEX}$ 操作时如何使得 $\text{DIFF}$ 变化最小

假如我们从1个位置移到另一个位置， $\text{DIFF}$ 不变

CF1671E

考虑两个子树交换不产生新贡献的情况

那么显然，这两子树AB数量必然相等。反推过来，两子树AB数量不等交换必然产生新贡献

思考后我们可以尝试推广，我们对所有可操作数的数量从小到大排序，按顺序操作即可

于是设 $f_i$ 表示以 $i$ 为根子树的方案数，$S_i$ 表示以 $i$ 为根子树内 A 的个数

$S_x$ 直接树形dp即可，$f_x$ 状态状态转移如下：

• 若 $S_{lx}=S_{rx}$，则 $f_x=f_{lx}\times f_{rx}$
• 若 $S_{lx}\ne S_{rx}$，则 $f_x=2f_{lx}\times f_{rx}$

$f_1$ 即为所求

CF1668D

设 $f_i$ 表示以 $i$ 结尾最大贡献，$s_i$ 表示前缀和，显然可以列出一个dp：

$$f_i=\max{}\left\{\begin{matrix} f_j\;\;(s_j=s_i) \\ f_j+(i-j)\;\;(s_j<s_i) \\ f_j-(i-j)\;\;(s_j>s_i) \end{matrix}\right.$$

第一个式子显然可以用个map来维护，然后看后两个式子，我们可以把和 $j$ 有关的放一起，那就是 $f_j-j+i$ 和 $f_j+j-i$

$i$ 显然可以后面处理，然后拿个单调栈维护就行，2式栈底到栈顶满足 $s$ 从小到大，3式就是从大到小

CF1666J

考虑区间dp

设 $dp(l,r)$ 表示一个子树包含 $[l,r]$ 的最小代价

显然我们要枚举一个根节点 $k$，然后左右子树可以先分别统计贡献 $dp(l,k-1)+dp(k+1,r)$

然后考虑跨区间的。我们在考虑这个问题之前可以先思考另一个问题，假如 $i\notin [l,r]$ 的话，我们其实可以用个 $f_{l,r}$ 表示 $\sum_{i\notin [l,r]}\sum_{l\leq j \leq r} c_{i,j}\times d_{j,k}$ （$k$ 表示这个区间的根节点）

为了方便转移，我们可以把它当成代价记在 $dp(l,r)$ 里面

现在重新考虑跨区间问题，我们发现对于 $[l, k-1]$ 和 $[k+1, r]$ 区间我们只需要考虑新增的两条边了

我们对 $c$ 做个二维前缀和 $S$，那么上面的代价就是 $S\left ( (l,k+1),(k-1,r) \right ) \times 2$

然后答案就是 $dp(1,n)$

和 $k$ 有关的代价随便乱搞一下就行

CF1660F2

考虑每次操作，会让 - 的数量-2，+ 的数量+1，也就是它们之间的差减少3。所以一个区间符合约束，必然是减号数量大于等于加号数量，且它们之间的差为3的倍数。

在这种约束情况下，是否有解呢？可以发现，当减号数量大于加号数量加一时，必然存在两个连续的减号，于是我们就必然存在一种在合法约束条件的构造。

回到原问题。由于是求合法区间个数，不妨先设个前缀和 $S$，$S_i$ 表示前 $i$ 个符号减号数量减去加号数量的结果。则一个合法区间 $[i+1,j]$ 必然满足以下条件

1. $i<j$
2. $S_j\equiv S_i\pmod 3$
3. $S_j-S_i\geq 0$

对于约束1，我们显然可以按顺序处理

对于限制2，我们似乎只需要开一个大小为3的数组即可

但加上限制3呢。其实我们只需要把数组改成树状数组，开3个树状数组维护即可

时间复杂度 $O(n\log n)$

CF1654D*

首先按照题目约束必然是棵树，我们任意定义一个点为根，假设它的分量是 $1$，则必然每个节点 $i$ 都可以用最简分数 $\dfrac {c_i}{d_i}$ 来表示它的分量。

要使所有都为整数，根节点至少为 $\text{lcm}_{i=1}^nd_i$，现在我们就是要求这个值的最小值

我们先推一下转换式子，假设节点 $i$ 为 $\dfrac {c_i}{d_i}$，节点 $j$ 为 $i$ 的儿子，两个之间的比为 $x:y$，则 $j$ 的分量为 $\dfrac {c_iy}{d_ix}$，，也就是每次相当于是乘上 $\dfrac{y}{x}$

一个常见的套路是维护每个质数个数。必然的，对于任意一个 $n$ 以内的数，其质因子个数不超过 $\log n$ 个。所以对于 $x,y$ 我们可以暴力更新当前分母每个质数的指数（可以为负），然后我们要求的lcm就是在考虑所有情况下的每个质数的指数最大值。

根节点求出来后，显然，每个节点可以直接顺推求出。

时间复杂度 $O(n\log n)$

CF1650G

题目就是求 $s,t$ 的最短路与次短路条数。

最短路条数直接bfs一遍可以求出。

次短路的话我们按最短路跑出的层次遍历，第 $i$ 层的某个节点可以从同层的最短路或第 $i-1$ 层的次短路转移过来。

时间复杂度 $O(n)$

CF1628D1

博弈论，由于是easy任务，往dp方向考虑。

可以发现，加入前面的已定，后面的情况是独立的。于是可以设 $f(i,j)$ 表示后 $i$ 个数至少 $j$ 个加的答案。

必然的，$f(i,0)$ 为0，因为此时Bob必然全出负，Alice为了应对只能出0

对于 $f(i,j)$，我们假设Alice出的是 $t$，那么Bob的抉择有两种，$+t$ 或 $-t$，那么可以推出转移式子：

$$f(i,j)=\min(f(i-1,j)-t,f(i-1,j-1)+t)$$

易证 $f(i-1,j-1)\leq f(i-1,j)$，随着 $t$ 变化，$f(i-1,j)-t$ 必然单调下降，$f(i-1,j-1)+t$ 必然单调上升，Alice要使 $f(i,j)$ 最大，显然是取这两个函数的交点，也就是另 $t=\min(\dfrac{f(i-1,j)-f(i-1,j-1)}2,k)$

答案即为 $f(n,m)$，复杂度 $O(n^2)$

CF1626D

为了方便处理，我们可以把相同的合并，变成 $m$ 段，每段有一个数 $a_i$ 和权值 $w_i$，此时最终答案相当于是 $2^X+2^Y+2^Z-n$，所以我们的目标就是让 $2^X+2^Y+2^Z$ 最小。

在不考虑前两段的代价下，最后一段显然 $\sum w_i$ 越小就可以使 $Z$ 越小，也就是我们可以贪心使前面往后取

但我们需要考虑前两段的代价，但我们可以直接枚举代价 $X,Y$，显然 $X,Y\leq 31$，于是前两段的最大代价已定，我们就让它尽量往后取，使第三段的代价最小。

复杂度 $O(n\log^2n)$

CF1621D^

右下的正方形是肯定要清理的

考虑左上正方形的四个对角格子，要使其移动，则左下和右上的正方形的各自四个对角格子至少清理一个。

而清理完这个，我们就可以构造出一种方案，使得全部移动到右下正方形，具体可以考虑原先的一行移动成一列。

时间复杂度 $O(n^2)$

CF1614D^

设 $dp_i$ 已构造序列的 $\gcd$ 为 $i$ 的最大值，设 $cnt_i$ 为 $i$ 的倍数的个数，则 $dp_i$ 初始值为 $cnt_i\times i$

考虑转移，枚举上一个 $\gcd j$，所以 $dp_i=\max_{i|j}(dp_j+(cnt_j-cnt_i)\times i)$

由于 $i$ 的倍数均摊下来是 $\log n$ 个，所以复杂度为 $O(n\log n)$

CF1606E^

设 $dp_{i,j}$ 为剩 $i$ 个人最大血量为 $j$ 的方案数，显然，这轮每人减 $i-1$ 血量

可以考虑枚举这一轮覆灭 $k$ 个人，则有 $C_i^k$ 种选人方法，这些人的血量可以为 $[1,i-1]$

于是就有 $dp_{i,j}=\sum_k dp_{i-k,j-k+1}C_i^k(i-1)^k$，$dp_{n,x}$ 即为所求

时间复杂度 $O(n^3)$

CF1605D

可以考虑可移动的两点，其最高位1必然相同（否则最高位min值为0,1与0异或值为1），可以发现这是个充要条件

考虑每个点都无法移动，由于任何2的整数幂最多占原数的一半，所以必然存在这样的构造

复杂度 $O(n)$，可能带个 $\log$

CF1599H

先考虑求下边界，询问整个棋盘左下和右下的距离

然后通过移动距离长的到某个地方，使两点到矩形左右边界距离一样

取其终点询问，其距离就是到下边界的距离

剩下两个边界同理，共询问8次

CF1593F

设 $dp(i,a,b,k)$ 表示前 $i$ 个字符凑的数模 $A$ 为 $a$，模 $B$ 为 $b$，且染成红色的数量比染成黑色数量多 $k$ 是否可行

转移考虑枚举这个数染红还是染黑

• 染红，转移至：$dp(i,(10a+s_i)\bmod A,b,k+1)$
• 染黑，转移至：$dp(i,a,(b*10+s_i)\bmod B,k-1)$

答案就是，$dp(i,0,0,k)$ 为1时 $|k|$ 的最小值，输出方案记录一下由哪里转移过来即可

CF1575L

设 $dp_i$ 表示前 $i$ 个数中 $a_i$ 生效的最长长度，显然有 $dp_i=\max dp_j+1$

考虑 $j$ 要满足什么条件，显然 $a_i>a_j$，而且中间的数必须足够，即 $a_i-a_j\leq i-j$，移项得 $i-a_i\geq j-a_j$

还有个隐藏条件 $i>j$，综合起来就是:

• $i>j$
• $a_i>a_j$
• $i-a_i\geq j-a_j$

显然cqd

（其实结合后两个条件可以推出第一个条件，所以其实二维偏序即可）

CF1560F2

对于一个数，从大往小处理，假如某个次数出现超过 $k$ 次，就这个数加1（进位照常），后面全改0，然后从头来过

CF1555E

显然先双指针，对已定最小值求当前最小最大值

然后拿个线段树来就行，支持区间加和区间最小值

时间复杂度 $O(n\log m)$