Liuxizai's Blog

做题笔记 2023.3

March 30, 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
$$

CF1784D Wooden Spoon

这类问题通常可以按两种顺序 dp，本题中我们需要限制每组中最小的数依次递减，一种显然的想法是从大到小 dp，对于每个数考虑该数是与之前的某些数构成一组还是不做任何操作，类似于 ARC093F，当然由于我们需要对第一个数的每种取值计算方案数，所以 dp 需要反向，转移过程中的组合系数可能会很反常。另一种是从后向前，从小到大 dp，在填数的过程中留下一些空位，在后期对每个数决策是去填上之前的空位还是新开一组。两种方法都是 $O(n2^n)$ 的。

竞赛图学习笔记

February 24, 2023 • 笔记 • Comment

定义：对任意 $u,v$，存在 $u\to v$ 或 $v\to u$ 的有向图为竞赛图。也可以说是有向完全图。

Solution. 取石子游戏

February 9, 2023 • 题解 • Comment

Description

$n$ 堆石子，第 $i$ 堆有 $a_i$ 个石子，颜色为 $c_i$。A 和 B 轮流行动，A 先手，每人有两种操作：

选择一堆石子并从中取出任意个石子。
选择一种颜色并从若干堆这种颜色的石子中取出不超过 $m$ 个石子。

不能不取。不能操作的人失败。