晚练计划总结

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 型连边均为“父节点-节点-子节点”的形式，的最大答案。