8.10-8.16 学习记录

8.10

ABC466E：值域取模，分裂成两类小值域。
P2812（懒的去码）：SCC 缩点模板题。重要的性质是 DAG 从所有入度为 0 的点出发 dfs，最后能到达图上所有点。
CF2046C：二分答案。check 里枚 x 当作扫描线，然后用值域 BIT 上倍增求出 y 验证即可。
CF2110E：图论建模。把关键字当作点，数对当作边，建出来一个二分图，满足交替相等的性质，在这上面跑欧拉路径即可。

知识学习：欧拉路径、BIT 上倍增 & 线段树上二分（CF1354D）
旧题重做：T784496 B. 旧址

8.11

P1070：处在同一条斜线上的转移可以用单调队列优化。
规范了一下 DP 的解题流程。
P8903（未码）：正反做 0/1 背包，枚举断点。
P5851（未码）：两种区间 dp 的综合。一是合并两个区间，二是取左右端点。
P2607（未码）：图论建模。版的基环树处理方式。树形dp。
P2585、P1441（懒得码）：水题。
CF721C（懒得码）：topo DP 的水题。但是有一个把 0/1 背包较大维当作值记录的小技巧，详见例题
P2831（未码）：我的做法是预处理出会使用到的函数，对应一个消除名单，状压dp，可以做到 2^n * n^2。可惜只有 85pts。
正解转移时只考虑最后一个 0 去除冗余。做到 2^n * n.
P6902（未码）：环上最小区间覆盖。简化问题成链，不难想到排序贪心。破环成链，变成区间覆盖。log 实现区间覆盖，要想到倍增。

8.12

模拟赛爆零。T1 组合数少一个特判 100–>0. T2 贪心假了一分木有。
CF222E: 题解区: 矩阵加速DP; 我: 倍增. 就很…你们懂吧 [捂脸哭]x3.
ABC470F（未码）：二元关系建模。块与块独立，计算多重集排列数累乘即可。
码掉：P8903、P5851、P2607、P2585、P2831

8.13

P6772（未码）：图上游走考虑矩阵加速dp。按 k 分段处理。拆点、预处理矩阵次幂。
P7914（未码）：区间 dp。直接转移很困难，通过维护其他量实现转移。
码掉：P6902
P13514（未码）：动态维护前 k 大。排序，离散化（注意要互异），离线，线段树上二分。
AT_arc100_c（未码）：SOS DP。核心转化是，若 $i | j == k$，则 $i, j \in k$ 是必要的。
补T2（未码）：基环树，首先考虑树/环的情况。猜结论，构造出环上最优解。树上路径求和，拆分贡献到边上，然后对环上结论做推广即可。

8.14

P4206（未码）：记忆化搜索实现期望 DP。定义势能为dis，每一条转移都是从势能大转移到势能小，因此无环。
P2515（未码）：将环缩成点，树上背包。
CF449D（未码）：SOS DP 板子。处理 a&b&c…&d = 0 的方案数，0 可扩展至 x。
完善了一些 SOS DP 的笔记。

8.15

学习回退背包。
CF981E（未码）：可以用回退背包瞎搞。正解是排序后贪心优化可行性背包的转移。
P13520（未码）：偏序关系考虑能否使用 dilworth 定理。转化为找最大反链。再将数对不同元素间的比较放到数轴上，转化为找区间最大交次数。
学习Dilworth 定理。
码掉：ABC470F、P6772
ABC模拟赛。

8.16

CF1701E（未码）：代价不对称，发现最优解结构。正反DP，枚举分界点。
P1707（未码）：矩阵加速dp板子。
P4159（未码）：矩阵加速dp板子。图上游走，拆点，本质P6772弱化版。
AT_arc189_c（未码）：惊世好题。首先考虑只有一个约束，对排列建图，会形成多个环。断环成链，在序列的视角下看链，发现最优解一定是任意解的子序列。问题转化为求两个序列的最短公共超序列（SCS）。这个问题等价于求 LCS。序列求 LCS 又可以优化成求 LIS。
排列–>环–>链–>序列–>scs–>lcs–>lis.
初赛模拟。
码掉：P7914