做题总结

xiehy · 2025-11-24 18:30:37 · 个人记录

1.P3554 [POI 2013] LUK-Triumphal arch

• 二分答案，然后跑dp，f[i]表示i子树需要上级的多少次支援

2.AT_agc013_d [AGC013D] Piling Up

3.CF755F PolandBall and Gifts

• 考虑建图，然后最大值就直接贪心，最小值跑背包，大小一样的环显然可以一起考虑，最多有根号种大小，直接跑多重背包，如果是判定性问题一般用二进制优化+bitset，否则可以考虑单调队列优化

4.AT_abc221_g [ABC221G] Jumping sequence

• 一开始发现横纵坐标可以拆开算，同时思考了一下距离的变换，但是题中是要到达定点，跟距离一点关系都没有，但是启发我们进行坐标变换（操作坐标轴），使在新的坐标系中的操作好维护

• 通过一系列变换可以让x和y的操作独立，变成判定性背包，直接记录方案即可

5.Coins

• 一个蠢题，二进制或者单调队列优化即可

6.P9140 [THUPC 2023 初赛] 背包

• 变成同余最短路（通过取模操作减少状态数），将单位价值最高的物品作为基准首先可以保证结果最优，同时可以保证没有正环，那么可以直接跑最长路，同时每转一圈就减去基准物品的权值这样可以保证无正环，可以保证模数相同方案最优性的正确比较，也可以正确的计算贡献

• 如果不是恰好，可以把每个点都算一遍

7.P2619 [国家集训队] Tree I

• 对白边进行加权处理，调整一个合适的边界使白边数量大于等于需要的数量，同时用当前最小生成树的代价减去midneed。如果在合适的位置取到need，这么做肯定没有问题，但如果mid时>need，mid+1时<need的情况呢？题目说保证有解，那么必定在mid的时候存在若干条黑边可以替换掉一条白边，同时最小生成树的代价不变，所以这个时候依然用代价减去mid need

8.CF739E Gosha is hunting

• 考虑网络流建模，如果是同时用球，发现多算了一点，考虑建两条边，一条容量为1，费用为0，一条容量为1，费用为-a*b，然后跑最大费用最大流。仔细思考发现是正确的。

9.P1758 [NOI2009] 管道取珠

• 答案的实际意义就是两个人选序列，所选序列完全相同的总方案数，然后直接dp

• 如果改一下题目666那么前两项可以直接算，后面一项即本质不同的序列数，考虑dp，如果两数不同显然不重，假设前面求得都是对的，那么将上方拼入和下方拼入的重复序列就是i-1，j-1，所以减掉即可

10.P13680 [IAMOI R2] 未送出的花

• 显然每一条链从上到下递减，每个点影响的点的数量固定，因此等价于选择1的联通块使影响的范围之和大于need，答案即最小的value。考虑dp，然后跑就行

• 求影响范围的时候可以倍增nlogn，也可以在dfs的时候记录depth的点，然后搜到的时候直接++，仔细想想就是对的

11.P12406 「CZOI-R3」消除序列

• 线段树优化dp

12.P12353 「HCOI-R2」DataErr0r

• 先不考虑操作1，显然直接异或起来，然后奇偶位分别考虑极长连续1段。

• 然后考虑删除操作，删后可以将两对操作合并。删除前亦然，同时还有一种特殊情况不在此赘述

13.P13687 【MX-X16-T5】「DLESS-3」XOR and Rockets

• 如果最后一个数不操作，值域比较小，如果操作，可以分段考虑异或上一个数是否单增，段与段之间以后上一个极大的数即可保证段与段单增，异或可以合并，直接dp即可

• 相邻两数可在最高分歧点进行操作，看是否矛盾即可

• 比较惊艳的点：分类讨论（保证正确性，如果操作就会钦定每一段都异或上一个数，但实际上最后若干数可以不异或），异或操作可以合并在一起（贪心），将操作数减少，在最高位分歧点进行操作（分歧点之前不管怎么搞都没影响，同时在分歧点必须进行钦定，否则可能无法保证递增）

14.P13494 【MX-X14-T4】分门别类

• 二分答案，dp定义为考虑前i种数，目前有j个奇集合

15.P13501 「Cfz Round 6」Imaichi

• 考虑dp，同一行刷分点必定相邻，那么直接dp转移，关于刷分点可以将其置为最大值k，负数特殊考虑即可。同时想要到达刷分点要从上方到达，还有可能从附近的刷分点转移过来。有可能从i向右转移到j刷分，然后再转移到i左侧的点k，因此跑两边dp（从左向右和从右向左各两次）

• 比较精妙的点：将刷分点的权值置为极大值k，同时跑两次dp，将变向的情况考虑进去

16.P12407 「CZOI-R3」数字变换

• 暴力dp复杂度有问题，考虑分组优化，将二进制对半分，高低位贡献可以分开算，高位相同的点分成同一组，分组优化，再枚举低位，直接暴力预处理，单次预处理O(n\sqrt n),单次查询O(\sqrt n)，

17.AT_abc353_g [ABC353G] Merchant Takahashi

• 线段树优化

18.P12017 [NOISG 2025 Finals] 可达性

• 问题变成了背包，分类讨论即可，同时有些点可能受到上面点的影响，因此可以在上面点决策时判定，保证合法，最后看看1号点即可

• 在最后一种转移中，实际上是将合法的判定转嫁给上方的点，当上方的点合法，下方的一定合法

19.P11799 【MX-X9-T3】『GROI-R3』Powerless

• 考虑相同的数，可以数位dp

• 不同的数考虑最高位的分歧点，也就是说前面要相同，因此插到trie树上面，即访问sz，同时钦定k的这一位，其他位可以分开算贡献，dp定义第i位为0/1，第j位为0/1。

20.关于基环树

• 分为无向和有向图，两种常见技巧：将基环树视为很多个树的树根通过环连在一起，那么在每棵树内dp，在环上跑dp。

• 找环：拓扑或dfs

• 环上dp：倍长环（断环为链）或钦定1和n的选择情况（注意初始化的不同）

• 第二种常见的技巧：考虑钦定基环树的树根，即删掉一条边（断环为链），然后钦定树根

21.P11842 [USACO25FEB] Bessie's Function G

• 按照上面的思路即可

• dfs找环：裸环找不了直接特判

• 拓扑：裸环特判

• 算贡献：一元环可能要特判

22.AT_abc341_f [ABC341F] Breakdown

• 显然只能从w大的往w小的转移，因此是DAG，无后效性，直接跑背包即可

23.CF1107E Vasya and Binary String

• 区间dp，平常的定义dp[l][r]会发现有可能右边有一些相同的元素一起消掉会更优，因此加一维k表示右边有k个相同的元素，可以写记忆化搜索，第一种直接把右边一连串消掉，第二种在里面找元素将之间的消掉，并且将该元素和右边的合并。

24.Rectangle Painting 1

• 直接横竖划分即可

25.P5336 [THUSC 2016] 成绩单

• dp记录min和max,考虑r带来的增量，要么不删，成为最小值或最大值，要么删掉直接划分区间

26.CF908G New Year and Original Order

• 开两个dp，一个f表示填到i位的贡献，g表示在此基础上一个1带来的贡献，发现转移和具体填了多少个当前的数无关，因此可以将所有转移合并，只记录位置即可

27.P3387 【模板】缩点

• low值定义通过非树边所能到达还在栈中的dfn最小值

• tarjan为拓扑逆序

• 如果不是栈中会有问题，不是dfn也会有问题

28.P3388 【模板】割点（割顶）

• low值转移不用看是否在栈中

• 判定是low[v]>=low[u]，这样可以保证不算上叶子结点，也可以保证正确性，如果是u和u比较就会出错

29.P8435 【模板】点双连通分量

• 两点双之间交点必定为割点，每个点双中dfn最小的点是割点或根节点，当根child>=2时，为割点，为1时也是点双的结算点，为0时特别地为点双，需要特判，如果放在具体题目中需要结合题目钦定是否为点双

• 退栈的时候到v停止，因为u和v不一定紧挨着，中间可能隔了一些待确定的点

30.P8436 【模板】边双连通分量

• 无重边可以记录father，有重边记录边的编号

• dfs里面注意死循环

31.P3835 【模板】可持久化平衡树

• 跟主席树一个思想，在分裂和合并的时候为了不影响到之前版本树的形态直接新建节点复制过来就行

32.P5055 【模板】可持久化文艺平衡树

• 在pushdown的时候为了不影响之前版本的平衡树直接将两个儿子节点新建，新儿子的数量可以保证不会很多

33.P1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

• 构造方案求出的数是唯一的，模数要两两互质，如果模数不是质数要求逆元，要么exgcd（在最后的时候注意负数的情况），或者求欧拉函数算逆元

34.高斯消元

• 用于解线性方程组

• 如果是取模的，除法就变成逆元

• 特别的取模2，可以视为异或，用bitset优化

35.矩阵

• 求恰好或至多k条边的路径数量，或最短路大小，和floyd很像

• 加速线性递推