晚练计划总结

26-1-20

。。。

简单题目。

26-1-21

神秘 Trick，84 pts DP 很简单，优化状态设计就变成了。

26-1-25

缩点，有 DAG 性质就好做了。

26-1-26

没考虑直径以外的点，挂完了。

26-1-27

绿题，写的时候打错了一个字符，挂了 45 分。

26-2-25

P1772，看了一会发现数据范围支持跑遍 dij，然后跑完直接 DP 做完了。

26-2-26

P2254，简单题， DP 是容易的，然后单调队列优化一下转移就了。

26-3-2

P9921，直接过，预处理 (1,1)~(i,j) 的前缀 max 答案和 (i,j)~(n,n) 的后缀 max 答案再枚举每个点再二分一下即可。

我草 cdo 会，恐怖如斯，大概是像 Kingdom 那样做。

哦哦那我会双 log 做。

26-3-3

保龄啦~~~~~~

建图？？？何意味？？？我这几天图论专题白做了？？？

连的双向边，然后分讨，偶数解是有环，奇数解是无环但是可以选一些边（就是按按钮）使得图中每个点度数为奇数，由于无环所以是森林然后可以直接 dfs。

解释奇数解的具体做法：

不难发现图中如果没有环，那么这个图就是个森林。

由于没有环，不可能有偶数解，所以所有点的度数都得是奇数。

注意到想要改变度数只能改变这个节点和其父亲的连边情况，所以从叶子节点向上进行改变即可。

若一个点的当前度数为偶数，则连接其父边，使其度数变为奇数，这样对于每一棵树，除了根节点都一定可以合法，此时根据根节点的度数的奇偶性就可以判断是否有解（根节点无父边，无法在不影响子节点的情况下改变度数奇偶性）。

26-3-4

写爆搜，枚举每个用多少个，每选一个用多重排列数算贡献，然后发现每往后移一位，就有一位固定住，所以不用记录它的信息，直接塞进另外一个变量里（加一维），然后发现此时状态数只有，可以记忆化。

26-3-5

。。。

无语了。

注意点：

先考虑顺子，再考虑带牌，这样搜得快。
加一个形如 nmf(i, 2, 15) if (cnt[i]) now++; ans = min(ans, now); 这样的东西，方便剪枝。
（加强版）加一个优化，对于一个搜索过的状态，若当前解不优于原解，则剪枝，可以用类哈希加 map 实现。

26-3-8

建一个分层图，第一层是横向边，第二层是纵向边，两层之间建边权为 1 的双向边，还有连接到起点和终点的边。

这是一个点数边数都是的图，跑一遍优先队列优化 dijkstra 即可。

26-3-9

设表示使用跳板的最大节省距离，对跳板排序后 DP，可以显然地完成，考虑优化这个朴素 DP，发现使用朴素 DS（这里是树状数组）优化会因为跳板的终点与起点不相同而无法正确维护可选转移项，这时我们采取延后更新的方式解决这个问题，就是把对维护可转移项的 BIT 有影响的东西扔到一个优先队列里，然后等到队头的第一维偏序（行坐标）不大于当前起点的行坐标时更新，这样通过排序+延后更新的方式解决第一维，BIT 解决第二维，正确维护了偏序关系以供快速转移。

最后时间复杂度是。

26-3-10

DP加斜率优化，注意时间范围是。

26-3-11

DP，设表示考虑前头牛，第头询问牛的权值为时的方案数。

朴素和优化都是蛮好想的。

但是，对于同一头牛的多个询问，要的最小那一个，这个才是最严格的要求，而不是直觉上的最大。

26-3-12

反图，拓扑求最长路，然后依次考虑最长路为的点，由于长度相同，我们可以按字典序将其路径排序，来给下一个长度转移。

因为从小依次考虑，所以上一个长度的最长路的排名不仅可以用来确定选择哪些路径转移给当前长度的最长路，还可以据此对当前长度的最长路排序。

就是将所连接的边的边权为第一关键字，连接的上一长度的最长路的排名为第二关键字排序。

后半部分逐长度处理用 bfs 实现，因为 bfs 一层一层遍历的结构恰符合我们的需要。

26-3-15

爆零。

发现图是个森林后可以 DP 做。

设分别表示以为根的子树内，选 / 不选且答案为的最小花费。

有转移如下：

初始设。

注意不要设，这是错误的，因为此时没有贡献，答案不为，不符合状态定义。

26-3-16

场上 80 pts。

二分答案+DP。

设表示以为根的子树内，最多分出几条赛道，以及在分出最多赛道的情况下，连接的最长路径长度。

为什么这个状态是对的，有一个贪心证明：如果当前在子树内最多分出条赛道，如果分出条路径可以得出最优，那么分出条赛道，最多使子树外少一条赛道（使那条包含“ 牺牲了一条赛道而空出的边”的赛道寄掉），结果显然不劣。

注意转移时的贪心策略是从小到大找不是从大到小。

例子：，最优结果是，但从大到小遍历得出的结果是。

26-3-17

场上 40 pts，草，没写出来正解。

考虑朴素，优先队列优化成，然后发现只用枚举会使优先队列出队的，然后就可以优化成，过程实际上跟离散化相似。

26-3-18

场上思路从一开始就是走进了死路（一遍 DP 且根固定），本质上一定需要换根以通过简单的单一结构（即下文所提的“父节点-节点-子节点”形式连边）进行 DP 来找到复杂的最优答案。

第一遍 DP 是容易的，第二遍换根也不难，只提一下第一遍 DP 的状态定义：表示子树内，是/否作为 II 型连边的中间点，且所有 II 型连边均为“父节点-节点-子节点”的形式，的最大答案。

26-3-19

一道贪心，破局点是从答案序列的第一个位置考虑，结合原树节点编号互不相同的性质，分类讨论正确结构。

26-3-22

本质就是 bfs，但是要用“整层处理”的思想。

时间复杂度看起来很不对，但是事实上是的。

大概理解：一个点不会成为下一层，当且仅当队首与之有连边，所有点最多会被留下次，每次都会产生一次删除和拷贝，单次均摊复杂度，累计产生的复杂度是的。

26-3-23

神秘贪心，感性理解不难但是就很神秘。

然后场上还没写出来。

我菜完了。 /ll

26-3-24

二分答案，转化为 01 序列，考虑如何判定，设表示令第位为需要的最少自由个数，直接按题意模拟，转移是。最后判断队列中最后一个的是否小于等于自由个数即可判定。

26-3-25

考虑时的特殊性质，然后把特殊性质应用到一般就过了。

26-3-26

从大到小正着做是比较好想的，但是发现很难优化了，考虑从小到大反着做，由于从小到大是合并操作所以用并查集维护。

注意，虽然转移只用最优解，但是并查集合并要将所有的所有合法邻接节点都合并，否则后面无法正确查询。

26-3-29

P9322 超级棋子，难点在于发现马的规律。

公式为：

26-3-30

P4364 IIIDX，题解 To do。

26-4-1

P15567，直接 DP 算走五片荷叶（走四步）的方案，不管重复，发现仅有四元环会被多算，然后考虑如何减去四元环贡献，发现多算了 $四元环数量$ 次，可以使用 bitset 统计四元环数量，时间复杂度。

注意本题要开 int128。

26-4-2

第一题 P13308，可以用哈希表记录下所有的修改，还可以离线处理，只记录与询问有关的位置的修改。

第二题 P12247，二维偏序下的 DP，将条件排序后用树状数组维护最优值，注意 DP 时要取前缀 max 转移。

26-4-7

P15939。

考虑贡献直接算的条件，然后发现需要区间覆盖维护来求，ODT 维护后，算出下一个断点（未跨过的辣团子），再算一下单段贡献，就可以倍增，然后做完了。

26-4-8

P14645。

去除英雄不能重叠的条件，显然最远点到达后就不会对其他点产生影响了，而到最远点的英雄显然也最早出来。

bfs 求所有可达点的距离，将所有堡垒的距离从大到小排序后发现答案就是 d_i+i-1$。

怎么想到这个结论呢？

考虑发配（？）号堡垒的英雄是什么时候出来的，发现号堡垒的英雄就是时刻出来的，所以耗时加上。

然后这个玩意的修改可以拍到距离域上通过线段树维护，线段树 info 是区间堡垒数和答案的 max，tag 维护对答案 max 的区间减，三种合并显然很简单，还要支持单点修改。

做完了。

但是场上写线段树 bug 有点多，没写出来（大悲），只交上了暴力。

26-4-10

晚练变早练说是。

第一道题，发现边双缩点后，边双内的点两两显然可以异色，再想想发现有且仅有割边连接的点需要同色，并查集维护一下同色性，然后如果并查集上至少有两种不同色连通块即有解，随便选一个连通块染成与其它点不同颜色即可。还需要特判不连通的情况，此时显然无解。

第二道题，简单 DP，设表示前层，已有个点的方案数，转移，另有，答案。

26-4-13

二分答案 + 树形 DP 实现贪心。

显然有关于答案的单调性，考虑如何实现 check。

设表示答案最小时以为根的子树最远需要覆盖点的距离。

设表示答案最小时以为根的子树最近被选择的点的距离。

转移如下：

。

若说明该点子树已被覆盖，。

若且说明该点未被覆盖且需要被覆盖，。

若说明该点子树需要被选择，否则不合法，并且此时也是最极限条件，一定最优，。

DFS 一遍贪心求出最优点燃次数，再判断是否不大于即可完成判定。

说实话这个贪心挺模糊的，但也不知道怎么严格证明。

26-4-14

绿绿得紫。

第一题 P11187，考虑 DP，表示到选择第位，这一位是最后一个配对中第个的情况下的最优答案。暴力，记录前缀中不同的最大值和次大值，也记录的最大值，优化转移至，整体时间复杂度。

第二题 P12000，二分答案加贪心，贪心策略就是在满足游玩需求的情况下，最多只买可以撑到下一个值更大（性价比更高）的位置上的游戏币，其实就是类似 P9749 [CSP-J 2023] 公路的贪心策略，注意需要单调栈处理一下下一个值更大的位置，整体时间复杂度。

26-4-20

P15301，汗国军队。

首先考虑插入，发现对于 LIS 的更新可以用对 01 差分数组的更新刻画，而且还很容易做，直接放进 DP 维度里，还有一个对于汗王护卫的要求，再加一维表示最后一个加入的汗王护卫的位置即可维护。

总状态数，是的，转移，时间复杂度。

26-4-21

绿绿蓝得紫。

第一题 P12675，分讨，共四种方案。

将变合法，答案。
将变合法，答案。
将变合法，，答案。
将变合法，但要求，答案。

第二题 P3419，贪心，贪心策略猎奇，就是若当前需要从地板中移除玩具车，则移除产生贡献最晚的那一个（下一个编号与之相同的车最远的）。

26-4-22

P15352，就是要支持到两个等长区间的一对一逐个合并，在朴素并查集的基础上 ST 表优化即可，查询是简单的。

26-4-23

发现每个出现了的数可能范围最大长度为，直接按左端点排序后，状压使用状态即可吃掉后效性，然后就可以 DP 了。

26-4-26

拆点处理边权，然后就可以用矩阵优化 DP，转移矩阵的幂二进制拆分，然后注意到并不需要用矩阵存储转移结果，只需要直接转移即可。

对于美食节，只需要分段转移，在美食节给当前的 DP 数组加一个值即可。

26-4-27

第一题 P10837，发现只需要关注某朵凋零玫瑰覆盖区间内被覆盖次数为，排序后取出前后共个，离散化后做前/后缀加即可计算移动一朵花的贡献。

第二题 P11969，超绝巴巴博弈，不想写了。

26-4-28

P14598。

考虑线段树处理，没有修改，所以关键在于 info 和合并。

info 包含。

分别表示以开始/结尾的子序列数量。

合并贴代码：

struct info
{
    int cl, pl, cr, pr;
    info operator+(const info &x)
    {
        info ret;
        ret.cl = cl + max(0, x.cl - pr);
        ret.pl = pl + max(0, x.pl - cr);
        ret.cr = max(0, cr - x.pl) + x.cr;
        ret.pr = max(0, pr - x.cl) + x.pr;
        return ret;
    }
};

挺显然的，不知道做的时候在想什么。

文件名还打错了，直接起飞。

26-4-29

P9402。

注意到很小，且公交车是有向无环的（甚至是链），所以可以做一个 DP 状物处理最短路（最短路显然最优，因为可以等车）。

naive 的就是直接枚举上车点转移到下车点，这个转移是的，然后取前缀优化一下转移就是。

时间复杂度瓶颈是 DP，时间复杂度。