CF1525F Goblins And Gnomes
题意有一个 $n$ 个点的 DAG，现在有 $k$ 波进攻，第 $i$ 波有 $i$ 个人，它们每个人会选择一条 DAG 上的路径，并占领这个路径上的所有点，路径之间是不能相交的。第 $i$ 波进攻前可以做一些准备，可以花 $1$ 秒关闭某个点的所有入边，或关闭某个点的所有出边。第 $i$ 波进攻有个参数 $a_i,b_i$，如果花费了 $t_i$ 时间准备，如果不会所有点都被占领，就会获得...
题意有一个 $n$ 个点的 DAG，现在有 $k$ 波进攻，第 $i$ 波有 $i$ 个人，它们每个人会选择一条 DAG 上的路径，并占领这个路径上的所有点，路径之间是不能相交的。第 $i$ 波进攻前可以做一些准备，可以花 $1$ 秒关闭某个点的所有入边，或关闭某个点的所有出边。第 $i$ 波进攻有个参数 $a_i,b_i$，如果花费了 $t_i$ 时间准备，如果不会所有点都被占领，就会获得...
挺有意思的：我大概写完这套题的时候被通知被权贵申诉杀了，后来买了 C 决定还是补完比较好。A. Edit Distance Yet Again题意求两个字符串的编辑距离，如果答案 $> k$ 就输出 NO，否则需要输出方案。$k \leq 1000,|s|,|t| \leq 10^6$。题解一个比较套路的做法：考虑最基本的暴力 dp：$f_{i,j}$ 表示 $s$ 的长度为 $i$ ...
题意有一条长度为 $n+1$ 的村庄，编号依次为 $0\ldots n$。最初，在 $i$ 和 $i+1$ 之间有双向通行的铁路。现在有两个铁路公司（A 和 B）要争夺这些村庄。$0$ 和 $n$ 这两个村庄同时被两个铁路公司占有，$[1,n-1]$ 内的村庄会被其中一个铁路公司占有。假设某个铁路公司占有的村庄按顺序排序为 $a_1,a_2,\ldots,a_m$，那么在 $(a_1,a_2...
题意有 $n$ 行 $m$ 列的棋盘，每个位置颜色一开始是红色或蓝色。每次操作你可以选择一个红色格子，选择将这个格子所在行/列都涂成白色格子。求构造一组最大化白色格子的方案。$n,m \leq 2500$。题解比赛的时候没有尝试往二分图上去想，因为感觉这种带先后覆盖顺序的问题好像不是很能做，但是事实证明错了。。这种每次覆盖一行，或者一列的做法都考虑将行列抽象成点，操作位置抽象成边。对于这个题...
题意有一个长度为 $n$ 的排列 $p_i$，你可以执行以下操作任意次：将数字 $x$ 移动到任意一个位置，花费 $A_x$将数字 $x$ 移动到开头，花费 $B_x$将数字 $x$ 移动到结尾，花费 $C_x$求排序最小代价。$n \leq 2 \times 10^5$。题解首先 $B_x,C_x$ 都要和 $A_x$ 取 $\min$。手动模拟一下，我们先固定一些不动的数 $a_1,a_...