「计蒜客模拟赛」抉择

Summarize

给定有根树，点有权值，要求选出一些点，满足集合中的点的祖先权值比它小，求集合大小的最大值。

$n\le 300000$

#3211. 「CSP-S 2019」Emiya 家今天的饭

Summarize

在 $n\times m$ 的矩阵中选 $k$ 个元素，要求 $k\ge 1$，每行最多选 $1$ 个元素，每列元素个数不超过 $\lfloor \frac{k}{2}\rfloor$ 的方案数。

$n\le 100,m\le 2000$

#43463. 「计蒜客 2020.2 提高组」保卫水库

Summarize

给定有 $n$ 个节点和 $m$ 条边的有向无环图。每个节点有一定的水量，每个结点的水在水库被破坏后会均等地沿着出边流向其他节点。给出 $k$ 个操作，要求查询某个节点流入的水量，以及修改某个节点的初始水量。

$n\le 5000,m\le 10000,k\le 500000$

测试点的查询和修改次数比例接近 $1:1$

#3098. 「SNOI2019」纸牌

Summarize

有一副纸牌，牌一共有 $n$ 种，每种有 $C$ 张。三张连号的牌或三张相同的牌可以组成一叠，如果一组拍可以分成若干叠，就称其为一组王牌。现已从牌堆摸了一些初始牌，需要再挑出一些牌组成一组王牌，求有多少种可能组成的王牌。

$1\le n \le 1e18,0\le C \le 1000$

#3057. 「HNOI2019」校园旅行

Summarize

给定一个有 $n$ 个节点、 $m$ 条边的简单无向图，每个节点有权值 $0$ 或 $1$。有 $q$ 次询问，每次询问两个节点 $u$、$v$ 间是否存在一条路径（可重复），使经过的节点权值为 $01$ 回文串。

$n \le 5000, m\le 500000, q\le 100000$

#3226. 「USACO 2019.12 Platinum」Greedy Pie Eaters

Summarize

给定$n$个数中$m$个区间，每个区间有一个权值，要求输出总区间权值最大的一个序列使得每个序列不被之前的序列的并集完全覆盖

$1 \le n \le 300,1 \le m \le \frac{n(n-1)}{2}$

感谢@oy的贡献