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 看能不能走。简单版就解决了，困难版的话显然一个节点不能走时留下让我不能走的那个朋友即可，于是解法为碰到一个不能走的就将答案加一。
用到的技巧：无（手玩技巧？）。
我想到了的：都想到了。
我没想到的：无。
20220529
ABC253G Swap Many Times (\(\color{#c0c000}{2051}\)) | Record（限时 70.2 分钟）
简要题意：有一个排列 \(A=[1,2,\cdots,n]\)，和操作序列 \((1,2),(1,3),\cdots,(1,n),(2,3),\cdots,(2,n),\cdots,(n-1,n)\)，取出操作序列中第 \(l\sim r\) 对数 \((x,y)\)，交换 \(A_x\) 和 \(A_y\)，求结果。
思路：操作序列开头和结尾有 \(\mathcal O(n)\) 的零散部分，可以暴力，剩下的是完整的 \((i,i+1),\cdots,(i,n)\)，找规律发现就是翻转两段区间。
用到的技巧：找规律。
我想到了的：都想到了。
我没想到的：无。
CF213C Relay Race (\(\color{#aa00aa}{2000}\)) | Record（限时 40 分钟）
简要题意：求两条从 \((1,1)\) 到 \((n,n)\) 的只向右向下走的路径，求被经过的位置的权值和（重复经过算一次）。
思路：跟 P1006 [NOIP2008 提高组] 传纸条 相同，考虑设 \({dp}_{i,j,k,l}\) 为第一条路径到 \((i,j)\) 第二条路径到 \((k,l)\) 的答案，不过这题数据较大空间开不下，于是压一维改成 \({dp}_{i,j,k}\) 表示路经长为 \(i\) 第一条的横坐标为 \(j\) 第二条的横坐标为 \(k\) 的答案。
用到的技巧：动态规划，压维。
我想到了的：都想到了。
我没想到的：无。
20220627
CF1494E A-Z Graph (\(\color{#ff0000}{2400}\)) | Record（限时 100 分钟）
简要题意：三个操作，加 \(u\stackrel{c}{\to}v\) 有向边，删 \(u\stackrel{*}{\to}v\) 有向边，不会重边，问是否存在一条经过 \(k\) 个点的路径，使得反过来也能走，并且正反走边上的字母连起来一样。
思路：是个很久以前打过的 Edu Round，可惜当时太菜了只做出了 AB。考虑在两个点 \(u,v\) 中间反复横跳，发现 \(2\nmid k\) 可行当且仅当 \(u\stackrel{*}{\to}v\) 和 \(v\stackrel{*}{\to}u\) 都存在，\(2\mid k\) 可行在前面条件成立的基础上还要求这两条边上的字母相同，于是随便维护一下就完事了。
用到的技巧：构造。
我想到了的：都想到了。
我没想到的：无。
CF846E Chemistry in Berland (\(\color{#ff0000}2\color{#ff8c00}{300}\)) | Record（限时 80 分钟）
简要题意：有一棵树，每个节点初始的数是 \(b_i\)，需要使它 \(\ge a_i\)。每一对父子关系有一个数 \(k_i\)，可以使父亲减少 \(k_i\) 并使儿子增加 \(1\)，或者使儿子减少 \(1\) 并使父亲增加 \(1\)，可以操作多次，问是否可以使所有节点的数符合条件。
思路：设 \({dp}_u\) 表示 \(u\) 子树内除了 \(u\) 都符合条件时，\(u\) 最大是多少，容易写出转移方程。但是会爆 long long，可以使用 long double（大的时候精度误差不重要）或者设置阈值来解决这个问题。
用到的技巧：无。
我想到了的：都想到了。
我没想到的：无。
20220702
CF1634D Finding Zero (\(\color{#aa00aa}{2000}\)) | Record（限时 40 分钟）
简要题意：交互题，一个非负整数数组 \(a\) 里有且仅有一个 \(0\)，每次可以询问三个元素的极差，找到 \(0\)，输出两个位置有一个正确即可。
思路：由于数组整个取反极差不变，输出两个位置一个是最大值一个是最小值。可以先询问前四个数 \(4\) 次，找到四个中的最大值和最小值位置 \(x,y\)，以及另一个位置 \(z\)。接着对于 \(5\sim n\)，询问 \((x,z,i)(y,z,i)\) 来判断 \(i\) 与 \(x,y\) 的大小关系并维护。
用到的技巧：构造。
我想到了的：先问前四个数再问其他。
我没想到的：问其他过程中具体问的方法想错了。
标签：le,限时,记录,color,difficulty,textrm,Record From： https://www.cnblogs.com/yinhy09-OI-blog/p/16629092.html