Codeforces试题乱做 Part2

Posted on 2022-01-29 Edited on 2022-04-11

终于上 $\color{orange}{\text{Master}}$ 了, 再接再厉, 暂时决定不开小号, 两个 $\color{orange}{\text{Master}}$ 号一起打, 争取冲到更高的段位, 至于 $\text{div 2}$ 的话就和别人一起开黑吧.

希望这个 $\text{Part}$ 的题能有更多是我自己独立做出来的, 没有的话也希望是很好的题, 绝不摆烂.

$\text{[CF802N]April Fools’ Problem (medium)}$

$\color{green}{\text{[EASY]}}$

惯例开篇 $\color{green}{\text{[EASY]}}$ .

看到最小化, 有限制, $n$ 还贼小, 不难想到是个费用流.

可以发现最暴力的建图是个长得像个二分图的样子的图, 最后是用一个伪汇点连真汇点一条 $(k,0)$ 的边来做限制.

如果给每个 $a_i$ 和 $b_i$ 都单独建点, 这样边数会大得吓人, 考虑优化建图.

发现 $a$ 和 $b$ 之间的边很多, 而且大多数没必要, 考虑把 $a_i$ 和 $b_i$ 缩点成一个, 然后通过在点 $i$ 和 $i+1$ 之间连一条 $(\infty,0)$ 的边来做到 $i_p \leqslant j_p$ 的限制.

这样点数边数都得到了很大的优化.

$\text{[CF802O]April Fools’ Problem (hard)}$

$\color{green}{\text{[EASY]}}$

考虑到费用流的本质就是反悔贪心, 同时不难看出在 $n,a,b$ 固定时, 令 $f(i)$ 表示 $k=i$ 时的答案, $f(i)$ 是一个下凸函数, 并且斜率不能为负数.

考虑 $wqs$ 二分, 并且斜率在 $[0,2\times 10^9]$ 上.

接下来考虑一个贪心, 对于每个 $b_i$ 要么找一个之前没选过的 $a_j$ , 若 $a_j+b_i-k \leqslant 0$ 则选择 $a_j$ 并更新答案, 这显然是错误, 于是考虑反悔贪心.

每个 $b_i$ 要么不选, 要么和 $a_j$ 配对, 贡献为 $a_j+b_i-k$ , 要么把某个 $b_j$ 换掉, 贡献为 $b_i-b_j$ , 用堆维护即可.

时间复杂度线性对数平方.

$\text{CF1363F Rotating Substrings}$

$\color{blue}{\text{[NORMAL]}}$

考的时候怎么可能想的出来这种神仙题嘛, 思维性太强了.

首先注意到一个操作的实质是把一个字母先前移动任意位值, 所以只要 $s$ 和 $t$ 中各个字母出现的次数相同, 就肯定有解.

我们要最小化选择的字符, 考虑 $dp$ , 设 $f_{i,j}$ 表示 $s$ 长度为 $i$ 的前缀加上后面若干个字母, 等于 $t$ 长度为 $j$ 的前缀的最小花费, 这里要求 $i \leqslant j$ , 那么答案即为 $f_{n,n}$ .

转移如下:

可以不让 $s_i$ 和 $t_j$ 匹配, 而是把 $s_i$ 向前移动, 花费 $1$ , 转移为 $f_{i,j} = f_{i-1,j}+1$ .
如果 $s_i = t_j$ , 那么可以直接令二者匹配, 转移为 $f_{i,j} = f_{i-1,j-1}$ .
如果 $i$ 后面的字符有多的 $t_j$ , 那么可以从 $i$ 后面抽出一个等于 $t_j$ 的字符放到这里与 $t_j$ 匹配, 转移为 $f_{i,j} = f_{i,j-1}$ , 需要注意的是, 这条转移会在之后的一次第一条转移被计算贡献, 所以这里不增加贡献.

三种转移取最小值, 时间复杂度 $\mathcal{O}(n^2)$ .

$\text{[CF1633E]Spanning Tree Queries}$

$\color{green}{\text{[EASY]}}$

说的好啊, 所谓教育场, 场场被教育, 但是这题属实是不难, 为啥就是没想到呢.

还是考虑最小生成树求解, 按照 $|w_i-x|$ 排序.

我们考虑在什么时候, 两条边会交换顺序, 不难想到这个分界值是 $\frac{w_i+w_j}{2}$ , 再考虑最多交换 $m^2$ 次, 于是可以对于每个边界处理出来答案.

对于一个询问 $x$ 可以二分找到它对应的顺序, 然后在通过计算比 $x$ 大的边的数来补齐少算或者多算的值.

$\text{[CF1633F]Perfect Matching}$

$\color{green}{\text{[EASY]}}$

说实话这题不应该有那么高的评分, 这评分纯属是因为树剖, 其实并不难, 但还是有教育意义的.

首先不难想到一个贪心的匹配方法, 每次选择一个叶子节点, 将它于它的父亲匹配, 然后删掉, 如果这样能匹配成功, 那么就有完美匹配, 否则没有.

想到这其实就做完一大半了, 但是如果这时候只想着更快速的匹配或者认为这样匹配不会改变匹配对象的话是没前途的, 这也是被教育到的地方, 这时候应该去观察一下这种匹配的性质.

我们发现, 每次删掉的是两个点, 所以不会改变任意一个节点的子树大小的奇偶性, 还能发现因为不改变奇偶性, 所以每次取叶子节点, 相当于取一个子树大小都是奇数的节点, 匹配它的父亲, 如果有完美匹配的话, 那它的父亲一定子树大小是偶数.

接下来把子树大小是偶数的节点简写为偶数节点, 子树大小是奇数的节点简写为奇数节点.

于是我们可以改变匹配策略, 每个奇数数节点与其父亲匹配, 所以有完美匹配就得每个偶数定点恰好有一个奇数节点儿子, 每个奇数节点恰好有一个偶数节点作为父亲, 所以, 奇数节点数量与偶数节点应该相等.

事实上偶数节点个数与奇数节点相等的话就必然有完美匹配.

所以树剖来维护节点状态与选择的边. 添加一个点的复杂度是 $\mathcal{O}(\log^{2}{n})$ , 求一种方案需要 $\mathcal{O}(n \log{n})$ 的复杂度判断每条边是否选择了.

$\text{[CF1634F]Fibonacci Additions}$

$\color{green}{\text{[EASY]}}$

又被简单题教育了, 说实话自己也不知道从何反思这题, 就姑且认为是见的不够多吧, 不过吃一堑长一智, 下次再做不出就说不过去了.

毋庸置疑的是, 肯定要变成 $c_i = a_i-b_i$ 再开始做题, 但是确实是没想到, 应该多跟着给出的递推式走走的, 再令 $d_1 = c_1,d_2 = c_2-c_1,d_i = c_i-c_{i-1}-c_{i-2}$ $(i \geqslant 2)$ , 很显然, 只有在所有的 $d_i = 0$ 时原数列才相等.

接着就是套路的考虑一次 $A$ 操作会对 $d$ 序列造成什么影响.

$d_l \leftarrow d_l+1 \\ d_{r+1} \leftarrow d_{r+1}-fib_{r-l+2} \\ d_{r+2} \leftarrow d_{r+2}-fib_{r-l+1}$

类似的考虑 $B$ 操作.

以后绝对不能被这种题教育了.

$\text{[CF626F]Group Projects}$

$\color{blue}{\text{[NORMAL]}}$

这个评分是因为我没见过这种套路吧, 这种考虑几个端点没有确定的 $dp$ 属实牛皮, 主要是模型也没想到, 想到也没往差分上想.

把 $a$ 排序之后就相当于选集合最大和最小值了, 经典状态设计是不考虑分了多少个集合, 只考虑有多少个集合只确定了一个值.

称只选定了一个端点的线段为未闭合, 则有四种转移情况.

加到一个没有闭合的组里, 这一组还没闭合, 对总和谐数贡献为 $0$ .
加到前面任意一个组里, 加入后组闭合, 对总和谐数贡献为 $a_i$ .
新建了一个组, 这一组没闭合, 对总和谐数贡献为 $-a_i$ .
新建了一个组, 这一组闭合了, 对总和谐数贡献为 $0$ .

那么可以设 $f_{i,j,k}$ 为考虑前 $i$ 个数, 有 $j$ 个未闭合, 总和谐数为 $k$ 的方案数, 有类似转移:

$f_{i,j,k} = f_{i-1,j,k} \times j + f_{i-1,j+1,k-a_i} \times (j+1) + f_{i-1,j-1,k+a_i} + f_{i-1,j,k} \\ = (f_{i-1,j,k}+f_{i-1,j+1,k-a_i}) \times (j+1) + f_{i-1,j-1,k+a_i}$

然而会出现负下标的情况, 总状态数是 $n^2 \sum a_i$ 的, 过不去, 考虑优化转移.

思考状态数太多的原因, 计算贡献的时候有加有减, 这样会让第三维的下标变的很小, 如果把这个过程变成单调不减的过程, 那事情就变的简单了.

那么这时候就应该想到差分, $a_r-a_l = \sum\limits_{i=l+1}^{r}{a_i-a_{i-1}}$ , 那么加入第 $i$ 个数之和的时候就相当于 $x \times (a_{i}-a_{i-1})$ ( $x$ 是之前没有闭合的组 )

令 $d = a_i-a_{i-1}$ 那么就可以轻松得到转移方程:

$f_{i,j,k} = f_{i-1,j,k-j \times d} \times j + f_{i-1,j+1,k-(j+1) \times d} \times (j+1) + f_{i-1,j-1,k-(j-1) \times d} + f_{i-1,j,k-j \times d} \\ = f_{i-1,j,k-j \times d} \times (j+1) + f_{i-1,j+1,k-(j+1) \times d} \times (j+1) + f_{i-1,j-1,k-(j-1) \times d}$

时间复杂度 $\mathcal{O}(n^2k)$ .

$\text{[CF490F]Treeland Tour}$

$\color{blue}{\text{[NORMAL]}}$

这个记录 $thusc2021\;Day1T2$ .

将 $a$ 离散化, 首先有暴力 $dp$ , 记 $up_{x,i}$ 表示从 $x$ 的子树中某个节点到 $x$ 的路径上上升子序列最后一个数为 $i$ 时的最长长度, $down_{x,i}$ 表示从 $x$ 到其子树中的某个节点的路径上下降子序列第一个数为 $i$ 时的最长长度, 那么有转移(其中 $y$ 表示 $x$ 的儿子),

$up_{x,i} \leftarrow up_{y,i}\\ up_{x,a_x} \leftarrow 1+\max_{i=1}^{a_x-1}{up_{y,i}}\\ down_{x,i} \leftarrow down_{y,i}\\ down_{x,a_x} \leftarrow 1+\max_{i=a_x+1}^{tot}{down_{y,i}}$

而答案不仅需要和 $up,down$ 取 $\max$ , 而且需要当 $x$ 新合进一个子树 $y$ 时更新,

$ans \leftarrow \max_{i<j}\{up_{x,i}+down_{y,j},up_{y,i}+down_{x,j}\}$

可以做到 $\mathcal{O}(n^2)$ .

考虑优化, 每个节点使用线段树, 每个叶子节点维护对应的 $up,down$ . 而转移可以直接通过单点修改区间查询实现, 合并更新答案时则可以线段树合并.

时间复杂度 $\mathcal{O}(n\log{n})$ .

$\text{[CF407E]k-d-sequence}$

$\color{blue}{\text{[NORMAL]}}$

特判掉 $d=0$ 的情况, 找最长相同数字区间.

对于一个等差数列, 它有两个很显然的性质.

所有的数 $\bmod d$ 的结果相等
区间内没有重复的数

那么我们可以将区间分成若干个 $x \bmod d$ 都一样的区间.

对于一个 $x \bmod d = c$ 的数列, 我们可以将 $x$ 变成 $\dfrac{x-c}{d}$ .

转化完之后, 问题就变成了加入 $k$ 个数, 使区间排序后公差是 $1$ .

对于一个区间 $[l,r]$ 可以算出最少需要加多少个数使得区间是等差数列, $\max\limits_{i=l}^{r}{a_i}-\min\limits_{i=l}^{r}{a_i}+1-(r-l+1)$ .

而且区间内不能有相同的数.

那么从小到大枚举 $r$ , 那么问题就变成求出最小的 $l$ , 使得 $[l,r]$ 无重复, 且加的数不能超过 $k$ .

对于第一个限制条件, 记录一下每个数上一次出现的位置, 与当前区间左端点取 $\max$ 即可.

对于第二个限制, 我们转化一下式子 $\max\limits_{i=l}^{r}{a_i}-\min\limits_{i=l}^{r}{a_i}+l \leqslant k+r$ .

用线段树维护 $val_l = \max\limits_{i=l}^{r}{a_i}-\min\limits_{i=l}^{r}+l$ , 对于每个 $r$ 在区间内线段树上二分查找最左端的位置使得 $val_l \leqslant k+r$ .

至于怎么维护 $val$ , 用单调栈加线段树维护即可.

$\text{[GYM102268J]Jealous Split}$

$\color{red}{\text{[HARD]}}$

我也不知道这人脑袋咋长的, 咋就能想出这么厉害的题呢.

可以证明不存在无解, 且使得 $\sum{s_i^2}$ 最小的方案一定合法.

用反证法, 假设不合法, 则存在相邻两段 $(s_1,m_1),(s_2,m_2)$ 使得 $s_1 > s_2+\max\{m_1,m_2\}$ .

将分割点向右移动一步, 能使得 $s_1^2+s_2^2$ 严格变小, 矛盾.

新的问题可以 $wqs$ 二分, 在 $\mathcal{O}(n\log 10^{20})$ 的时间内完成.

特别还被这教育到了一点, 正常的 $wqs$ 二分不能处理三点共线时还要输出方案.

所以我们得记录每个转移点的最大分割段数, 和最小分割段数, 然后再贪心.

这个 $\text{Part}$ 用了很久的时间, 中间发生了很多事, 但最终还是完结了, 希望以后不再这么拖拉了, 以后会多以 $AtCoder$ 的题为主, $Codeforces$ 的题随缘做吧.