本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-15 12:50:31

本场失误

赛时只过了 A-F，G 题题目太长直接跳过，H 题写完了正解，忘了判断长度为 $0$ ，就差几分钟。

赛后做 G 猜了个结论看着没错，写了个二分直接过了，H 判了下长度为 $0$ 就过了。

丢了 G,H perf 还能苟到 2000+ 是我没想到的，小号 $1242 \rightarrow 1561$。

A

注意到满足以下几个条件才是重要数字：

1. 长度一定大于等于 $3$。

2. 前两个数字分别是 $1,0$。

3. 第三个数字大于等于 $2$，或者第三个数字等于 $1$ 且总长度大于等于 $4$。

B

模拟就可以了。

C

本质上 $s$ 作为模板，决定了哪些位置上的数是同一类，哪些位置上的数不是同一类。

那么，现在使用一个算法，对每个位置上的数，编号其所属的类。

考虑从前到后扫描，设当前有 $x$ 个种类，如果当前字符之前出现过，那就与之前那个字符归于同一类，否则就新建一个 $x+1$ 种类。

明显，如果 $s$ 与 $t$ 匹配，那么 $s,t$ 按照上述算法，每一个位置所属的类别都是相同的，反之一定是不同的。

D

本题最大的坑点在于一个数可以选多次，我赛时是看到公告才注意到这一点。

容易发现，第一个 L 之前和最后一个 R 之后的数字都不能被选择。

从这里入手，容易证明第一个 L 应当与最后一个 R 匹配。

然后，设其位置分别是 $l,r$，那么问题转化为了 $[l+1,r-1]$ 区间的子问题。用相同做法就可以。

E

由于 $n\cdot m \le 2\cdot 10^5$，本题只需要枚举每个位置，计算其被多少 $k\times k$ 矩形包含。

然后贪心选择。

F

考虑到各个矩阵互不影响，且事实上只关心每个矩阵贡献为 $i$ 时的代价 $c_i$ 。

考虑对每个矩阵预处理贡献对应的代价。

$dp_{i,j}$ 代表当前矩阵涂满了 $i$ 行 $j$ 列的最小代价。

1. $dp_{i,j} \leftarrow dp_{i-1,j}+\max\{0,b-j\}$
2. $dp_{i,j} \leftarrow dp_{i,j-1}+\max\{0,a-i\}$

对于 $c_i$ ：

$c_i \leftarrow \min\limits_{j=0}^{i}\{dp_{j,i-j}\}$

现在要求总贡献 $k$ ，求最小代价，背包就可以。

G

容易发现答案具有单调性，并且容易证明对于任意一个点，都应该尽可能早到达（换句话说，不存在一种情况，使得晚到达一个节点反而会使最终到达时间提前）

二分，跑 dijkstra 就可以了。

我的理解是，假设一个节点在 $x,y$ 时刻到达，$x \gt y$ ，且 $x$ 时刻到达的答案更优，那么 $y$ 时刻可以原地等待到 $x$ 时刻，取得同样优秀的答案。

H

注意到长度为 $k$ 的段是包含在长度为 $k+1,k+2,\cdots $ 的段的。

由于本题中 $k$ 的上限是 $2 \cdot 10^6$，超过 $2 \cdot 10^6 $ 的长度可以直接当作 $2 \cdot 10^6$ 来处理。

每次操作，相当于删除一个或两个段，加入一个或两个段。

每次查询，相当于在长度为 $[k,2\cdot 10^6]$ 的段里找最小左端点。

整理一下，发现需要支持的操作是这些：

1. 给定 $1 \le x,y \le 2\cdot 10^6,$ 在第 $x$ 个位置插入一个数字 $y$。
2. 给定 $1 \le x,y \le 2\cdot 10^6$，在第 $x$ 个位置删除一个数字 $y$。
3. 给定 $l$ ，查询 $l$ 开头的后缀的所有集合的最小值。如果没有数字就输出 2000001。

开个 $2 \cdot 10^6$ 的线段树，$2 \cdot 10^5$ 次查询是稳过的。