CF \(\color{#aa00aa}{1900}\sim\color{#ff0000}{2400}\) | AT \(\color{#0000ff}{1600}\sim\color{#c0c000}{2399}\) 做题笔记

前言

准备多刷些这个分数段的 CF/AT 以涨知识，提高水平顺便提高 rating。

本博客主要收录上面 rating 段的题目，但是如果见到该 rating 段以外的妙妙题，或者由于 Easy Version 和 Hard Version 等原因，也可能收录其他难度的题目。

AT 跨度这么大是因为只能方便地按颜色筛选题目难度。

策略是限时想题，如果想不出来就看题解，看看自己到底啥地方不知道。

限时的时间暂定如下方法计算：（单位是分钟）

\[\begin{aligned} \operatorname{TLCF}(\textrm{difficulty})&= \begin{cases} 10,&800\le\textrm{difficulty}\le 1300\\ 15,&1400\le\textrm{difficulty}\le 1500\\ 20,&1600\le\textrm{difficulty}\le 1700\\ 20+0.1\times(\textrm{difficulty}-1800),&1800\le\textrm{difficulty}\le 2200\\ 60+0.2\times(\textrm{difficulty}-2200),&2300\le\textrm{difficulty}\le 2500\\ 120+0.15\times(\textrm{difficulty}-2500),&2600\le\textrm{difficulty}\le 2700\\ 150,&2800\le\textrm{difficulty}\le 3500\\ \end{cases}\\ \operatorname{TLAT}(\textrm{difficulty})&= \begin{cases} 10,&0\le\textrm{difficulty} < 1200\\ 15,&1200\le\textrm{difficulty} < 1400\\ 20,&1400\le\textrm{difficulty} < 1600\\ 20+0.1\times(\textrm{difficulty}-1600),&1600\le\textrm{difficulty} < 2000\\ 60+0.2\times(\textrm{difficulty}-2000),&2000\le\textrm{difficulty} < 2200\\ 100+0.15\times(\textrm{difficulty}-2200),&2200\le\textrm{difficulty} < 2400\\ 150,&2400\le\textrm{difficulty}\\ \end{cases}\\ \end{aligned} \]

函数的设计思路是：太水的题一眼就切了，时间给相同贴下限就好；太毒瘤的题咋想都不会，时间给相同贴上限就好；中间的想题时间给一定坡度。

20220522

CF1624G MinOr Tree (\(\color{#aa00aa}{1900}\)) | Record（限时 30 分钟）

简要题意：给一个图，求一个生成树使得边权按位或最小。

思路：由于 \(2^k > \sum\limits_{i=0}^{k-1}2^i\)，所以按位从大往小贪，能取 \(0\) 就取 \(0\)，并查集维护一下。

用到的技巧：按位贪心。

我想到了的：都想到了。

我没想到的：无。

CF1421D Hexagons (\(\color{#aa00aa}{1900}\)) | Record（限时 30 分钟）

简要题意：六边形网格，向右走横坐标加一，向左上走纵坐标加一，向右上走横纵坐标都加一。向每个方向走有不同的代价，求 \((0,0)\to(x,y)\) 最小代价。

思路：大分讨，屑题。

用到的技巧：无。

我想到了的：都想到了。

我没想到的：无。

CF1616D Keep the Average High (\(\color{#aa00aa}{2000}\)) | Record（限时 40 分钟）

简要题意：给定序列 \(a_{1\cdots n}\) 和正整数 \(x\)，选出最多的数，使得对于所有 \(l < r\) 都有，要么区间内有数未被选择，要么区间平均数不小于 \(x\)。

思路：先把每个数减 \(x\) 转化成区间和不小于 \(0\)，然后考虑裴蜀定理，只要长度为 \(2,3\) 的子串都满足条件，则所有被选中子串都符合条件。于是问题转化为一个简单的贪心或 DP。

用到的技巧：平均数通过全局减少转化为和与 \(0\) 的比较，裴蜀定理。

我想到了的：全局减 \(x\)。

我没想到的：裴蜀定理，转化为长度为 \(2,3\) 的问题。

CF576C Points on Plane (\(\color{#ff8c00}{2100}\)) | Record（限时 50 分钟）

简要题意：给定 \(n\) 个点 \((x_i,y_i)\)（范围均为 \(10^6\)），重新排列它们使得 \(\sum\limits_{i=2}^n|x_i-x_{i-1}|+|y_i-y_{i-1}|\le 2.5\times 10^9\)。

思路：发现这跟莫队移动指针很像，于是按莫队的询问排序方法排一下即可，注意需要奇偶块优化。

用到的技巧：莫队奇偶块。

我想到了的：都想到了。

我没想到的：无。

20220523

CF1674G Remove Directed Edges (\(\color{#aa00aa}{2000}\)) | Record（限时 40 分钟）

简要题意：给一个有向图，删除若干条边，要求每个点的入度和出度要么为零，要么减少。求删完边后最大的点集大小，使得点集中任意两个点 \((u,v)\) 都能从 \(u\) 走到 \(v\)，或者从 \(v\) 走到 \(u\)。

思路：先把所求转化为最长的简单链，考虑转移 \(u\to v\) 的必要条件是 \({in}_v > 1\) 且 \({out}_u > 1\)，可以拓扑排序进行 DAG DP。

用到的技巧：拓扑排序 DAG DP。

我想到了的：都想到了。

我没想到的：无。

CF253D Table with Letters - 2 (\(\color{#aa00aa}{2000}\)) | Record（限时 40 分钟）

简要题意：给定一个字符方阵，求有多少个长宽均大于一的子矩形满足四个角字母相同且矩形内 a 的个数不超过 \(k\)。

思路：Link。

用到的技巧：双指针、二维前缀和。

我想到了的：都想到了。

我没想到的：无。但是实现的时候思路有点乱调了好久。

20220525

CF1611E1 Escape The Maze (easy version) (\(\color{#0000ff}{1700}\)) | Record（限时 20 分钟）

CF1611E2 Escape The Maze (hard version) (\(\color{#aa00aa}{1900}\)) | Record（限时 30 分钟）

简要题意：一棵根为 \(1\) 的树，我在 \(1\)，我有 \(k\) 个朋友在不同的节点。每次我和每个朋友都走一步，我走到非根的叶子就赢，但是如果在边上或点上碰到一个朋友就输。简单版问我是否必胜，困难版问至少留下几个朋友能使我必败。

思路：发现朋友一直向根走肯定最优，于是第一遍 dfs 处理每个节点第一次被一个朋友走到的时间戳，第二遍 dfs 看能不能走。简单版就解决了，困难版的话显然一个节点不能走时留下让我不能走的那个朋友即可，于是解法为碰到一个不能走的就将答案加一。

用到的技巧：无（手玩技巧？）。

我想到了的：都想到了。

我没想到的：无。