251125 模拟赛
T1
有 \(n\) 个怪物和 \(k\) 个地雷，每个怪物有初始位置 \(a_i\) 和初始血量 \(h_i\)，每个地雷有固定位置 \(x_i\)。你可以：
- 花费 \(1\) 的代价减少一个怪物 \(1\) 点血量；
- 花费 \(1\) 的代价将一只怪物移动 \(1\) 点距离；
- 花费 \(1\) 的代价点燃一颗地雷，打败所有和地雷在同一位置的怪物；
问最少消耗多少代价可以打败所有怪物。
\(1\le n,k\le 2\times 10^5,~1\le a_i,h_i\le 10^9\)
由于移动的代价和点燃地雷相等，因此每一个怪物只会考虑离他最近的那一个（两个）地雷。从左往右贪心考虑每一个怪物，如果直接砍死的代价严格小于两侧的地雷，那么选择前者；否则选择后者。如果两侧地雷代价相等，那么优先选择右边的地雷，因为这样对后面更有利。
T2
线段树模板题
T3
初始给定一个长为 \(2n\) 的合法括号序列。你需要让左括号匹配到一些新的右括号，只需要满足以下条件：
- 左括号在其匹配的右括号左边；
- 任何一个左括号都不能匹配原先匹配的右括号；
计数合法匹配方案，对 \(10^9+7\) 取模。
\(n\le 3000\)
如果没有第二个条件，那么一个右括号可以匹配的左括号数量等于：其左边左括号的数量减右括号的数量。对第二个条件进行容斥，钦定一个一个集合的左括号匹配原先的右括号，那么方案数就是把它们扔掉之后任意匹配的方案数。这样可以做到 \(O(2^npoly(n))\)。
注意到对于一个右括号我们只关心它外面有几层被钦定的括号。考虑括号序列形成的树结构，把外层钦定的括号数量记入状态，枚举本层括号是否钦定，然后做完了。