再谈树上背包的上下界优化
July 5, 2023 •
Comment
关于树上背包的上下界优化，当时 fz 推荐我读的是 ouuan 的文章（cnblogs github pages），但是，我现在认为那里面的复杂度证明存在问题。
Erdos-Ginzburg-Ziv 定理
March 29, 2023 •
Comment
Erdos-Ginzburg-Ziv Theorem
对任意 $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
$$
广义串并联图方法学习笔记
January 30, 2023 •
Comment
广义串并联图指不存在同胚于 $K_4$ 的子图的图，其中，我们称两个图同胚当且仅当这两个图可由同一个图通过边细分变换得到，边细分指删去一条边，新建一个点，并将新点与原边的两个端点连边。