( ext{High Card Low Card})
USACO2015DEC Platinum T2
贝西和艾尔西在玩游戏。有 (2n) 张牌，牌上的数字是 (1) 到 (2n) ，贝西 (n) 张，艾尔西 (n) 张。
贝西事先知道艾尔西先后出的 (n) 张牌。
她们进行 (n) 轮出牌，轮流各出一张牌。一开始，谁的数字大谁赢。
贝西有一个特殊权利，她可以在任意时刻把规则从谁大谁赢改成谁小谁赢，问贝西最多能赢多少轮。
(2le nle 50000)
(1.00s, 128 MB)
Solution
考虑贪心。我们记 $pre[i]$ 表示 $1$ 到 $i$ 中最多能赢几局， $suf[i]$ 表示 $i$ 到 $n$ 中最多能赢几局。
答案 $ans = minlimits_{i=0}^{n} (pre[i] + suf[i+1])$
如果前面和后面选的数重复了怎么办？不存在这种情况！
你如果两个地方用的同一张牌i，肯定有一张牌没被用，那么分情况讨论。
1.比这张牌大。 那么这张牌可以替换掉在规则1下的牌i
2.比这张牌小。 那么这张牌可以替换掉在规则2下的牌i
中间过程用两个 $set$ 维护一下即可
复杂度 $O(nlogn)$
( ext{Cave Paintings})
USACO2020JAN Platinum T1
给你一张 (n imes m) 的图，每个格子要么是空的，要么是石头。
你可以给空格子上水，但是上完后的图要真实的（符合水不会再向四周流动）。
问你所有合法的上色的方案数，答案对 (10^9+7) 取模。
(1le n,mle 1000)
(2.00s, 256 MB)
Solution
从下往上考虑，显然一层可以分成若干段空格子，使得每一段都是连通的。观察知这是一个树形结构，那么我们可以做类树形dp:
$dp_u = 1 + Pi _{vin son(u)} dp_v$
从下往上用并查集维护就行了。
复杂度 $O(nm)$
( ext{Help Yourself})
USACO2020FEB Platinum T3
在一维数轴上有 (n) 条线段，第 (i) 条线段包含满足 (l_i le x le r_i) 的所有实数 (x) 。
定义一组线段的并为所有被至少一条线段所包含的实数 (x) 的集合。
定义一组线段的复杂度为这些线段的并的连通区域数量的 (K) 次方。
计算所有 (2^n) 个子集的线段组复杂度之和，答案对 (10^9+7) 取模。
(1le nle 10^5, 2le Kle 10, l_i < r_i, 保证 { l_i, r_i} = { 1, 2, ..., 2n-1,2n } (1le ile n))
(2.00s, 256 MB)
Solution
首先将这些线段按左端点先排好序。考虑 $K=1$ 时如何做。这一档是 Gold T2 原题。
用 $dp[i]$ 表示前 $i$ 个线段的 $2^i$ 个子集的线段组复杂度之和。
那么第 $i$ 根线段不选： $dp[i-1]$ ；
第 $i$ 根线段选：$dp[i-1]+一些额外产生的贡献$
注意左端点已排好序，所以要想产生贡献，则之前的线段的右端点均小于该线段的左端点。
右端点我们可以利用前缀和提前预处理，于是这一部分的贡献就可以计算了。
接下来是正解时刻：
