CF 高分段题目总结

· · 个人记录

思维：指临场分析的难度以及需要独立思考的内容深度 / 数量。

技巧：指包含的套路 / trick 的难度 / 数量。

细节：指完成代码或思考必不可少的小细节难度 / 数量。

代码：指考虑板子等因素下完成代码的综合难度。

颜色与难度关系与洛谷一致：\color{Red}\text{低} ，{\color{Green} \text{较低}}，{\color{Blue} \text{中}}，{\color{Purple}\text{较高}}，\color{Black}\text{高}。

CF576E Painting Edges

代码长度：1.53k（压行） #### 题意 给定一张图，每条边有颜色，初始为无色，$q$ 次操作每次修改某条边的颜色，若修改后满足「同一种颜色的边的导出子图是二分图」那就进行修改，否则不进行。你需要判断每个操作是否会执行。 $n,m,q\le 5\times 10^5

思路

对同一种颜色开种类并查集维护合法性，使用线段树分治进行维护操作。

问题在于一个操作如果不合法就不会执行，而在一开始我们是不知道每个操作是否合法。那就在每个操作第一次出现的时间判断一下，如果合法就插入线段。

CF585F Digits of Number Pi

#### 题意 给定一个长度为 $n$ 的数字串 $s$ 和两个长度为 $m$ 的数字串 $l,r$，求「存在长度至少为 $\frac m2$ 的子串是 $s$ 的子串」的数字串 $t\in[l,r]$ 的数量。 $n\le 10^3,m\le 50

思路

注意到 n 比较小，所以把 s 所有长度为 \frac m2 的子串插入 AC 自动机，然后在 AC 自动机上数位 DP 即可（是否顶上界、是否匹配到）。

CF587D Duff in Mafia

给定一张图，每条边有颜色和权值，需要选出若干条边使得它们是一个匹配，并且剩下的每种颜色的边都是匹配。最小化选出边的最大权值。 $n,m\le 5\times 10^4

思路

先二分，变成从小于等于 k 的边里选，判断是否存在方案。

匹配 \to 每个点至多连一条边 \to 若选择某条边则其他的都不能选 \to 2-SAT。

## CF611H New Year and Forgotten Tree $\color{Purple}\text{思维}$，$\color{Purple}\text{技巧}$，$\color{Blue}\text{细节}$，$\color{Purple}\text{代码}$，代码长度：3.53k（未压行） #### 题意 有一颗树，点的编号从 $1$ 到 $n$。你只知道每条边连接的两个顶点的编号在十进制下的位数，给出一个构造或者判断无解。 $n\le 2\times 10^5

思路

位数很低，只有 6，自然地把点分为 6 个集合，我们可以求出 每个集合的大小 以及 集合两两之间的连边数量。

进行一步构造（hard）：为每个集合选择一个代表元，如果存在合法的树，一定存在一种情况，使得代表元连成一个连通块，其他点连向某一个代表元。

用 prufer 枚举树形 \to 发现对于每条边 (x,y) 都面临一个选择：从 x 的代表元连向 y 还是 从 y 的代表元连向 x \to 构造一个匹配模型：

左部点是所有的不在枚举的树上的边，右部点是 6 个集合，每个集合的容量是集合大小 -1（减去代表元）。左部的边 (x,y) 向右部两个集合 x 和 y 连边，意味着可以选择 x 或者 y 集合的代表元。

边的数量很多 \to 通过连接的集合不同划分成 \frac {6 (6+1)}2 组边，每组边的数量已知 \to 二分图多重匹配。

CF613E Puzzle Lover

#### 题意 有一个 $2\times n$ 的字符矩阵，给定一个串 $s$，问有矩阵中有多少条不交路径恰好组成 $s$。 $n,|s|\le 2\times 10^3

思路

随便走很困难，注意 2\times n 很重要 \to 如果想要回头就必须直着走 \to 从回头点开始考虑：

借用小粉兔的图：两个蓝线之外是回头部分，中间是随便走部分。

回头部分是一个 U 型，用哈希什么的之间就能处理出每个点向左 / 向右是否存在一个长度为 i 的 U 形。

中间随便走，但只可能是从左往右或者从右往左走，都是单向的，可以 DP：f_{i,j,k} 表示当前在 (i,j)，上一步是从左边转移，匹配了 k 位的方案数，g_{i,j,k} 表示当前在 (i,j)，上一步是从上边转移，匹配了 k 位的方案数。

需要特别注意可能计算重复的贡献。

CF627E Orchestra

#### 题意 在一个 $r \times c$ 的矩阵中有 $n$ 个点，问有多少个连续子矩阵至少包含 $k$ 个点。 $r,c,n\le 3\times 10^3,k\le 10$。 #### 思路 首先最正常的做法是枚举上边界和下边界，内部用双指针处理，复杂度 $O(r^2c)$，但是与 $k$ 无关。 枚举下边界可以从上边界开始向下推 $\to$ 考虑新加入一行，这一行的每个点 $i$ 的贡献为 $(x_i-x_{i-1})\times (c-x_{f_i}+1)$，其中 $i-1$ 是以列为第一关键字，以行为第二关键字排序下的 $i$ 前驱，而 $f_i$ 表示从 $i$ 向右第 $k$ 个点。 新加一个点 $i$ 只影响前 $k$ 个点的 $f$，并且点 $i$ 的贡献可以用平衡树在 $O(\log n)$ 的复杂度算出，所以我们可以 $O(k\log n)$ 的复杂度加入一个点，总复杂度 $O(rc+r(r+nk\log n))=O(r^2+rc+rnk\log n)$。 因为带了个 $\log$ 过不去，并且**只加点不删点** $\to$ 倒着用链表维护。 ## CF750G New Year and Binary Tree Paths $\color{Blue}\text{思维}$，$\color{Purple}\text{技巧}$，$\color{Green}\text{细节}$，$\color{Green}\text{代码}$，代码长度：1.27k（压行） #### 题意 一颗无穷个节点的线段树，求有多少条树上的简单路径编号和为 $s$。 $s\le 10^{15}

思路

路径 \to 先考虑一条链的做法，每个节点有向左和向右两个决策 \to 假设一开始全向左，再计算若干个节点向右的贡献。

设链顶为 x，链长为 h，一直走左儿子的贡献就是 \sum\limits_{i=0}^{h-1}2^ix=(2^h-1)x。假设在这条链自下而上第 k 个儿子是右儿子，则额外增加 \sum\limits_{i=0}^{k-1}2^{i}x=(2^k-1)x 的贡献。

令 p_i 表示自下而上第 i 个节点是左儿子（p_i=0）还是右儿子（p_i=1），则一条链的总贡献就是 s=(2^h-1)x+\sum\limits_{i=1}^{h-1}p_i(2^i-1)。0\le \sum\limits_{i=1}^{h-1}p_i(2^i-1)<(2^h-1)x，也即 (2^h-1)x\le s<2(2^h-1)x，那么 x=\lfloor\frac{s}{2^h-1}\rfloor。

换句话说，假设我们已知 s 和 h 就可以确定唯一一个 x。因此只需枚举 h\in[1,\lfloor \log_2 s\rfloor]，然后判断是否存在一组 \{p\} 使得 s -(2^h-1)x=\sum\limits_{i=1}^{h-1}p_i(2^i-1)，也即是否存在一个 \{1,3,7,15,\cdots,2^{h-1}-1\} 的子集和为 s-(2^h-1)x。又因为这些数中任意一个数都不是其他若干数之和，所以可以从大到小贪心，能取就取，判断是否有剩余即可。

现在考虑路径是两条链的拼接：

设 LCA 为 x，x 左儿子向下的链长为 h_1，x 右儿子向下的链长为 h_2，一直走左儿子的贡献就是 x+2x(2^{h_1}-1)+(2x+1)(2^{h_2}-1)。

令 p_i 表示左链自下而上第 i 个节点是左儿子还是右儿子，q_i 同理表示右链，那么额外增加的贡献是 \sum\limits_{i=1}^{h_1-1}p_i(2^i-1)+\sum\limits_{i=1}^{h_2-1}q_i(2^i-1)。同理枚举 h_1,h_2\in[1,\lfloor\log_2s\rfloor] 那么也可以确定唯一一个 x=\lfloor\frac{s-2^{h_2}+1}{2^{h_1+1}+2^{h_2+1}-3}\rfloor。

现在要做的是判断是否存在一组合法的 \{p\},\{q\}，再枚举 k=\sum p+\sum q，那么数位 DP 一下即可，f_{i,j,k} 表示前 i 位选择了 j 个，是否进位。

CF786E ALT

#### 题意 给一颗 $n$ 个节点的树，每个边上有一个守卫。有 $m$ 个居民，每个居民有一个散步路径（两个节点的树上最短路）。一个居民高兴当且仅当他获得了一个宠物或者他散步的路径上所有的守卫都有宠物。宠物可以分配给居民或者守卫者。求最少需要几只宠物才能让所有居民高兴。输出方案。 $n,m \le 2\times 10^4

思路

要给每个宠物分配给一条边或者一个路径 \to P1231 教辅的组成。一条路径连边数过多，所以可以倍增优化建图。

CF793F Julia the snail

#### 题意 有一个长为 $n$ 的杆，上面有 $m$ 条绳子，每条绳子可以让蜗牛从 $l_i$ 爬到 $r_i$，蜗牛也可以自然下落。$q$ 次询问 $x$ 出发，途中高度不能低于 $x$ 或高于 $y$，问最高能爬到的位置。 $n,m,q\le 10^5

思路

不低于 x 且不高于 y 是二维限制 \to 一维扫描线掉 \to 把绳子和询问按右端点排序。

在询问 [l,r] 之前只加入右端点不超过 r 的绳子 \to 维护一个答案序列 f，其中 f_i 表示从 i 开始，只走当前加入的绳子，最远能走到哪里。

考虑加入一条绳子 [l,r]，其影响是 f_i\gets r(i\in [1,l]\land f_i\ge l)，即 [1,l] 中所有大于等于 l 的 f_i 都变成 y，使用吉司机线段树即可。

CF793G Oleg and chess

#### 题意 有一个 $n\times n$ 的矩阵，每行每列至多能放一个棋子，另外有 $q$ 个矩形的区域不能放棋子（这些矩形区域互不相交），问最多能放多少个棋子。 $n,q\le 10^4

思路

经典网络流建模，但边数太多 \to 扫描线 + 线段树优化建图。

普通的想法是给每一行开一颗线段树，但是发现相邻两行变化的并不多，动态开点就行了。

CF827F Dirty Arkady's Kitchen

#### 题意 给定一个无向无权图，其中第 $i$ 条边可以在 $[l_i,r_i]$ 通过，问从 $1$ 出发到达 $n$ 的最早时间。不可以在一个点上停留。 $n,m\le 5\times 10^5

思路

因为可以在一条边上反复走，到达两点的奇偶性不变，所以把每个点拆成奇偶两个点，一条边拆成奇偶 / 来回四条边。现在相当于可以在一个点上停留了。

把所有边放入堆，按 l 从小到大排序，对每个点维护 f_i 表示在这个点最晚能停留到什么时候，那么如果一条边 (u,v,l,r) 满足 l\le f_u 那么 f_u\gets \max(f_u,r)，否则就把这条边先存着，等以后再说。

这题太过于精妙了。

CF1178G The Awesomest Vertex

#### 题意 给定一颗以 $1$ 为根的树，每个节点有两个权值 $a,b$。定义 $R(u)$ 表示 $u$ 的所有祖先组成的集合，则一个节点的价值为 $$ \left|\sum_{x\in R(u)}a_x\right|\cdot\left|\sum_{x\in R(u)}b_x\right| $$ 支持 $q$ 次操作： 1. $a_v\gets a_v+w
  1. 输出以 v 的子树中价值的最大值。
#### 思路 转化为区间修改，区间求最大值。让 $x$ 处 $a$ 的变化量为 $\Delta$，那么价值为 $(\sum+\Delta)\sum =\Delta\sum + \sum\sum$ 相当于关于 $\Delta$ 的一次函数。 也即区间 $x$ 平移一段距离，求 $\max f_i(x_i)$。 看起来就不可做 $\to$ 分块 $\to$ 块内维护凸包，查询时块间取 $\max$。 详细地：修改时整块打 tag，散块重构；查询时整块二分，散块暴力。总复杂度 $O(q\sqrt n\log n)$，但是修改时散块重构可以归并，查询时整块二分的位置单调递增可以用双指针，总复杂度 $O(q\sqrt n)$。 ## CF1188D Make Equal $\color{Green}\text{思维}$，$\color{Blue}\text{技巧}$，$\color{Green}\text{细节}$，$\color{Blue}\text{代码}$，代码长度：1.12k（未压行） #### 题意 给定 $n$ 个数字，每次操作可以给某个数字加上 $2$ 的幂，问使得所有数字相等的最少操作次数。 $n\le 10^5,a_i\le 10^{17}

思路