题记 2

_Vix_ · 2023-10-17 10:25:18 · 个人记录

P5666 [CSP-S2019] 树的重心

总结： 从根沿着重儿子找一定能找到重心，如果有两个重心，一定是连续两个。跳重儿子可以倍增优化，加上换根就可以了。注意同时记录重儿子和次重儿子，方便换根时更新重儿子。

题意：n 个物品，第 i 个物品的体积为 x_i \times v_i，价值为 v_i，m 次操作，要么删掉一个物品，要么询问用 x 体积的最大价值。n, x_i,v_i,x_i\times v_i \le k=2\times 10^6，m \le 5000。

总结： 相同 v_i 的一定是按照 x_i 从小到大选，最大总体积不超过 k，可以证明有用的物品只有 \sqrt{k\log k} 个。考虑根号分治的思想，对于 x_i \leq B 的直接暴力背包，剩下的 DP 值比下标小，考虑价值体积交换的背包（价值一定体积最小），将两种背包结合起来。m 次操作倒序考虑，删除变为添加。

P5369 [PKUSC2018] 最大前缀和

总结： 考虑答案的样子，前面部分前缀和为非负数，后面部分任意前缀和都为负数，两部分分开状压 DP。前面部分转移考虑加入一个数的新集合，后面部分转移考虑删去一个数的子集合，最后答案为 \sum v_ S\times f_S \times g_{U-S}

Dreamoon and Sets / [AGC027D] Modulo Matrix

总结： 构造题小结。连续三个奇数一定互质，（四个不一定，比如：3,5,7,9）。见到矩阵可以黑白染色再观察性质。

P5021 [NOIP2018 提高组] 赛道修建

总结： 树上拼凑链的模板，贪心加上 multiset 保证正确性和时间复杂度。

Phoenix and Computers / P7967 [COCI2021-2022#2] Magneti / P9197 [JOI Open 2016] 摩天大楼 / Ant Man

总结： 连续段 DP（也叫插入 DP，高级的新东西），记 f_{i,j} 表示用考虑前 i 个拼成了 j 段的方案数。

新建：f_{i,j} \times (j+1) \rightarrow f_{i+1,j+1}
合并：f_{i,j} \times (j-1) \rightarrow f_{i+1,j-1}
扩展：f_{i,j} \times2j \rightarrow f_{i+1,j}

根据题意，状态的定义以及转移会有不同。如果涉及到值的大小，一般排序来规避掉过多的讨论。有时候需要去除不合法的转移，例如合并的时候不足两段，规定了开头与结尾的也应特殊考虑。

The Three Little Pigs

总结： 求 \sum \binom{ki}{x} 可以维护 f_{i,j}=\sum \binom{ki+j}{x} 方便递推。同时结合帕斯卡定理和上指标求和。

帕斯卡定理：\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}

上指标求和：\sum_{i=1}^{n}\binom{i}{m}=\binom{n+1}{m+1}

Gregor and the Odd Cows (Easy)

总结： Pick 定理：给定顶点均为整点的简单多边形，其面积 s 和内部格点数目 a、边上格点数目 b 的关系：

s=a+\dfrac{b}{2}-1

Nauuo and Pictures (hard version)

总结： 非常好的期望 DP 题，先推普通 DP 并转移。再着手优化状态等等。

Sasha and Interesting Fact from Graph Theory

总结： \text{Cayley} 定理：节点个数为 n 的有标号无根树的个数为 n^{n-2}。

扩展 \text{Cayley} 定理：n 个标号节点形成一个有 k 棵树的森林且给定的 k 个点没有两个点属于同一棵树的方案数为 k\times n^{n-k-1}。

Present

总结： 我们只关心对答案有贡献的部分，以及怎样才对答案有贡献。转化题意后会有意想不到的效果。

Sasha and a Very Easy Test

总结： 由简入难。发现如果模数互质好做，这提示我们将模数质因数分解，将其他数也拆成互质与不互质的两部分，发现这样是好做的。

Graph and Queries / P3273 [SCOI2011] 棘手的操作

总结： 考虑 kruskal 重构树，对于每一条边赋一个时间戳，连通块一定是重构树上的一棵子树，成功转化为树上问题，套一棵线段树就好了。建树的代码有一点小细节，要弄清楚权之分别是什么。

XOR Triangle

总结： 异或与数学三角形相结合的美学，如果 x，y 在任意一位上没有相同的 1，那么就有 x \text{ xor } y = x+y，反之有 x \text{ xor } y < x + y，进而转化成 x \text{ and } y 是否等于 0。然后就可以套数位 DP 啦。

Boboniu and Jianghu

总结： 假如没有两点 b 相等，那么每条边方向是可以确定的，可以快速得到答案。对于相等的边，都先假定向着一个方向，然后调整答案（将一些边的方向调整为反向）。由于要求最小值，因此调整的时候也要按照子节点答案从小到大调整，排序的时间复杂度是正确的。

Legacy / P6348 [PA2011] Journeys / P5025 [SNOI2017] 炸弹

总结： 线段树优化建图。用于优化区间连边，本质上是一棵出树和一棵入树之间连边，需要根据题意建边，有时需要用上一些图论算法。

Team-Building

总结： 可撤销并查集（要按秩合并）的板子，只不过如果直接枚举颜色会是 k^2 的，但是根据边来做最多是 m 的。算是优化暴力的一种思想。

Divide and Sum

总结： 将题目用数学的式子更形式化地表现出来，有时候会方便后续推式子，同样结合实际意义变化式子有时也有奇效。

Vasya and Binary String

总结： 可以归为区间消除 DP，参考此文。

Gregor and the Two Painters

总结： 代表元思想，转化十分巧妙。然后就是二维数点（二维偏序）了。

P4516 [JSOI2018] 潜入行动

总结： 书上背包的时间复杂度是 O(nm) 的。这种 DP 的一般思路是将一棵子树合并到当前树中。

[ABC256G] Black and White Stones

总结： 如果知道边的共用点的颜色，那么将会方便统计答案，因此很容易想到计数 DP，再加上矩阵乘法优化即可。

P2391 白雪皑皑

总结： 区间颜色覆盖可以倒序做，同时并查集可以加速该过程。