水题乱做 - 2023 - 10

10 月了，是不是马上要 NOIp 了，是不是马上要省选了 /fad。

CodeForces-1007C

转化为找平面上的一个点，对于两维同时倍增，如果都不在对应区间，则同时缩小步长。

CodeForces-995F

容易进行朴素 dp，$f_{u,i}$ 表示 $u$ 子树，根 $\le i$ 的方案，发现转移就是点积和前缀和，所以多项式度数 $\le n$，直接插值即可。

Luogu-P7554

对于询问进行二分，check 是查询区间某个区间内的值个数可以主席树维护。

CodeForces-788E

发现 $p_1$ 和 $p_5$ 根本不重要，可以直接移到 $p_2$ 和 $p_3$ 上，对于每个值域开线段树维护。

CodeForces-724E

暴力做法是建出网络流，随后将最大流转化为最小割，直接 dp，设 $f_{i,j}$ 为前 $i$ 个位置，有 $j$ 个割了 $s$ 的边，转移容易算贡献。

CodeForces-724F

首先考虑如果不算重，可以钦定根为重心，并且接儿子大小从大到小，背包的合并是平凡的。

CodeForces-1874D

列出 dp 转移式，转化为从前往后推的形式，发现最小化的其实是 $\sum\frac{s_i}{a_i}$，这个东西有决策单调性，直接分治转移。

CodeForces-1874E

令 $f_{i,j}$ 为长度为 $i$ 的排列，进行快排复杂度 $\ge j$ 的个数，转移可以通过点值形式，最终插值出这个多项式的每一项系数。

Luogu-P9699

对于转化对应进制后长度 $\ge 3$ 的，可以直接枚举每个的 base，另外的可以直接枚举差的因数计算。

AtCoder-ARC124E

将代价转化为每个位置选择一个球，可以分选择的球是自己的还是上一个的转移，为了防止算重，还需要保证至少一个间隔没有传递，dp 时记录一维。

CodeForces-1874B

每一位独立，由于 $(a,b,m)$ 只有 $8$ 种，对应的 $(c,d)$ 有 $4+1=5$（有一种不关心）种，所以只有 $5^8$ 个本质不同的状态，直接预处理。

Luogu-P3587

对于每一个位置随机赋权，保证每种颜色的权值异或和为 $0$，条件被转化为区间异或和 $=0$，直接开 map 记录。

Luogu-P9702

枚举割了哪个对角线，两部分的直径一定是两遍的两个端点之间的长度，可以类似区间 dp 进行预处理。

Luogu-P6822

转化为有向边，对边建点，切换边时如果变大有对应边权差的权值，变小权值为 $0$，边转向定义为走一步，边权为原边权，直接跑 dijkstra。

Luogu-P5538

点分治，对于每个分治重心的每个子树，都处理出那 $\log V$ 个不同的值，两两枚举，由于 $d$ 很小，因此复杂度有保证，虽然很多 $\log$。

CodeForces-1876C

对应的 $i\to a_i$，题意转化为选择基环树上一个点集，使得点集间无边，点集并上一步能到的点集为全集，对树上拨叶子，环上直接做。

CodeForces-1876D

第一个条件告诉我们只需要求两个相等的，划分出两两交在一起的段，他们的相对顺序是捆绑的，直接用并查集并起来。

CodeForces-241D

真逆天，只需要保留 $< 32$ 的所有值下来 dp 即可，她声称用 $\le 24$ 的数就可以完成构造了。

CodeForces-241E

不能到达 $n$ 或者 $1$ 不能到的点是没用的，对于剩下的点，$d(1,i)$ 是固定的，对于 $d(1,i)$ 这些值做差分约束。

Luogu-P5590

同上一题，做差分约束即可。

CodeForces-813D

拆点后网络流建图，转移的边只要给相邻的之间连，直接跑费用流，注意相等的之间和 $\bmod 7$ 同余之间要连不选择直接转移的。

CodeForces-818G

同上一题，把真实源点和虚拟源点之间的流量限制改为 $4$ 即可，她大概是想要卡掉上一次的 dp 做法。

CodeForces-1343F

发现最后一个值的性质是恰好出现一次，但是第一个值也有这个性质，因此先枚举第一个值，随后一直取只出现一次的数，构造后 check。