水题乱做 - 2023 - 9

哎，9 月了，还在这里摆，忍不了了！

CodeForces-1864G

观察一下性质，然后直接数数，最后是一些阶乘的乘积。

Luogu-P5631

按照边权线段树分治，用并查集维护连通性。

CodeForces-1615F

将操作做差分转化为交换元素，求每个间隔对答案的贡献。

CodeForces-1354G

先通过随机寻找一个石头，再通过倍增和二分来寻找第一个礼物的位置。

CodeForces-838C

观察先手必胜的字符串特征，随后随便状压 dp 即可。

Luogu-P7565

要找一个最长的且使两边子树大小相等的最长链，直接点分治。

Luogu-P5105

可重集去重后价值不变，且连续区间可以快速算出，使用线段树维护。

Luogu-P6891

直接 dp 时合法的 dp 位置是一段区间，记录区间把 $O(n^2)$ 优化为 $O(n)$。

Luogu-P7212

按照题意模拟，合并时采用启发式合并即可，注意模拟时的细节。

Luogu-P9597

容易写出暴力 dp，带修改直接使用动态 dp 即可。

Luogu-P9599

通过询问相邻两个与三个的结果，确定出先对大小关系，直接模拟构造。

CodeForces-1863E

完成每个任务的结束时间确定，直接拓扑，合并时贪心往后放。

CodeForces-1863F

从外到内区间 dp，能转移到的可以被表示为区间前后缀和某一位为 $0/1$，在左右端点打标记。

CodeForces-1863G

建出基环树，每个点可以被每个入点表示，环上会被多算，删除重复贡献后相乘。

CodeForces-1861F

二分答案后转化为最小割，枚举右边每个点被割至哪里，可以 $2^4\cdot \log$ 进行 check。

CodeForces-1866L

枚举每一个 $k$，随后可以 $O(k)$ 数出能得到多少个球。

CodeForces-1866G

二分答案，每个数可以处于一个区间，用堆来模拟贪心即可。

Luogu-P5812

通过观察性质来减少有效点数，随后建图跑 dijkstra 即可。

CodeForces-1267G

计算出每次操作两种方式各自的期望收益，贪心选择较大的。计算到达每个状态的概率可以背包。

CodeForces-1120D

每个叶子都至少对应一个祖先，树形 dp 并记录转移方案，构造可以通过转移推算。

CodeForces-1303G

点分治后转化为选一个一次函数和一个点，将一次函数插入李超树中，再枚举点查询。

AtCoder-ARC094F

特判特殊情况后，只需要相邻不同且和 $\bmod 3$ 同余，可以直接 dp 计数。

Luogu-P5331

cdq 分治过程中优化费用流建边。

Luogu-P9596

答案为一个数之前大于他的个数最大值，观察性质并弱化条件，直接使用线段树维护。

Luogu-P9531

按照边权排序，每条边控制的 $X$ 是一个区间，求出每条边所控制的区间，询问双指针。

Luogu-P5776

一个边双联通子图可以进行耳分解，反向耳分解来构造边双联通子图，可以状压 dp 计算。

AtCoder-ABC318Ex

推一波式子之后发现方案数是一个多项式 exp 的形式。

AtCoder-AGC003D

将每个数的完全立方因子除去，每个数恰好对应一个数，二选一，贪心选多的。

CodeForces-536E

离线询问，扫描限制，每个边权为 $0/1$，直接树剖维护即可。

CodeForces-845G

可以去环上绕一个圈后回来，异或上的恰好是环上边权异或，把所有环上边权异或和插到线性基里。

CodeForces-724G

与上一题类似，算每一位对于答案的贡献，要么是全部，要么是恰好一半，直接计算。

CodeForces-1801D

按照演出次数与剩余的钱当作两位关键字，直接跑最短路。

CodeForces-CF1801E

有效合并次数为 $O(n)$，可以通过哈希找到每一次的下一个有效合并点对。

Luogu-P8162

枚举最终选择的支持者数量，观察性质后可以直接做最优化 dp。

Luogu-P5100

建出分层图，横向、竖向移动可以分别开一层，随后跑最短路。

AtCoder-ABC219H

吹灭的蜡烛一定是一个区间，可以将原长和烧掉的长度分开计算，做区间 dp。

CodeForces-1327F

每一位是独立的，分别找出限制，随后前缀和优化 dp。

CodeForces-1801F

暴力 dp 时发现第二维的有效值只有 $O(\sqrt V)$ 个，直接优化 dp。

Luogu-P9631

合法的数可以表示为某一个二进制位为 $1$。直接用吉司机线段树维护每个二进制位 $1$ 个数。

Luogu-P3488

判定形如二分图是否存在左部点完全匹配，Hall 定理转化后维护最大子段和状物。

Luogu-P9607

极值分治，枚举短的那一边，找出 $\gcd$ 不同的 $\log$ 个位置计算。

CodeForces-1693D

暴力做法是枚举左端点后向右 dp，遇到相同的 dp 值直接 break，一个 dp 值最多被更新 $O(1)$ 次。

CodeForces-1693C

直接倒序跑 dijkstra，被更新到的 dis 一定是递增的，因此选择保留的一定是一段签注。

Luogu-P9613

建出 ACAM。ACAM 节点数是 $O(\sum len)$ 的，可以直接矩阵快速幂优化转移。

Luogu-P9606

求出最长的回文后缀，可以直接 manacher。

CodeForces-1379E

先构造一条长度为 $k-1$ 的类链形状，然后在下面接一个满二叉树。

Luogu-P6623

每个点每个二进制位的贡献是有循环的，直接对于每个循环节长度开差分数组即可。

Luogu-P6672

由引理：对于一个和为 $0$ 的整数序列，则其所有循环位移中恰好有一个满足所有的前缀和都是正数。直接转化后套用。

Luogu-P8456

建出圆方树，点双之间的点对容易计算，同一个点双内如果连结两种颜色的只有两个，则减一。

CodeForces-1152F2

从小往大加数，状压记录一下前 $m$ 个数的填写情况。

Luogu-P4870

做法同 AtCoder-ABC219H，增加一个滚动数组即可。

Luogu-P3793

详见 浅谈 $O(1)-O(n)$ rmq。

Luogu-P4007

本质不同的状态大约只有 $200$ 种，直接矩阵快速幂优化转移。

Luogu-P8688

根据卢卡斯定理，原问题转化为数位 dp，直接按照数位 dp 的方式转移。

UVA-1464

建出圆方树，必经点是圆方树路径上的圆点个数。

Luogu-P8946

根据转移分类，特殊转移数量较少，用数据结构（数组）优化转移即可。

CodeForces-1418F

枚举 $x_1$ 与其因数，用 set 维护可行的 $y$，列出限制即可快速查询。

CodeForces-1017H

对于每一种不同的 $k$ 分别跑莫队，注意每次根据询问数量取块长。

CodeForces-1418E

对于每一块盾牌分别算贡献，$\ge b$ 与 $< b$ 的盾牌产生贡献的概率是相同的。

CodeForces-875E

二分答案，枚举一维，用 set 维护另一维的可行位置即可，转移时变化的元素个数是 $O(1)$ 的。

CodeForces-1096G

算出 $n/2$ 个数能表示出的所有数的集合即可，可以用多项式快速幂优化。

CodeForces-875F

转化后题意转化为最大生成基环树，类似最小生成树地贪心即可。

CodeForces-875D

进行极值分治，枚举短的一边，随后二分另一边的最远距离。

Luogu-P9546

存在 $0$ 时可以根据段的长度奇偶性算出胜负，不存在 $0$ 时根据讨论可以转化为存在 $0$，线段树维护之。

CodeForces-1867F

只需要找一棵节点数最少的树使得其未出现，然后上面挂一条链。这个树节点数很小，可以暴力。

CodeForces-959F

离线询问，维护线性基，没插入线性基的元素能对答案产生 $\times 2$ 的贡献。

CodeForces-1207F

根号分治，小于根号的模数修改时暴力，大于根号的模数询问时暴力。

AtCoder-AGC058F

每条边上加一个点，再挂 $P-1$ 个点，问题转化为给边定向，容斥后可以树形背包解决。

Luogu-P6620

将多项式转化为下降幂多项式，进行一个式子的推后可以快速计算。

AtCoder-ARC165D

同时考虑限制的每一位，相同则跳过，不同时从小的向大的连边，然后缩点，同一个点内的一定相等，最多做 $O(n)$ 轮。

AtCoder-ARC165E

考虑每一个点被操作的概率，以这一个点为根，可以二维树形背包计算形如切 $x$ 个子树，最终剩 $y$ 个点的方案。

AtCoder-ARC165F

交换次数最少只需要对于 $a_i < a_j\land b_i < b_j$ 的数对 $i$ 在 $j$ 前，主席树优化建图跑拓扑。

CodeForces-842D

建出 trie 数，每次异或相当于把某一层的左右儿子 swap，直接在 trie 上二分。

CodeForces-848C

最大坐标 $-$ 最小坐标可以拆开成相邻两个求和，转化为三维偏序后 cdq 分治。

CodeForces-449E

枚举长度，列出式子化简后需要处理 $\sum_{i=1}^{x-1}\gcd(i,x)$ 状物，可以筛 $\varphi$ 后计算。

CodeForces-364D

一个数有一半概率出现在最终集合中，直接随机，确定一个数后贪心选最大的满足条件的 $\gcd$。

CodeForces-1019C

先进行一遍贪心选择，满足走一步能到所有点，随后选择的点之间构成 DAG，跑拓扑来满足没有相邻的限制，距离最多再走一步。

CodeForces-868F

设 $f_{i,j}$ 表示前缀 $i$，操作 $j$ 次的最小代价，可以决策单调性优化转移。

Luogu-P5574

同上题，统计区间 cost 时可以使用树状数组，复杂度多一个 $O(\log n)$。

CodeForces-1305G

新建一个虚点，转化为最大生成树。从大到小枚举边权，点对可以通过枚举子集得出。

CodeForces-1774G

寻找正负抵消的限制后，将线段构造成树形结构，倍增寻找最近的满足条件的祖先。

CodeForces-1553H

按照值域建出线段树，某一位异或 $1$ 等价于交换某一层的左右儿子，build 时直接记录所有交换情况的答案。

Luogu-P9595

同上一题，线段树存储的信息与合并方式修改即可。

CodeForces-1553G

$s,t$ 均操作则都为偶数，答案最大为 $2$，$0$ 容易判断。对于每一个连通块维护操作一次能产生的质因数，与能合并的质因数。

CodeForces-1553I

根据 $a$ 可以推断出连续的区间形态，限制是相邻段不能可拼接，容斥后可以多项式分治乘法优化转移。

Luogu-P4632

离线后扫描线，对于每个数维护 $(i,pre_i)$，二分答案后需要所有 $i>r$ 的 $pre_i\ge l$，可以线段树区间查询 check。

CodeForces-700D

莫队求出所有出现次数的数的种类数，不同的出现次数只有 $O(\sqrt n)$ 个，询问模拟即可。

CodeForces-1870F

对于同一个 $k$ 进制位数的，字典序递增，容易求解一个数字典序，可以而分出中间一段 $x=rk_x$ 的区间。

CodeForces-1870G

答案递增，对答案直接依次 check，每次 check 可以对 $cnt$ 数组倒着扫，容易数据结构优化单次 check 到 $O(\sqrt n\log n)$。

CodeForces-1870H

建出最小树形图树，每次修改为一个点到根路径 $+1$，求点权 $=0$ 的价值和，可以树剖或 set 维护 dfn 序。

CodeForces-1334G

套路的将匹配转化为式子的形式，然后用多项式来求出式子的每一项的值。

Luogu-P8991

由于数据随机，单调栈长度期望根号，因此选择区间长度也 $\le \sqrt n$，直接扫描线枚举每个区间。

Luogu-P8985

先按照贪心策略将 $a$ 排序，随后 $\log$ 对 $a$ 分块，块内状压统计四维偏序的答案。

Luogu-P8990

合法性与贡献都可以被表示为三种边的数量，直接用线段树维护每次操作后三种边的数量并统计答案。

CodeForces-632E

直接将所有物品看作一个多项式，进行多项式快速幂。

CodeForces-340E

算出所有已经被限制的位置后，枚举不合法 $a_i=i$ 的位置个数进行容斥。

CodeForces-1034C

枚举最终被划分成的块数，存在合法划分当且仅当 $\frac{S}{x}\mid s_u$ 的数量为 $x-1$，随后枚举因数 dp。

CodeFocres-1187G

最终时间一定 $\le n+k$，直接间分层图跑费用流。

CodeForces-1059E

算出选择每个点后能覆盖到的最上面的点，随后从下往上贪心选择。

CodeForces-1059D

二分答案后算出对于所有点合法区间的交，容易 $O(n)$ 进行 check。

Luogu-P3260

结论：物理可达即光路可达。最小割 $=$ 最大流，给有交的原件间连边跑最大流。

Luogu-P5504

操作的左右端点种类一定相同，列出暴力转移 dp 后可以对于每一种颜色开李超树来优化 dp。

CodeForces-1452G

如果 Alice 不动，到每个点的时间可以 bfs 求出。为每个点找出 Alice 的最终点可以点分治。

CodeForces-576E

线段树分治，更新边颜色的操作可以在分治到线段树叶子节点时加入。

Luogu-P5381

每个函数都是凸的，因此所有函数的和也是凸的，直接用 bit 维护每个点的函数值，询问时可以三分。

Luogu-P9655

从下往上做，维护每个点子树内到每个点的括号序列每个值的个数，合并时可以 dsu on tree 并打标记。

Luogu-P9654

连续操作的长度不会超过 $3$，直接 dp 即可，构造需要暴力分讨。

Luogu-P4340

第一个非乘法即以后的都会被抵消，只要考虑第一段连乘的贡献即可，容易使用线段树维护。

CodeForces-1172C2

考虑 dp，设 $f_{i,j}$ 表示点了 $i$ 个 upvote，$j$ 个 downvote 的概率，答案容易算出。

CodeForces-689D

枚举左端点，前者递增，后者递减，可以直接二分出两者相等的区间。

AtCoder-ABC077D

在 $\bmod k$ 意义下建图跑最短路，建边是容易的。

CodeForces-482C

统计出每个状态下有多少个串是无法确定的，随后将猜的位置集合状压 dp，记录所有串的期望之和。

CodeForces-482D

直接 dp，考虑子树内选择了奇数个还是偶数个节点染色，dp 时容斥掉算重的方案。

CodeForces-1799G

直接容斥，列出容斥的式子后，发现可以先对每组内做类似背包的 dp，再对组间做类似背包的 dp 即可。

CodeForces-1313E

先通过 exkmp 求出 $a,b$ 的前后缀与 $s$ 的 LCP，随后容斥掉无交的区间，可以双指针扫描。

CodeForces-266E

直接线段树维护区间答案，合并时可以直接二项式定理 $O(k^2)$ 转移。

CodeForces-601E

线段树分治，层间转移时进行背包。

CodeForces-813F

线段树分治板子。

Luogu-P5382

容易证明最有情况下只有一个起始点，不然可以选较大的一个。求出传递闭包后直接枚举，传递闭包可以 bitset 优化。

Luogu-P6344

将所有的数二进制反转，发现转化为二维数点，直接扫描线。

Luogu-P5443

根号重构，对于一个块内的询问按照重量排序，随后对于边按称重量扫描线，用并查集维护连通块状态。

Luogu-P6246

首先可以 wqs 二分，cost 满足四边形不等式，具有决策单调性，可以直接二分单调队列进行转移。

CodeForces-1163F

转移时，根据改变的边是否在直径上与边权大小变化讨论，直径上边长的做法同 玛丽卡。

CodeForces-713D

首先二分求出每一个左上角的最大全 $1$ 正方形边长，询问时也可以二分，查询矩形 $\max$ 可以二维 st 表。

CodeForces-958E2

考虑 wqs 二分，直接进行 dp，dp 时需要记录上一个位置是否选择。

Luogu-P3620

同上一题 CodeForces-958E2。

Luogu-P5501

莫队二次离线模板，先莫队，再离线，再分块。

Luogu-P3629

找两次直径即可，也可以直接分类讨论。

CodeForces-1425B

观察到每个环要么一个人走完，要么两个人最终会和，直接 dp 即可。

CodeForces-1882E2

在排列的开头加一个 $0$，操作被转化为每次交换两个数，枚举最终的排列，随后建出图容易计算和构造。

CodeForces-1882D

如果定根，那么每次在根上操作即可，容易 dp，输出每个根只需要进行换根 dp 即可。

CodeForces-1879F

枚举 $x$，然后枚举 $\lceil\frac{a}{x}\rceil$，随后维护区间 $\max h$，区间可以转化为后缀，维护后缀最大的两个即可。

CodeForces-1879E

不难发现答案 $\le 3$，因为只要对于数进行三染色，每一个点一定有一种颜色不存在。而对于 $=2$ 的，可以直接判断。

CodeForces-1878G

首先逐位考虑，每一位一定是要么全 $0$，要么就是两边 $1$，中间一段 $2$，直接对链上位置离散化后扫描。

Luogu-P2605

做 $k$ 遍 dp，每次确定一个基站的位置，直接线段树优化 dp，容易在线段树上统计和改变贡献。

CodeForces-940F

直接跑待修莫队，求 mex 可以用分块 $O(1)-O(\sqrt n)$ 维护。

CodeForces-915G

如果确定 $n$，可以直接莫比乌斯反演计算答案，如果要对 $1\sim n$ 全部求答案，可以转化为 $n\log n$ 次区间加，做差分即可。