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_...