集训笔记 Day 1

Cute_Wazzy · 2026-02-06 12:11:56 · 算法·理论

DAY 1

混乱邪恶的 dp 。

考虑用最少的状态去描述一个状态。

定义 dp_{i,j} 表示考虑到第 i 个棍木，这个木棍的开头离左边界距离为 j ，这样就可以得到所有关心的东西。

这题好像也可以二分+贪心。

计数 (x_1,x_2\dots,x_n)\in \mathbb{N}_+ ，使得 \sum\limits_{i=1}^mx_i=k,1\leq x_1\leq x_2\leq \dots \leq x_n 。

要求 O(n^2) 。

一个经典的 trick ， dp_{i,j} 表示考虑到第 i 个数，和为 j 的方案数。

分类讨论，可以选择选 1 或者是不选 1 ：

选 1 ，不妨令 x_1=1 ，则有 \sum\limits_{i=2}^nx_i=j-1 ， 1\leq x_2\leq x_3\leq \dots \leq x_n 。不难看出方案数等价于 dp_{i-1,j-1} 。
不选 1 ，不妨令 x'_i=x_i-1 ，因为没有 1 ，所以 1\leq x'_1\leq x'_2\leq \dots \leq x'_n ， x'_1+x'_2+\dots+x'_n=j-n 。不难看出方案数等价于 dp_{i,j-n} 。

综上 dp_{i,j}=dp_{i-1,j-1}+dp_{i,j-n} 。

这个 trick 还是非常有必要的东西。

比较有代表性的一类题目。

因为没有顺序，因此考虑安排一个顺序使得最优的安排是这个顺序的子序列。

不难注意到一个性质，若 s_i+w_i\leq s_j+w_j ，则 i 在 j 下一定比 j 在 i 上更优。

这个性质的证明可以使用邻相交换法证明。

有这个性质后，排序后随便 O(n^2) 就可以了。

还有的类似的题目，扩展到了 3 元，听教练说大概是贪心两次然后 dp 套 dp 即可。

非常厉害的题目。

最重要的性质是发现物品的质量和数量的特殊性。

考虑根号分治的思想，我们定义编号 i\leq \sqrt n 的物品为“小物品”，编号 i\gt \sqrt n 的物品为“大物品”。

我们可以用一种类似于 meet-in-the-middle 的思想。定义 f_i 为只用“小物品”拼出 i 的方案数量， g_i 为只用“大物品”拼出 i 的方案数量。

因此有 ans=\sum\limits_{i=0}^n f_i+g_{n-i} 。

先处理“大物品”，我们发现“大物品”的数量约束没有意义，因为选完任意一个“大物品”都可以发现，体积会大于 n 。

定义 dp1_{i,j} 为取了 i 个大物品，体积总和为 j 的方案总数，状态数是 O(n\sqrt n) 级别的。

但是完全背包复杂度不行，所以考虑使用例题 2 的 trick 优化，分类讨论是否有体积为 \lceil\sqrt n\rceil 的“大物品”。

同理容易推出了 dp1_{i,j}=dp1_{i,j-i}+dp1_{i-1,j-\lceil \sqrt n\rceil} 。

考虑“小物品”，因为个数少，所以可以直接多重背包+前缀和优化。

换根 dp 模板题。

考虑以 1\sim n 分别作为集会地点的代价 f_i ，不难发现由父节点的 f_u 得到子节点的 f_v 是容易的。

因此只需要第一次 dfs 时预处理出转移需要的信息，第二次 dfs 时转移即可。

这应该是换根 dp 的常见套路吧（没做过什么换根 dp 的题）。

状态设计和转移都是平凡的，主要是如何优化。

容易发现每次转移需要前缀最小值，转移时计算即可。