【题解】[NOI2020] 命运
[NOI2020] 命运
给定一棵 $n$ 个点，以 $1$ 为根的树，现让你对边染色 $(0/1)$ 。有 $m$ 条限制，每条限制形如 $(u_i,v_i)$ ，意为 $u_i$ 到 $v_i$ 的路径上至少要有一条 $1$ 边，其中保证 $u_i$ 是 $v_i$ 的祖先。问染色方案数。
$n,m \le 5 \times 10^5$
标签 dp 下的文章
【题解】[USACO20DEC] Sleeping Cows P
动态规划优化
题意：
现给定长度均为 $n$ 的数组 $s_i$ 与 $t_i$，$s_i$ 能与 $t_j$ 匹配当且仅当 $s_i\le t_j$。一组匹配是极大的，当且仅当对于任意一个匹配对 $(s_i,t_j)$ 均满足 $s_i\le t_j$ ，且任意未被匹配的 $s$ 与 $t$ 中无法再组成匹配对。
求所有极大匹配的方案数。
$n\le 3000,s_i,t_i\le 10^9$。
【解题报告】CSP-S 2020
考完自闭了，怎么能这么菜......