8.2-8.9 学习记录
8.2
ABC 469 D: 及时去除无贡献的点。
ABC 469 F：kruskal 本质是先选择边权小的贪心。基于此，不必拘泥于给所有边排序，可以枚举值域。
ABC 469 E：本质二分找最大均值。形式化出来就好做了。写代码之前先想清楚啊。
P2829 & 2865：次短路学习+板子
P1967：MST 与瓶颈路的不解之缘
P3430：看题解。染色。找出主体的不同状态，用边将不同主体联系起来，边权表示状态的异同。
模拟赛：还是太慌张了。先想好啊。下次至少要拿一个rk5吧。
8.3
颓废了捏。
8.4
P6033（2WA+TLE）：与石子合并的区别在于，石子合并多了一个合并相邻堆的约束。本质选取两个最小堆，可以用两个队列分别维护 原 & 合并后 的堆，每次取队头。
P1197（RE）：并查集离线加边处理连通块数量。
P4513：涉及到动态维护区间信息，考虑线段树。先找到需要维护的信息（考虑合并时可能发现需要再添加）。在合并时，考虑节点与节点、节点与标签、标签与标签之间的合并。
P7706：考虑线段树节点合并时，先考虑答案落在左或右的情况，再考虑答案跨越左右的情况。对分类讨论要敏感。
CF438D（TLE）：对于难以维护的操作（区间每个数取模/开方），直接暴力再考虑优化/剪枝。这是因为操作至多进行 log 次。最终时间复杂度 n2logn.
8.5
模拟赛复盘。
- 打暴力之前可以想想更优秀的做法，不要将自己的思维限定在“优化暴力”上面，很多题目的正解和暴力不沾边的。
- 对于单调性要足够敏感，不要觉得这题二分不了就什么也不做。
- 选择方向时，如果发现这个方向上的东西太过复杂且时间复杂度难以保证，可以先试试别的方法。
P1972：能离线的要离线。排序往往带来优秀性质。
8.6
P4198：线段树求最长递增前缀。要维护的东西与区间有关，第一时间想到线段树。
P6327：线段树区间加。难点在于标签与节点的合并。若维护的信息没做过，有两种方法：
拆分成好维护的
直接研究操作影响
CF1918D：子段和问题，想到二分答案。
P12406（明天继续）：想贪心失败，正解是 DP。
复习：单调队列优化多重背包板子，分组背包板子（g 的初始值要设为 dp 哦），SPFA 板子（带返回值的函数记得返回返回值啊），abc465e.
感觉自己的思维有些太跳跃了，这样就很容易踩坑，下次可以慢下来。
在 u 群提了下问，遇到不会做的题就枚举知识点，假设这题就用这个知识点做。往往不能一命速通，失败是正常的，失败之后要反思为什么开始的方向是错的，或者说，根据提示，能不能更快的选择出正确的方向。
8.7
P12406：移动序列可以等价于移动头指针。
abc311f：网格图计数，想到按行/列 DP。
arc187b：明天继续。先推性质，然后暴力 DP，最后优化 DP（一开始猜的结论是假的调了两个小时呜）
复习：tarjan 求 SCC、割点割边、SOS DP
先摸出一点性质再深度思考啊。一点性质都没有硬想肯定难出啊。
8.8
arc187b：发现断点性质之后，形式化题目。贡献法做。
CF372C：区间转移考虑单调队列优化 DP。
另一种解法是找到函数顶点进行剪枝。
CF1234F：20 的字符集暗示状压DP。反转操作本质拼接合法字串。通过性质转换题目。子集 DP 处理 $a_i & a_j = 0$ 的约束。
ABC rk1700+。
旧题重做：ABC466E、P11230、P8817（bfs一旦被访问要立马标记）
8.9
模拟赛。
T1 思路秒出但是不熟计数DP调了一小时。转移时考虑转移前后集合的具体样子。
T2 没摸出性质做不出来。
补T2：求神秘数。构造不出考虑维护。加上一个原来大于自己的数会将数量至少翻倍。
优化了一下解题流程。
CF76A：瓶颈路考虑MST。
旧题重做：P1407（看到二分图完美匹配 ＆ 替换，想到交替环）
定好计划之后就不要想着昨天明天了，把握好今天就 OK 呢。实在状态不好那就去切切水题，看一下语文文言文的视频吧。
然后就是早点睡。
这周也是圆满结束了！！！训练量还是到位的吧（？