拉格朗日乘数法学习笔记
November 22, 2023 •
1 Comment
做题笔记 2023.10
October 12, 2023 •
Comment
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
$$
Solution. CF1025G Company Acquisitions
January 31, 2023 •
Comment
Description
有 $n$ 个结点，每个结点有两种状态：active 和 acquired。
一个 active 结点后面跟着若干 acquired 结点。
对于两个 active 结点 $A,B$，如果 $A$ 收购 $B$，那么所有跟着 $B$ 的结点变为 active，$B$ 变为 acquired 并跟在 $A$ 后面。
每次随机选择两个 active 结点，随机让其中一个收购另一个。
求只剩一个 active 结点的期望步数。
$n\le 500$