贪心

感冒咳嗽，头实在是太晕了，打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。

一句话题解

A – 破坏

简单的 $\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k)$ DP。记录每个节点的路径数奇偶性考虑是否翻转即可。

B – 共识

用 std::bitset 写的暴力大家都会。不过如果你胆子大些，不判断是否为部分分数据范围直接提交（加入随机化的）暴力，将喜提 $\text{100 pts}$。

命题：现有一个由 $2n$ 个元素构成的集合，保证 $2\mid n$。有 $n+1$ 个大小恰为 $n$ 的子集 $S_1,\cdots,S_{n+1}$。则至少存在 $n/2$ 对无序对 $(i,j),i\neq j, i,j\in[1,n+1]$，使得 $|S_i\cap S_j|\geq n/2$。

证明（引自宋佳兴学长）：记元素 $p,p\in\{1,\cdots,2n\}$ 在所有子集中出现的次数为 $\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)$。则显然有“所有子集两两之交的大小” $$\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}$$

考虑计算该式最小为何。不妨先考虑 $\binom{a}{b}+\binom{n-a}{b}$ 在何时取最小值。

引理：$\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq n$ 在 $a=\lfloor n/2\rfloor$ 处取最小值。

（更多…）