晚练计划总结

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，时间复杂度。

26-5-5

注意到显然一步可以到一个包含的区间，跳两步就是，更多步同理。

发现这个过程可以倍增加速。

一条线路事实上就是区间对取或对取，可以用线段树维护算出来。

然后倍增就是形如这样的东西，这个也可以用数据结构维护。

然后就做完了。

26-5-6

不好题。

首先是发现操作的一定是连通块。

然后先操作的可以通过后操作的连接。

只要所有颜色最后都能连通即可。

然后两个并查集，一个维护连通性，一个维护已操作点连通性及已操作点连通块邻域。

思维是没有的，代码是复杂的，不开 vector 替换静态数组是会 TLE 的（猎奇）。

26-5-7

首先推性质，就是在两两配对过程中的任意时刻，至少有一个点度数为。

不会证。

知道这个性质后就可以用拓扑排序，每取一次匹配就把相邻边全删了，然后继续取出当前所有一度点。

然后重构图，类似缩点，但是是为了保证走到一对匹配上时一定会从另一端出来。

重构过程就是有当且仅当存在，是的匹配点。

然后再跑一遍拓扑排序求最长路即可。

26-5-11

唐。

26-5-12

重点是从按学校顺序考虑转到按值域区间考虑，之后的转移和式子就挺好想的。

26-5-13

首先写出 DP，发现其转移条件是一个二维偏序条件，因此将所有询问及雨滴的偏序值离散化后跑一遍树状数组优化 DP 即可。算法是离线的。

26-5-14

数数题，正难则反，注意到元素为正整数，所以不出现要求的结构的条件就是当前序列后缀和中不同时存在。因为，所以可以状压。

26-5-17

~~这种地雷炸弹苦力怕的数数题是不是都是设个 DP 钦定 xxx 不爆炸时的方案数啊。~~

设表示考虑到，且不爆的方案数。

设为左侧第一个会引爆的地雷编号，有。

另有设为右侧第一个会被引爆的地雷编号，有会对做贡献。

用树状数组处理区间求和，在每个贡献区间右端点挂上，适时取消贡献即可。

26-5-18

题目就是给出一棵树，再给若干带权非树边，求在没有偶环的基础上能保留的非树边的权值和的最大值。

发现直接形成偶环的非树边是肯定不能要的，而两个奇环若有相交边则会形成偶环，因此，我们需要在此条件下保留更多权值。

我们考虑用树形 DP，用以存储子树答案。

发现一条边若要被使用，为了防止奇环重合，取边的贡献时就只能形如这样给做贡献。

打绿勾的部分是可以贡献给子树的位置实例。

因为若使用或路径上的 DP 值，会导致可能的奇环重合，而只取子树，以及这两条路径上的节点的兄弟子树，就绝对不会出现重合，这也包含了所有可能的贡献。

为了方便转移，加一维状压表示当前节点还未使用哪些子树。

这是第一步转移，不考虑非树边的贡献，只考虑子树。

此时。

定义表示选取时，包含的子树和包含的子树所产生的贡献。

分别定义为，

转移就是这样，跑一遍树形 DP 即可。

26-5-19

从小到大加点，这样不用多记一维或者限制转移以确认转移系数。

两点距离不大于时连通，加点时用并查集维护连通块，连通块对应一个区间，显然区间内任意一个点均可以用于转移，线段树维护区间即可转移，需要支持单点修改。

26-5-20

Cancelled，题面是求若干基环树的直径。

26-5-21

假交互，从后往前考虑，发现对于一个点 i，若 protocol[i] 为 0/1/2 分别表示：i 和 host[i] 之间：选权值更大的一个/要么同时选要么同时不选/至多选一个。

分别表现为：

confidence[host[i]] += confidence[i];
ans += confidence[i], confidence[host[i]] = max(confidence[host[i]] - confidence[i], 0);
confidence[host[i]] = max(confidence[host[i]], confidence[i]);

最后 ans += confidence[0];。

26-5-24

结论是如果如果有子串，取其第一次出现的位置，答案是，否则，如果有，答案是；否则答案是。

考虑线段树。

info 维护区间子串第一次出现的位置，是否出现过，前后缀的个字符。

tag 是区间取反，这个也是可以与 tag 和 info 合并的，不过 info 中就要记录若干辅助信息，例如其他类型子串的出现等等。

反正非常麻烦。

但这就是正解。

26-5-26

一个简单题，题面中的问题看似很不可做，实则就是转化成给你上有若干点的数轴，你要在点与点之间选点，两点之间最多选一个，选的点不能相交，问你最多选多少点，以及选点最多情况下的方案数。

注意到题目答案要求一个 array<int, 2>，其实这个 array<int, 2> 的合并是满足交换律和结合律的。

具体合并过程如下：

array<int, 2> operator+(array<int, 2> x, array<int, 2> y)
{
    if (y[0] > x[0])
        x = y;
    else if (y[0] == x[0])
        x[1] += y[1];
    return x;
}

然后上述 DP 过程显然一个前缀和优化 DP 秒了。

26-5-27

先考虑贪心，将元素按排序，固定发现个元素被若干个 gap 分成了几个区间，长度为偶数的区间可以一一配对，长度为奇数的区间则要多出一个无法匹配。

对于一个长度为奇数的区间，元素能不匹配的条件是或者。

然后发现随着的增大，会合并区间，可能上面第二个条件之一也更有可能满足。

所以将询问按排序后处理，维护一下上述两个变化即可，使用并查集维护合并。

具体的，用表示以为代表的区间中，在偶/奇数位，满足第一/二类条件的元素的最小值。

一个区间，假设其代表为的答案（用代码表示）就是 min(mn[f][l&1][0],mn[f][(l&1)^1][1])。

26-6-1

真交互，恐怖。

Sub 1 简单。

重点看 Sub 2。

注意到，我们可以将整个序列分成若干组，每组内部进行两两询问，这样可以从每组内选出一个。

举例，分成组，就是分成两半，选出一半，分成组，就是两两询问，然后直接选出答案。

发现分组越多，查询次数越少，但是排除非最大值的速度更慢，请求数多。

反之分组越少，查询次数越多，但是排除非最大值的速度更快，请求数少。

注意到询问次数之和，可以在前面分多组排除，后面规模小了，就利用多出来的询问次数，分更少组，减少请求数。

我们考虑先手动寻找最优解。

考虑使用记忆化搜索。

设表示剩余次操作次数，个待确认元素的最小查询次数和。

枚举分组数量，有。

表示个元素分成组的最小查询次数。

对于显然是均匀分配到每一组再查询最优。

LL calc(int y, int d)
{
    LL blk = y / d;
    int re = y % d;
    return re * ((blk + 1) * blk / 2) + (d - re) * (blk * (blk - 1) / 2);
}

但此时转移太慢了，但是并没有好的转移优化方法。

所以只能随机减少枚举范围。

改成了某一个，注意偏移量，不然最后跑出来询问次数不是最优的。

嗯，所以这样就能就能跑出来了，兑。

我们只需要最终结果，所以结果如下……

1	{500000, 250000, 125000, 62498, 20832, 3472, 183, 1}

……刚好询问次。（大雾）

26-6-2

做过的题。

二分答案加树形 DP。

注意到国王往回走显然是更宽松的，所以我们不考虑这种情况。

设表示，国王在节点，保证国王在子树中不走到没有凯旋门的点需要多少次修建。

有，是二分出来的参数。

显然，因为我们不知道哪个子树会被国王走，显然要填上儿子，所以需要把所有不合法可能消灭，自己能自力更生做到合法（）的子树我们不能加上，因为我们不能往里面放负数个操作次数，或者说在其中多出来的操作次数并不能时间回溯用到现在~~（支援过去）~~。

不管因为都已经走到了所以不用管，这也刚好契合初始节点有凯旋门。

26-6-3

Trick：区间异或差分成两个单点操作，而且某些原序列要达成的条件也可以转化成差分数组上的情形，这样更加易于建模、转化。

将点亮当做，熄灭当做，所以一个熄灭点在差分数组上的效果就是 c[a[i]] ^= 1, c[a[i] + 1] ^= 1，目标就是将差分数组所有位置置为。

区间取反就是差分数组上两点取反。

转化成图论问题。

图上点有点权，即差分数组的值，而区间取反就是一条边连接。目标是使所有点权为的点度数为奇数，点权为的点度数为偶数。

发现最终连边中，不可能有环，因为环对环上每一个点都贡献了偶数度数，所以不影响奇偶性。

然后发现，由于边对度数的总贡献显然是偶数，所以点权为的点应当配对处理。

因此最终结构就是在配对的点中连简单路径（没有环）。

然后求出所有点的单源最短路（BFS 即可），再状压 DP 就做完了。

26-6-4

恐怖树形 DP。

首先，由于点灯路径有两个端点，所以对于一颗子树，就有三种可能：

两个端点均不在子树内；
有一个端点在子树内；
两个端点在子树内。

对于这三种状态，我们考虑直接设对应的 DP，我也不知道为什么要考虑这个但就这么考虑吧。

分别设表示 1、2、3 情况下，子树内除了全部点亮，自身不点亮（0）/点亮（1）的方案数。

唉算了还是直接看洛谷上的题解吧。

题解链接。

26-6-5

To do.

26-6-7

To do.

26-6-8

To do.

26-6-9

To do.

26-6-10

乱搞过的，直接枚举，二分查找区间和离平均值（）最接近的、，再加个偏移量即可。

骗你的，作弊了。

26-6-11

升序排序并去重后，发现的部分只能用重量为的塞满。

所以我们直接贪心地塞满，剩下没用的就直接拼成若干个重量为的物品（最后最小的那一坨质量凑不齐的就用权值为的填上，这不影响答案），然后将之后的和全部除以，继续递归处理。

这样做的复杂度是什么呢，一个物品被拼装，最多拼次（因为每次至少使翻倍，因此是对数级别），在排序中产生最大复杂度。对于每一种质量的物品排序，是。

所以复杂度是的。

26-6-13

其实并非晚练，但还是记下来。

To do.

26-6-15

早上由于断网所以练了一道“晚练”题。

To do.

晚上一道蓝题，DP，通过直觉和对期望线性性的一点点感知做出来了。（滑稽）

设表示从点开始，走次的期望答案。

设表示从点开始，走次，期间经过点的概率。

转移方程如下：

大力转移即可，时间复杂度。

26-6-20

转化重点是将不可做的随机选点变成对于随机排列按顺序删点。

可以这么转化是因为对于任意时刻，所在连通块大小不大于的点可以直接忽略，这样当前局面下，所以所有排列中，所有可删点作为下一个被删的点的概率是相同的，这与题面相符。

然后发现，一个大小大于的连通块，只会产生一次贡献，产生贡献后就变成若干小块了，所以只需要算一下它产生贡献的概率即可。

一个连通块产生贡献的条件是它被“剥”出来，即树中所有相邻点均被删除，且子图中所有点还没被删除。设子图内有个点都还没被操作，且与之相连有个点。回到排列上，上述条件等价于：某个点在排列上的位置均在某个点前面，概率。

然后用树形 DP 统计一下满足某种条件的子图数量。

DP 是朴素的，表示深度最浅的点是，大小为，不算的父亲有个相邻点的子图数量，直接转移即可。

26-6-21

首先，要从一段 01 序列中选出若干不相邻 1，只要求最大化选出数量，这玩意的信息是可以合并的，记录一下左右边界是否有被选的 1 时的答案即可。

然后就有很多办法了，无论是二分答案在枚举最小值，还是双指针直接求都行。

26-6-22

AwA。

首先发现，要开始加边之前，我们先要将所有度数大于的点去掉，目标是在尽量少炸掉点的同时留下尽可能多的边（这样可以减少加边数量），所以直接树形 DP 统计即可，由于少炸一个点和多留下一条边是等价的，所以我们只关心操作次数和剩余边数之差，目标是最小化操作次数减剩余边数，这样就好 DP 了。

状态设计表示点不操作，有/无父边，子树内的最小答案，表示炸掉点，子树内的最小答案。

转移如下：

对每个儿子，定义

并将所有从小到大排序，取前两个最小值为

若儿子不足两个，则对应的视为，且。

则转移为：