拉格朗日乘数法学习笔记
November 22, 2023 •
1 Comment
我们知道对于树上背包,若每个结点上只有总大小为 $O(1)$ 的物品,则总复杂度为 $O(n^2)$;若再限制背包大小为 $m$,则总复杂度为 $O(nm)$。
关于树上背包的上下界优化,当时 fz 推荐我读的是 ouuan 的文章(cnblogs github pages),但是,我现在认为那里面的复杂度证明存在问题。
对任意 $2n-1$ 个整数,可以从中选出 $n$ 个使得这 $n$ 个数的和是 $n$ 的倍数。
形式化的,对任意 $a_1,\dots,a_{2n-1}\in \mathbb Z$,存在两两不同的 $i_1,\dots,i_n$ 使得:
$$
a_{i_1}+\dots+ a_{i_n}\equiv 0\pmod n
$$