Codeforces Round 966 (Div. 3) 记录

· · 个人记录

本场失误

赛时只过了 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 。

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

1. $dp_{i,j} \leftarrow dp_{i-1,j}+\max\{0,b-j\}
  1. 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 次查询是稳过的。