PKUSC2021 部分题解
D1T2 逛街题意给定一个长度为 $n$ 的序列，有 $m$ 次操作，每次操作为如下两种形式之一：1 l r 从左到右遍历 $i \in [l,r-1]$，令 $a_i \gets \max(a_i,a_{i+1})$输出区间 $[l,r]$ 中所有前缀最大值的和保证初始时 $a_i$ 两两不同。$n,m \leq 3 \times 10^5$。题解有一档部分分是，保证操作 1 中 $l=1...
D1T2 逛街题意给定一个长度为 $n$ 的序列，有 $m$ 次操作，每次操作为如下两种形式之一：1 l r 从左到右遍历 $i \in [l,r-1]$，令 $a_i \gets \max(a_i,a_{i+1})$输出区间 $[l,r]$ 中所有前缀最大值的和保证初始时 $a_i$ 两两不同。$n,m \leq 3 \times 10^5$。题解有一档部分分是，保证操作 1 中 $l=1...
题意有一个 $n$ 个点的 DAG，现在有 $k$ 波进攻，第 $i$ 波有 $i$ 个人，它们每个人会选择一条 DAG 上的路径，并占领这个路径上的所有点，路径之间是不能相交的。第 $i$ 波进攻前可以做一些准备，可以花 $1$ 秒关闭某个点的所有入边，或关闭某个点的所有出边。第 $i$ 波进攻有个参数 $a_i,b_i$，如果花费了 $t_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_...