3月日记

26-3-1

开学第一天

不说做题，只是这个竞赛生活动还是有点抽象了。

@Antimony_ 退役了，祝好。

@Takato_ 退役了，祝好。

26-3-2

P10947，P10948 前者是最短路计数，后者是图论建模，但是有比我的更优的做法（利用一个层只会到一次的特点用优先队列优化 bfs （dijkstra） 跑最短路）。

26-3-3

P3225，基环树板子题，分讨然后跑个 LCA 再分讨。

P10951，二分 + spfa 找正环，但是数据卡了朴素 spfa 是令人忍俊不禁的。

P4819，前半部分 tarjan 缩 SCC 还算容易，但是有关概率的部分很迷惑，正解结论感觉很合理，但又不知道自己的思路错在哪里概率白学了。

26-3-4

P10950，欧拉路径应用计算机译码板子。

P3304，随机化乱搞过的。

P3225，显然可以想到点双，但是对于点双中的的情况分析稍有难度。

如下：

1. 点双内无割点，则此时需要在该点双内放两个出口
2. 点双内有一个割点，则此时需要在该点双内的非割点中放一个出口
3. 点双内有不小于两个割点，则此时不需要在该点双内放出口
4. 如果是点双内只有一个点，且该点不是割点，则也需要放一个出口

但是不知道为什么 UVA 和 SPOJ 上过不了。

26-3-5

P10953，边双缩点，然后 LCA 求树上两点距离。

P4281，抬手分讨。

1. 若一点在另外两点的路径上，直接选这个点，这是最优解之一。
2. 若有一点，以另两点的 LCA 为根，该点不与另外两点在同一个子树内，则选这个 LCA 是最优解之一。

大概可以证明 ,,,,, 六点中至少有一个点满足上述之一条件……吧？

UVA1464，圆方树板子。

还因此被迫学习了重链剖分 :（ 写小常数 LCA。

26-3-6

P10949，对于一个子图，若该子图中的点的权值和为 0，则该子图可以单独成一棵树。

对于每一个子图跑最小生成树，记子图 的最小生成树边权和为 ，若该子图中的点的权值和不为 0 或无法生成树，则将 设为 。

然后跑 DP，设 表示子图 的最优答案，直接枚举子集转移即可。

26-3-9

P15649，联合省选 2026 D1T1，先拆贡献成 ，设计 DP 状态 表示以 为根的子树内，以 为链顶的重链长度为 的概率，卷积计算概率来转移，转移时刚好算贡献（因为贡献要在父亲算），然后卷积需要反卷回退以计算每个儿子被选的概率，仔细思考发现每个儿子只需要求一次逆元就可以逐步回退，直接做就做完了，不过实现细节会大幅影响常数，需要实现得精细一些。

树上卷积是经典看似 实则精细实现 ，回退假装是跟卷积相同的，所以最后时间复杂度应该是 ……？

其他三道绿题，不提了。

26-3-10

P10589，略。

P1502，略。

P10463，运用更相减损法将区间加减变成单点加减，然后就能做了，但是线段树节点合并因为需要求 gcd 所以是 的，所以最后时间复杂度是 。

P3345，这我得坐起来写，题解点这里。

26-3-11

P10590，分块优化 暴力，通过分块加指针高效判断偏序关系。

P1494，莫队板题。

P4178，点分治板题，点分治学习笔记点这里。

26-3-12

P4735，可持久化数据结构的一大用处就是通过记录历史版本的信息，帮助我们过滤错解（本题中用于使答案符合有关 的限制），通过维护另外一些信息还能扩展，如支持更多限制等（本题中是有关 的限制）。

P1525，略。

P10686，判定方式比较有趣，是假设一个人是裁判，此时有关这个人的所有条件是无用的，除去这些无用条件后再扫一遍判断，若合法就证明这个人可以是裁判，第二问的答案是判定其他不是裁判的人时找到矛盾的最大轮数，因为至少要经过这些轮次后才能知道其他人不是裁判。

P10687，yes 表示同一部落，no 反之，这是好想的，但是后面然后要跑一遍背包，因为对于每一个连通块，其具体情况是未知的，所以要跑背包以考虑所有情况，如果有且仅有一种方案符合条件，那这就是解。

DP 状态 表示前 个连通块， 个人神圣的方案数。

输出具体方案，就是记录状态如何转移，但这里有个 Trick。

在把 DP 第一维去掉之后，发现有方案的 在 DP 过程中会越来越大，而且因为当且仅当 时有解，所以中间 DP 转移显然是一条线似的玩意，所以完全可以只压成一维，因为若后面覆盖了原来记录的这个位置的值转移方案，则转移出来的值显然大于二，也就不可能在正确解倒推时遇到（或者说： 若要成为正确解倒推时遇到的路径，则其被赋过值且仅被赋值过一次）。

反正就是直接压成一维不用滚动而且连记录方案的数组也是如此就对了。

26-3-13

P2894，区间最大子段和加区间赋值加线段树二分。

P10688，略。

P4135，类似于蒲公英的思路，实现稍繁琐。

26-3-14

模拟赛 - 凌云计划 7。

预估得分 300 pts，实际得分 300 pts，没有挂分。

总结 To do。

26-3-16

P4169，cdq 分治，比较板。

P4149，点分治，比较板。

26-3-17

补了 CF2204D,E,F。

完成了 P10689，平衡树屎题，差评。

26-3-18

P4390，cdq 分治，比较板。

今天效率较低，下午学整体二分学了比较多的时间，学完后写的题目也没调出来。

26-3-19

P3527，整体二分，特别之处是转区间为差分再转为单点修改操作，本题注意空间限制。

P10690，正解分块套可持久化 01 Trie，预处理 表示第 块左界到第 块右界的答案，对于查询，如果答案区间端点在整块里则答案已经在 中，如果端点在散块里，则枚举左端点暴力查询再枚举右端点暴力查询（不是枚举左右端点），预处理和暴力查询都需要可持久化 01 Trie 来优化复杂度，最后是个 。
但是有歪解，注意到设 表示 内的最优答案，转移是 。时空复杂度都是 带 常数，空间上稍微卡一下不存无用状态完全可过，优化内存分布减少 cache miss 后还跑得飞快比正解还快。

P2824，二分答案加权值线段树。

注意到 这玩意是有单调性的。

所以原排列分为小于 的（当作 ）和大于等于 的（当作 ）。

然后发现排序就是将序列区间修改，一半 一半 这样，升降序只是影响是前一半还是后一半，这个可以用线段树维护。

然后在 25-8-18 的模拟赛（还是 hyc 模拟赛）的 T3 sort 中，后半部分这个 Trick 就基本出现了。

甚至 sort 题面也有一模一样的排序操作。

我甚至在模拟赛中场切了 sort。

我好菜，水平严格低于以前 /ll。

26-3-20

P3402 【模板】可持久化并查集，就是用可持久化线段树维护并查集，由于不能路径压缩（Hack：构造两个大小之和 的并查集，然后合并，为了压缩路径会修改产生 个新版本，然后回退一步操作，再合并又会产生 个新版本……），所以只能按秩合并或者启发式合并。

然后基本就是一个任意操作复杂度带只 的普通并查集。

然后开始蓝书数学专题，今天通过 6 道。

cdo 进度尚未追上，同志仍需努力！