CF能力提升计划-D

一些我不会做的 CF C,D,E 题以及其他难度相当的思维题，记录在这里。总结大致思维方式，以提升自己的实力。 *** [CF1905D Cyclic MEX](https://www.luogu.com.cn/problem/CF1905D) $1$：移位操作会有大量**重复数据**，考虑每次移位维护**变化值**。 $2$：由于无法直接维护总和，考虑维护每一个**前缀**的 mex 值，并考虑移位后的**影响**。 $3$：找到基本思路之后，使用数据结构，**维护区间双端队列**，优化至 $O(n)$。 [CF1916D Mathematical Problem](https://www.luogu.com.cn/problem/CF1916D) $1$：使用程序枚举小数据**找到规律**，以此来推算出更通用的规律。 $2$：找到规律后，使用完全平方公式进行**证明**。 $3$：利用找到的规律进行**构造**，并计算个数验证规律是否适用。 [CF1918E ace5 and Task Order](https://www.luogu.com.cn/problem/solution/CF1918E) $1$：**分析**可以提供的询问，发现可以确定数列中一些数的**相对大小**。 $2$：考虑使用**排序**算法，将每一个**位置**按照相对大小进行排序。 $3$：考虑使用类似**归并排序**的思想，每次把序列分为两部分，**逐层合并**。 $4$：由于明确知道一个值**不现实**，考虑**随机化**一个数作为序列的划分标准。递归实现即可。 [P10143 [WC2024] 代码堵塞](https://www.luogu.com.cn/problem/solution/P10143) $1$：枚举方案显然不可行，考虑计算**每个元素**被计算了多少次。 $2$：考虑影响某个元素**提交时间**的**因素**，并**分析其性质**。 $3$：根据这些因素的性质，确定方法为**分类讨论**和**计数 dp**。 [CF1928E Modular Sequence](https://www.luogu.com.cn/problem/CF1928E) $1$：考虑最终答案的**组成形式**，相当于分析最终答案的**性质**。 $2$：根据数据范围，确定**枚举**部分和**预处理**部分。 $3$：确定**动态规划**的处理方式，并记录**前驱**用于输出方案。 [CF1923D Slimes](https://www.luogu.com.cn/problem/CF1923D) $1$：分析**可合并区间**的性质，并发现可以通过**前缀和**快速判断可合并区间。 $2$：每个史莱姆可以被**左边**或**右边**的史莱姆合并，按照左边或右边分类讨论。 $3$：分类讨论之后，发现可合并区间具有**单调性**，**二分**即可。 [CF1943B Non-Palindromic Substring](https://www.luogu.com.cn/problem/CF1943B) $1$：直接维护显然不可能，**正难则反**。 $2$：分析 $k$ 为不同取值是**不是** k-good 的**性质**，**分类讨论**。 $3$：考虑使用 **Manacher** 和**前缀和**进行预处理，优化复杂度。 [CF1946D Birthday Gift](https://www.luogu.com.cn/problem/CF1946D) $1$：题目涉及位运算，考虑**拆位**分析。 $2$：对于每一位，分析这一位最终的**结果**的**性质**，进行**分类讨论**。 $3$：发现**高位**对**低位**有影响，确定处理**顺序**。 $4$：**无法处理**相等的情况，于是将 $x$ 加 $1$。 [CF1967B2 Reverse Card (Hard Version)](https://www.luogu.com.cn/problem/CF1967B2) $1$：利用 $\gcd$ 的**性质**，**简化**式子为 $(x+y)\mid ky(xk=a,yk=b,\gcd(x,y)=1)$。 $2$：利用整除的**性质**以及**放缩法**，分析出 $x,y$ 的**上界**。 $3$：利用上界较小，**枚举**互质的 $x,y$，并利用**式子**直接计算出可以取的 $\gcd$ 值。 [CF1981C Turtle and an Incomplete Sequence](https://www.luogu.com.cn/problem/CF1981C) $1$：每两个数以及前后缀**单独处理**，把序列分成几个**子问题**。 $2$：通过变化方式进行**构造**，联想到**二叉树**儿子节点的存储方式。 $3$：将最优构造方式转化为二叉树上的 **LCA**，并通过判断**奇偶性**确定是否有解。 [P10465 双端队列](https://www.luogu.com.cn/problem/P10465) $1$：考虑常规处理方式无法处理**重复元素**，分析**目标**的性质。 $2$：**排序**，将题目转化为序列**分段**问题。 $3$：分析**每一段**的**性质**，发现**单谷**性质。贪心，用变量维护**递增**或**递减**，以及上一次的元素。 $4$：考虑将相同元素**合成一段**，记录**最大值**与**最小值**。判断与上一次元素大小关系决定**递增**或**递减**排列。 [CF1978E Computing Machine](https://www.luogu.com.cn/problem/CF1978E) $1$：考虑**特殊情况**，发现进行操作可以使用**贪心算法**。 $2$：考虑能够影响答案的**取值**，发现操作的影响**不具有**传递性， $3$：考虑暴力求出**较小情况**与**边界情况**，中间不受影响的部分通过**前缀和**求出。 [CF1989E Distance to Different](https://www.luogu.com.cn/problem/CF1989E) $1$：分析**答案**的性质，发现 $b$ 数组与 $a$ 数组中元素的具体值**无关**。 $2$：考虑到答案与元素的**不等关系**有关，**构造**数组 $c_i=[a_i\ne a_{i-1}]$ 来反映不等关系。 $3$：分析**特殊情况**，通过特殊构造将 $b$ 数组与 $c$ 数组建立**双射**。 $4$：**动态规划**求出满足条件的 $c$ 数组构造，即可得出 $b$ 数组的构造。 [P3586 [POI2015] LOG](https://www.luogu.com.cn/problem/P3586) $1$：原操作难以快速维护，考虑转化为其**充分必要条件**。 $2$：以题目中的**是否查询**为突破口，**只需要**操作 $s$ 次，**去除** $a_i\gt s$ 的情况。 $3$：分析**答案性质**并**手玩样例**，不难发现结论。利用**建模法**或**数学归纳法**进行证明。 $4$：利用**数据结构**快速维护解决问题。 [AT_agc006_d [AGC006D] Median Pyramid Hard](https://www.luogu.com.cn/problem/AT_agc006_d) $1$：考虑中位数经典转化，**二分答案**并对大于、小于二分中值的答案进行**标记**($1$ 或 $0$)。 $2$：分析**答案**的**性质**，发现连续的 $1$ 或 $0$ 具有**稳定性**。 $3$：得出稳定性后，发现不稳定的 $1$ 和 $0$ 会**发生变化**，原本稳定的 $1$ 和 $0$ **忽略限制**依旧保持稳定。 $4$：问题转化为中心的数**先**转化为哪一个**稳定**的数，十分容易判断。 [CF1997E Level Up](https://www.luogu.com.cn/problem/CF1997E) $1$：分析每个**位置**的怪兽的性质，发现对于每个 $x$ ，**是否**与这个怪兽**战斗**具有**单调性**。 $2$：考虑**二分**求出与每一个位置的怪兽战斗的**最小阈值**，通过与阈值比较用于回答询问。 $3$：发现每次二分可以用到**之前**的阈值，需要考虑求值域上**前缀和**，**树状数组**维护即可。 [CF1998C Perform Operations to Maximize Score](https://www.luogu.com.cn/problem/CF1998C) $1$：按照 $b_i$ **分类讨论**，单独分析每一类中的**性质**。 $2$：对于 $b_i=1$，发现全部加到自己**更优**。 $3$：对于 $b_i=0$，发现最优只会选择**最大的数**的位置的分数。 $4$：对于 $b_i=0$，是一个**中位数**问题。采用经典**二分**处理方式，二分中位数，返回比中位数**大**的数的数量，依据这个数量进行二分。 [CF2004E Not a Nim Problem](https://www.luogu.com.cn/problem/CF2004E) $1$：博弈论问题，考虑 **SG 函数**与 **Nim 博弈模型**。 $2$：考虑求出每个数字的 SG 值，通过**打表**发现规律并**数学证明**。 $3$：使用**线性筛**预处理，即可完成统计。 [CF2001D Longest Max Min Subsequence](https://www.luogu.com.cn/problem/CF2001D) $1$：字典序问题，考虑**逐位贪心**，选择**可行**且**字典序最小**的位置。 $2$：分析可行的性质，在**没被选**的数**最后出现**的位置的**最靠前**的点**之前**均可，于是得到了可以选的数的**区间**。 $3$：考虑**数据结构优化**，**线段树**维护区间没被选的数的最大最小值，**`set`** 维护没被选的数最后出现的位置。 [P7961 [NOIP2021] 数列](https://www.luogu.com.cn/problem/P7961) $1$：分析不出来任何性质，**优先考虑**算法。 $2$：考虑计数类**动态规划**。由于进位**从后往前**，确定数位顺序**从低位到高位**。 $3$：考虑**按位构造**数列，并枚举选择**多少个某位置**与目前**处理到的数位**避免算重。 $4$：进位不好处理，利用**升维**处理进位。 [CF2018B Speedbreaker](https://www.luogu.com.cn/problem/CF2018B) $1$：**转化贡献体**，考虑从每个点出发能满足多少时间的要求。 $2$：分析每个时间出发点的**性质**，发现满足要求的出发点构成一个**区间**。 $3$：利用**差分**统计每个点出发能满足多少时间的要求，找到满足所有时间要求的点即可。 [AT_arc084_b [ABC077D] Small Multiple](https://www.luogu.com.cn/problem/AT_arc084_b) $1$：考虑**单独分析**数位和的性质，构造**生成方式**可以生成所有正整数且**容易统计**数位和。 $2$：把整除 $K$ 的限制**加入**生成方式，即需要寻找**模 $K$ 余 $0$** 的数。 $3$：结合上面两步想出**同余最短路**，选择一个不影响答案的位置为源点。 [CF2021C2 Adjust The Presentation (Hard Version)](https://www.luogu.com.cn/problem/CF2021C2) $1$：**分析性质**，转化为**不依赖**外部变量判定的形式，即判定两个序列去重之后是否**相等**。 $2$：发现只需要记录每种元素**第一次**出现的位置，使用 `set` 维护。 $3$：每种元素第一次出现的位置的**顺序**与 $a$ 数组紧密**相关**，考虑 $b$ 数组中的元素按照 $a$ 数组的顺序**映射**。 $4$：映射之后直接维护前后的**大小关系**，判断**邻项**逆序对是否为 $0$ 即可。 [CF58E Expression](https://www.luogu.com.cn/problem/CF58E) $1$：**贪心**考虑，**假设**不添加数，寻找**限制条件**。 $2$：考虑**如何添加**数满足条件，发现只有在**低位**添加数才可以满足限制。 $3$：考虑有**多种**满足条件的方法，使用**搜索**或者**动态规划**。 [CF1743E FTL](https://www.luogu.com.cn/problem/CF1743E) $1$：分析双飞船**同时攻击**的性质，发现会回到**初始情况**。 $2$：每一次飞船攻击有**多种决策**，且伤害值与血量**比较小**，考虑以**减少血量**为维度**动态规划**。 $3$：考虑**答案构成**，必由若干**双飞船攻击周期**组合得到。预处理双飞船攻击周期，直接进行**完全背包**转移。 [CF2031D Penchick and Desert Rabbit](https://codeforces.com/contest/2031/problem/D) $1$：分析每一个**位置**的性质，发现**第 $n$ 个位置**必然能跳到**最高**的树。 $2$：无法对每个位置直接计算答案，可以以第 $n$ 个位置为**初始状态**，尝试从高位往低位**递推**。 $3$：**预处理**前缀最大值和后缀最小值加速递推。 [CF894B Ralph And His Magic Field](https://www.luogu.com.cn/problem/CF894B) $1$：填数具有极大的不确定性，考虑寻找**可以确定**的量。 $2$：发现**一行**中**前 $m-1$ 个数**确定时，第 $m$ 个数**可以确定**。于是考虑使用**最后一行**与**最后一列**确定整个矩阵。 $3$：考虑使用最后一行和最后一列**刻画**整个矩阵，直接**计数**并判断无解。 [CF2049E Broken Queries](https://www.luogu.com.cn/problem/CF2049E) $1$：观察数据范围与限制，考虑**对数复杂度**算法，想到**二分**。 $2$：显然求不出来 $1$ 的位置，**假设**我们知道 $1$ 的**范围**，我们发现只要知道 $1$ 在 **$[1,\frac{n}{2}]$ 或 $[\frac{n}{2}+1,n]$** 就可以二分求出 $k$。 $3$：发现可以通过**再次折半**通过 $[1,\frac{n}{4}]$ 和 $[\frac{n}{4}+1,\frac{n}{2}]$ 返回值是否**相同**来确定 $1$ 是否在 $[1,\frac{n}{2}]$，**分类讨论**一下就做完了。 [CF2056D Unique Median](https://www.luogu.com.cn/problem/CF2056D) $1$：**正难则反**，注意到**值域**很小，**转化贡献体**，考虑**枚举**较小的中位数。 $2$：中位数**判定**问题，考虑**经典技巧**，把小于等于 $x$ 的赋为 $-1$，其余赋为 $1$。 $3$：区间因为较小的中位数导致不好的**充要条件**是赋值后**区间和为 $0$**，**前缀和**加 **`map`** 统计，注意特判没有出现 $x$ 的情况。 [P7514 [省选联考 2021 A/B 卷] 卡牌游戏](https://www.luogu.com.cn/problem/P7514) $1$：翻面对极差的影响**不好处理**，考虑极差的**定义**，我们只需要确定选择的 $a_i$ 和 $b_i$ 的**最大值**和**最小值**。 $2$：注意到最大值和最小值之间的数可以**任意选择**，由此找出最大值和最小值合法的**充要条件**。 $3$：和**大小顺序**有关，把 $a_i$ 和 $b_i$ 拆开，**排序**，发现可以枚举左端点**双指针**。 [CF2092E She knows...](https://www.luogu.com.cn/problem/CF2092E) $1$：直接做很难处理，考虑分析**奇偶性**，直接分析也不行，考虑分析颜色的**变化**对奇偶性的**影响**。 $2$：相邻格子数为**偶数**的格子**改变颜色**时**不会**影响奇偶性，于是只考虑**边上**(除去四个角)的格子就行了。 $3$：边上每一个黑格子**贡献**为**奇数**，如果边上没填满用一个格子即可**调整**，其余格子**随便选**。 [CF2086E Zebra-like Numbers](https://www.luogu.com.cn/problem/CF2086E) $1$：$10^{18}$ 内**只有** $30$ 个 `Zebra-like` 数。 $2$：考虑一个数的**最优表示**，直接**贪心**，通过**反证法**假设**最小的元素**证明贪心策略一定**不劣**。 $3$：**前缀和**差分一下，就是**数位 DP**的经典模型。 [CF2119D Token Removing](https://www.luogu.com.cn/problem/CF2119D) $1$：**无法计算**单独一个序列的贡献，考虑**转化贡献体**处理每种**最终状态**的方案数。 $2$：计数问题通常考虑**更严**的限制，由于被取走的 Token 必须与区间右端点**一一对应**，**从右往左**计算右端点的选法。 $3$：发现枚举时有很多重复信息，考虑使用**动态规划**结算每一种方案的**贡献和**。 [CF2120D Matrix game](https://www.luogu.com.cn/problem/CF2120D) $1$：是经典的**鸽笼原理**问题，直接利用鸽笼原理算出 $n$ 的**下界**。 $2$：问题相似，分析 $m$ 的**下界**，通过不出现可以同时在答案矩阵中列的**最大**列数 $x$ **转化**到鸽笼原理的问题。 $3$：分析 $x$ 的**上界**并证明可以取到。 *** [CF能力提升计划-E](https://www.luogu.com.cn/training/745272)