CF2000~2500选做

先能够熟练的切掉一些基本题,然后再慢慢的往上提水平.

每一道题都需要自己写过!! 不要口胡解法就不写了!!

每一道题初始给自己 20min 的时间,20min 一点头绪都没有就看题解,有头绪再给 30min,30min后没写出来就看题解.

必须要写过! 锻炼码力!! 尽量看完题解自己写.

写完之后你有 10 min 的时间再这篇博客上记录,不需要写太多复制题解也是可以的,重点是记录了你写过这道题.

如果遇到了自己没有学过的知识点,也一并记录,也要写 并使用六级标题标注.

每连续独立出写5道题目,区间向上移100分,如果连续写不出5道题目,向下降100分.

题目顺序乱序排列

2025.3.17

CF1174F

我们看到 $36 = 2\text{log}_2(2\times10^5)$ 想到需要使用带 log 的想法,最naive的想法就是每走一步就直接查下一步,肯定不优.

我们想到只有一个儿子可以优化,但经过尝试后依旧会寄.

我们发现树链剖分是log 的,并且会发现有一个性质:

于是考虑树链剖分,发现我们只需要每一次都沿着重链跳到与猜测节点深度相同的位置,就可以求出它们的LCA,进而再用一次S操作即可递归,每一组操作相当于跳过一个轻边.因此是 log 的.

实现上的细节就是在设置重儿子是判断一下深度是否够,不够就不用,这样在找的时候就会方便很多.

难度:⭐⭐⭐⭐

2025.3.18

CF755D 🆗

简单题,我们发现实际上块增加的个数就是与线交点的个数,我们直接模拟,然后计算新加的线与已经加的线的交点个数即可,这个可以用树状数组实现,在每一个端点上加一,然后区间和,对于跨过 $n$ 的拆开即可.

有几个小细节:一是左右两个端点的线段不计入统计,另一个就是当 $2k>n$ 时要将 $k\larr n-k$ 即可,因为就相当于逆向操作,但是如果直接操作会与不能交的线相交.

难度: ⭐ 一颗星给细节

CF337D

唉唉,2000的DP都做不出来.

我们果断考虑DP,我们设DP代表的时到这个点最远的关键点的距离,这样我们统计答案时就直接统计小于 $d$ 节点个数即可.那我们考虑如何进行DP.

在子树内的DP是容易的,我们考虑如何子树外的,对于根,答案就是它本身,那么其他的我们就可以换根求出

剩下的就是套路的换根DP了,发现求最大值,记录次大值即可.

死因:懒(自己在写的时候懒得记录次大值写了一大坨)

难度: ⭐⭐⭐⭐ (因为DP不好)

CF1665D

那很唐了,我们看到 $\gcd(x+a,x+b)$ 应当是能想到辗转相减法的: $\gcd(x+a,a-b)$ 这样我们就可以发现我们就可以控制最大公约数了.

看到每个数最多尝试30次,我们考虑试出那个数二进制下的每一位,具体就是从第一位开始试起,每一个 $a$ 先减去已经有的答案 再加上二的位数倍,$b$ 设置成 $a$ 的高一位加一 ,如果我们发现得到的GCD是当前的倍数就统计进答案,否则就不统计.

难度:⭐⭐ (是自己太唐了)

2025.3.19

在整数学和学生会,没写题

2025.3.20

在整数学和学生会,没写题

2025.3.21

CF1042F

一开始是没有头绪的,但是这种类型的题很容易就想到DP,我们需要记录所有的儿子然后我们发现,我们好像只需要记录深度没有超过 $k$ 的最深的一个儿子,因为比它小的可以推到后面合并,比它大的在子树时就应该合并了.

于是我们发现这不是DP,而是一个贪心,我们每次将最大的看看能否合并,如果能合并就合并取较深的那个,如果合起长度大于$k$ 答案就加一(不用管小的,因为大的进入答案的时候会把所有小的清掉).

难度:⭐⭐⭐⭐*　还是比较神奇的.

CF1423J

我们通过给出的集合可以猜到,题目应该跟八进制数有关,但是题目中给出的是二进制数的形式:

$x_0{2^0}+x_1{2^1}+x_2{2^2}+x_32^3+⋯=m (0\leq x_i\leq7)$

我们把它分组:

$m=(x_08^0+x_38^1+x_68^2+\cdots)+2(x_18^0+x_48^1+x_78^2+\cdots)+4(x_28^0+x_58^1+x_88^2+\cdots)$

那么我们实际上就应该求的是:

$a+2b+4c=m$

非负整数解的个数,

对于 $a+2b=m$ 的非负整数解的个数为 $\left \lfloor\frac{m}{2}\right\rfloor+1$ 其实就是枚举 $b$ 都会有一个 $a$ 相对应.

那么我们就有所求式子的解的个数为 $\sum \limits_{c=0}^{\lfloor\frac{m}{4}\rfloor} (\lfloor\frac{m-4c}{2}\rfloor+1)$

$$\begin{align*}\sum \limits_{c=0}^{\lfloor\frac{m}{4}\rfloor} (\lfloor\frac{m-4c}{2}\rfloor+1) &=\sum \limits_{c=0}^{\lfloor\frac{m}{4}\rfloor} (\lfloor\frac{m}{2}\rfloor-2c+1)\\ &=(\lfloor\frac{m}{4}\rfloor+1)(1+\lfloor\frac{m}{2}\rfloor)-2\sum \limits_{c=0}^{\lfloor\frac{m}{4}\rfloor}c\\&=(\lfloor\frac{m}{4}\rfloor+1)(1+\lfloor\frac{m}{2}\rfloor)-(\lfloor\frac{m}{4}\rfloor+1)(\lfloor\frac{m}{4}\rfloor)\\&=(\lfloor\frac{m}{4}\rfloor+1)(1+\lfloor\frac{m}{2}\rfloor-\lfloor\frac{m}{4}\rfloor)\end{align*}$$

于是这道题就做完了.

难度:⭐⭐⭐⭐⭐ 神奇题目(话说这题数学竞赛生是不是能做得更快)

2025.3.24

CF248C🆗

先将球变成一个点(就是将点其余的点向外扩一圈),然后把球门给对称过去,这样我们只需要求出球门一端到球门另一端与开始点的连线的距离,这样的话就可以判断无解.后面再求出与墙的交点即可.

难度:⭐ 计算几何不好写.

CF154C🆗

想到是哈希就不难了,我们可以仿照"星战"的方法,为每一个点附上随机权值,一个点的总权值是它连边的节点权值和,然后判断权值和相等的有多少个,注意需要特别枚举有连边的两个点,因为他们要互相减去对方点的权值.

写的双哈希,单哈希被卡了

难度:⭐⭐⭐ 初见难想,写过就是套路(一个⭐给单哈希被卡)

2025.3.25

CF1605E🆗

这种思路,很少见啊.

我们可以发现从 $1 \cdots n$ 的方法一个一个置成 $b_i$ 是最优的,那么我们就可以先把式子列出来:

$$s_i=c_i-\sum\limits_{d|i}s_d$$

其中 $c_i$ 为 $a_i-b_i$ ,$s_i$ 为把 $a_i$ 改成 $b_i$ 所需要修改的量(有正负),答案就是 $\sum\limits^n_i|s_i|$.

我们可以把这个式子拆开,然后发现如果一个点的值与 $s_1$ 有关,那么它的 $\mu(i)$ 一定不为零,并且它的 $s_1$ 的系数为 $-\mu(i)$

这样我们就可以将与 $s_1$ 无关的答案先统计出来,然后按照 $s_i$ 中 $s_1$ 的系数分成两类,一类是负,一类是正,统计答案就是先把 $s_1=c_1$ 求出来,然后我们二分统计出答案,注意还要加上 $|s_1|$ .

柿子 : $ans \leftarrow ans-(n-t+1)\times s_1 +sum_n+(t-1)\times s_1 -2sum_{t-1}$ 这是第一类的柿子,第二类将 $s_1$ 取反即可.其中 $sum_i$ 为这一类的前缀和.

难度:⭐⭐⭐⭐ 神奇

CF1614D1🆗

看见了最大公约数,还提示了值域很小,不妨考虑将标记数组整出来,我们设 $f_i$ 代表以 $i$ 为最大公约数的个数, $v_i$ 代表 $i$ 的个数,那么我们就可以写出关于 $f$ 的转移,然后我们一开始考虑设 $dp_i$ 为填了 $i$ 个数的答案,发现不行,会统计多,于是我们可以换一下,因为我们明白,最后的答案的最大公约数是所有数的最大公约数,于是我们考虑设 $dp_i$ 代表 $\gcd()=i$ 时的答案即可,注意初始值是 $dp_i=v_i\times i$ 如果从转移来的地方 $f$ 为 $0$ 就跳过.

$dp_i=\max\limits_{i|d,f_d\neq0}\{dp_d+(f_i-f_d)\times i\}$ 细节是需要倒着枚举.

难度:⭐⭐⭐* DP还是难做啊.

2025.3.26

CF1296F🆗

我们先把问题转换一下,题目上要求的是对于每一个给出的路径的最小值要大于给定的一个值,也就是说,我们这个路径上的每一个边的权值都需要大于等于这个给出的值.

那么这道题就不难了,我们标记每一条路径,标记的过程就是更新这条路径上的最大值.但是这样有个问题,就是我们的无解十分难以判断.

我们发现无解实际上就是覆盖的所有边的最大值都大于了给出的值,导致没有相等的值.

因此我们可以按给出的值从大到小进行覆盖,在每一次覆盖的时候判断这条边是否被更新,如果这一次覆盖没有一条边被更新那么我们就判断无解.

难度: ⭐ 没什么难度,主要是细节有点恶心.

level up! 2100~2600

2025.3.27

CF629E

不难想到,我们实际上统计的就是环的总长和个数,对于不是祖孙关系的连个点,统计的结果就是将一个子数中节点到当前节点的路经总和乘上另一个子树的节点个数,然后对于零一个子树同理.最后直接加上两点间的距离+1(因为这些长度存在于每一个环中)

对于有祖孙关系的两个点,我们显然不能用刚才的解法,我们会发现,较靠近根的节点所能选的范围是它祖先以及他们的孩子,所以我们还需要统计出整棵树中每一个节点到这个节点的距离和,再减去当前节点路径上的这一个子树即可.这个可以用第二遍dfs实现.

具体就是求LCA用倍增,求路径上第一个孩子也是,还需要处理出三个数组(子树大小,子树路径和,全体路径和)即可.\

s=1.0*sum[y]/siz[y]+1.0*sum[x]/siz[x]+(d+1)

1.0*(suf[y]-sum[t]-siz[t])/(siz[1]-siz[t])+1.0*sum[x]/siz[x]+(d+1)

贴一下公式

难度:⭐⭐ 没难度,没写出来是因为细节(还有自己懒得写第二遍dfs)

2025.3.28

CF884D

怎么会,这么弟弟.

一开始被2300得数据结构吓到了,没反应过来,只需要想到正难则反,就能够知道用priority_queue维护最小值每一次合并即可.

但是有一个问题,一次合并三个会导致后面有问题,我们发现需要用合并两个的时候就是 $n$ 为偶数得时候,因此我们直接在偶数的时候先合并一次两个的就行了.

难度:⭐⭐ (tang)就不会要降级了吧

###　CF177D

神仙分治题．

我们发现我们所求的实际上是一个子矩阵,我们似乎可以考虑先容斥,把它转成从原点开始的一个矩形.

我们看到这个柿子给出来的十分像快速傅里叶变换的过程，因此我们可以考虑分治．（但是不要想位逆序优化）.当然,从矩阵和进而想到分治也是十分自然的.(?

我们设出我么在分支过程中所需要的内容:下标限制,数值限制,分治左右端点.

我们进而发现,每一次进行的分治实际上是将一个等差数列分成了两个等差数列,公差翻倍,一个首项不变,另一个首项错开.

那么我们还需要再分治之中再加上当前的等差数列长度,首项与公差.

然后我们分治就是如果下标限制大于中点,我们直接递归右区间,加上左区间答案,否则递归左区间.

左区间答案就是等差数列求和.

难度:⭐⭐⭐⭐* 神奇

2025.3.31

CF1271D 🆗

艹,遇到做过的题了.

其实思路很简单,就是我们发现一个节点被占领的时间能推就推,不能退再看能不能占领,然后这道题的数据范围很小,我们能够猜到使用背包,那么此时这道题我们就已经做完了.

难度:⭐⭐ 还好

2025.4.3

CF1257G

FFT/NTT

没错,中间隔了3天,至于干什么去了,这道题会说.

我们可以想到,当所有的质数都不同的时候,我们选择正好一半的方案数肯定是最多的,那么我们猜测(可以试一试)对于有相同的质数也是一样的.答案显然是肯定的.Sperner定理但是我们发现多重集内部的个数是会重复的.

接下来考虑怎么求这个东西,可能能想到生成函数,那么这道题就简单多了,统计出每种质因子个数,然后构造 $f_k(x)=\sum\limits_{i=0}^{cnt_k} x^i$ 对这个东西NTT即可.

没错,就是NTT学了整整三天.

难度:?? 不好评,没学过.

2025.4.8

摸鱼爽

CF1326E

没做出来,神奇题目

我们想一个值什么时候能够在队列中活着当且仅当它走到当前位置还没有被炸掉,而且后面炸弹的个数比后面大于这个数的个数少.

然后我们有注意到,对于答案肯定是单调不减的因为多一个炸弹肯定多一次删除最大值的机会,会在上一个炸弹之后多炸一个.

于是我们就可以炸弹的顺序来做,同时维护一个答案(初始等于 $n$ ),于是我们用线段树维护这个数后面比它大的数的个数和当前炸弹个数下这个位置之后的炸弹个数.只要炸弹个数大于比它大的数的个数,那么答案就减一,否则输出答案.

有一个技巧,就是我们可以维护区间加和整体最大值的线段树,对于一个炸弹,当前位置前缀减一,对于一个数,前缀加一,然后数字不提前加,直接更到哪个答案就加那个数,那么我们只需要判断全局最大值是否小于零即可.

难度:⭐⭐⭐⭐ 💣(这题2200?)

CF788E

糖丸了,糖丸了.

很显然是DP,(但是想了好一段时间的贪心),对于题目给出的条件,我们可以做一个前缀和,那么我们可以试图做出前缀和,那么前缀和做差大于零就代表这段区间和为正,那我们应该能设计出DP:

$$dp_i=\max(\max\limits_{j=0,s_i-s_j\geq0}^{i-1}\{dp_j+i-j\},dp_{i-1})$$

(至于为什么是 $i-j$ 而不是 $i-j+1$ 因为我们判断的条件是 $s_i-s_j\geq0$ 而对应区间是 $[j+1,i]$ 相当于将 $j$ 平移了一位)

这是 $O(n^2)$ 的,考虑优化.我们将 $dp_j-j$ 分成一组,那么我们实际上是要求所有小于 $s_i$ 的位置的 $dp_j-j$ 的最大值,直接上权值线段树即可.

难度:⭐⭐⭐ 这题比上一道题像 2200

CF2068C

码力有待提高.

显然的,我们可以想到每一次最好要用两个数凑出 $k-1$ 这样我们就可以顺带带走一个最大值.

于是我们就能想到将数组排序后直接"三指针"维护即可(一个维护最小值,一个维护相加得 $k-1$的值,另一个维护最大值)

但是不会写了😓.看了题解以后发现是直接用一个标记数组,外加判断下标之间的大小关系,能少掉很多的分类讨论.

难度:⭐⭐ 唐

CF1032E🆗

好险,差点就掉级了.sol

难度:⭐⭐ 2100怎么紫?

2025.4.11

这个月做题少很多了啊.

CF567F

我们应该能很快发现这个是DP,然后考虑如何DP.

于是我们根据这个trick,就可以考虑按照数字进行枚举添加,又因为题目要求的是一个单峰函数,因此,我们能写出DP:

$dp_{i,j}$ 代表剩下 $[i,j]$ 没填是的方案数,.转移就是从小到大一个一个数进行枚举,只有两个都放左边,两个都放右边,左右各一个三种情况,直接转移即可.对于额外的条件,因为我们发现所有比当前数小的数是我们已经填过的位置的数,比当前数大的数是我们没填过的数.因此我们就有判断的方法了.

难度:⭐⭐⭐⭐

CF746F🆗

没什么难度,我们能够想到贪心的取每一次最大的几个打折,然后用双指针维护区间,我们还能够想到,我们可以使用两个multiset直接维护区间内的打折和没打折的音乐,删除打折区的音乐后从没打折的里面挑选一个最大的加到打折区中.

每一次操作完以后更新答案即可.

难度:⭐⭐ 这题评紫的原因估计是那时候没有STL(大雾

2025.4.13

CF1252F

树哈希

很明显的树哈希板子题,直接枚举断点,然后哈希即可,但是注意把树分开之后,子树的形态可以变化.

难度:⭐⭐

2025.4.17

又在摸鱼了

CF756D

神奇DP,我们发现,最终的序列的样子很好,实际上就应该是原串中的一个子序列(没有相邻字符相同),然后经过一个一个字符复制出来得到的.

我们考虑对选出来的最终序列进行DP,(这个转换思路应该会比较常见),我们会发现,对于一个合法子序列,设它的长度为 $k$ 则这个子序列会对答案贡献 $\dbinom{n-1}{k-1}$ 个不同的答案.那么我们只需要统计本质不同子序列个数即可,设$dp_{i,j}$ 代表子序列长度为 $i$ 且最后一个字符为 $s_j$ 时的本质不同子序列个数.那么我们很快就能够推出转移.

但是这种转移会有重复,因此我们只需要考虑从前一个与当前字符相同的字符开始即可.可以使用前缀和优化,在每一次行转移结束之后统计一下ans即可.

难度:⭐⭐⭐* 还好,但是自己太懒了.

2025.4.21

今天的首要任务是将之前有一些写过的题目的blog补上

CF787E🆗

我们考虑对于一个区间,这个区间中异或完以后 $=k$ 的数一定是成对出现的,我们可以考虑先将这些对子两两配对,我们会发现这样配是能够配出最多的$=k$ 的组,如果这些还少的话就无解,否则我们考虑将除了已经配完的数以外的数全部都异或到一起,如果异或值为 $0$ 答案存在,否则答案不存在.

因为如果将一个数字分成两个异或和的话,那最终的异或和依旧不变,因此两两配对是可行的.

难度:⭐⭐

CF601B🆗

我们发现给出的这个柿子像是斜率的柿子 ,也就是区间内两个点的斜率的最大值,而我们知道斜率的最大值是在相邻的时候取到,具体是为什么,因为如果跳过一个点,那么与被跳过的点连线中一定会有一条斜率大于当前这条线.

因此我们发现这个就是统计每一个子区间中区间最大值的和,我不知道有什么奇技淫巧,所以我就用单调栈记录递减序列,然后对于一个点,在这个点被弹出的时候更新答案即可,注意是经过这个点的区间.

难度:⭐⭐

2025.4.22

CF936C🆗

现在要提速,也要保证质量.

我们会发现,题目要求的 $6100$ 次实际上就是 $3\times n$ 次,也就是对于一位,我们要用三次将它转到正确的位置.

先分析操作,实际上就是将末尾的一段字符串翻转到开头,再继续手玩样例可以发现,这个翻转会使在里面的依旧在里面,靠外的依旧靠外.

我们再来试一试,设 $1,2,3,x,\cdots,4,\cdots$,那么我们这一步的操作是要将 $4$ 挪到 $3$ 的后面.

我们需要分析,什么时候 $4$ 能够接到 $3$ 后面,当且仅当 $3$ 为左端点,$4$ 为翻转区间的开始时用一步可以拼到一起.

那我们知道了我们的首要任务时将 $3$ 从中间挪到左边,我们发现只能先将 $x$ 之后的全部翻转过去,然后再整体反转,这样我们的序列就变成了: $3,2,1,x,\cdots,4,\cdots$ 但是这样把 $4$ 挪过去,我们发现在这段完成的区间两侧有没完成的区间,很烦.一次我们考虑怎么把这些东西搞掉.

我们发现其实并不需要将整体翻转,直接翻转一部分就可以了,也就是从 $\cdots,4,\cdots,x,1,2,3$ 可以只翻转 $4$ 之后的部分,这样就变成了 $3,2,1,x,\cdots,\cdots,4$ 那么再进行一次操作后就变成了 $4,3,2,1,x,\cdots,\cdots$ 非常好看,而且方便我们继续递推.

但是我们只讨论了(已经排好的区域)正向的情况,得到的是反向的 因此我们在考虑一下反向的情况,类比之前的方法不难得到(其中标红的代表翻转的区间):

$$[\color{red}3,2,1,x,\cdots,4,\cdots\color{white}] \rarr [\cdots,4,\color{red}\cdots,x,1,2,3\color{white}] \rarr [3,2,1,x,\cdots,\cdots,\color{red}4\color{white}]\rarr [4,3,2,1,x,\cdots,\cdots]$$

用了三步,并且得到的序列也是反向的,就可以直接进行递推了也就是说根本就出现不了正向的情况,最后再整体反转一下就可以了.

与此同时我们发现,第二部所翻转的数的个数就是 $4$ 在这组操作前在数组的位置,记录一下即可.

我们再看序列中 $\cdots$ 的部分,这一部分可以根据样例手推得到,结果就是操作前 $4$ 前的 $\cdots$ 顺序不变,$4$ 后的 $\cdots$ 顺序相反.直接模拟修改即可.

对于无解,当我们向后找不到要放到这一位的字符时,就无解.

难度:⭐⭐⭐⭐

2025.4.23

CF1193F🆗

这道题固定石头不动,让机器人和终点移动,我们注意到以下三点:

1. 我们可以能够先走到 $m-1$ 列,然后再走到终点,因为最后一列没有石头

2. 对于机器人,向上走转变完坐标系后是不动的,因此不优

3. 最先走到第 $m-1$ 列的方法最优,因为有且仅有 $m-2$ 次向右移动,多余的(额外操作的)向下还是向上都比答案不优(可以相当于最后再走这些向上/向下)

于是我们就能够发现,本题就是一个搜索,直接模拟即可.

难度:⭐⭐ 死因bfs

CF208E🆗

上厕所时想出来的

这道题求所有的 $k$ 级祖先相同的点的个数.

我们有一个很基础的想法:存下每一个节点 $k$ 级孙子的个数,然后怎么做都行了,但是时间和空间都不允许.

我们发现,dfs序有一个优秀的性质:一个子树的编号是连续的.

于是我们就有了这个想法:先统一存下深度相同的点的集合(存DFS编号),然后因为子树dfs序是连续的,所以

我们只需要向上找到 $k$ 级祖先,然后直接再这个深度的点的集合中二分找到再子树区间的元素个数即可.

难度:⭐⭐

level up! 2200~2700 (估计很快就降了)

2025.4.24

CF1205D

简单构造题写多了,遇到稍微困难点的构造题就无从下手了.

其实这道构造的入手点并不少:可以能够先从数量较少的构造入手,或者也可以从题目中给出的数的数量入手.

我们先从数量较少的构造入手,对于一棵树:我们有一种稳定的方式能够构造出至少 $n-1$ 条数值不同的路径,就是边权为dfs序之差.

我们再观察题目中给出的数量要求: $\lfloor \frac{2n^2}{9}\rfloor=\lfloor\frac{n}{3}\times\frac{2n}{3}\rfloor$ 又因为 $\frac{n}{3}+\frac{2n}3=n$ 我们能够想到,选重心作为根,然后将子树分成两类,一类构造 $n$ 种不同的取值,另外一类构造这些数的倍数即可(这样就是两数相乘)

难度:⭐⭐⭐⭐ 2700打脸了

2025.4.25

CF2025F

wow,是和年代一样的比赛号.另外2700构造题怎么这么多

我首想贪心,但是挂了.

题目给出的条件(二选一)就很适合建图,于是我们将这种二选一的关系看成一条边,我们腰围这条边分配顶点.

我们发现,我们可以先分配顶点,等所有的顶点都分配完毕之后再为每一条边分配权值.还是显然的:我们对于一个顶点所分配的边,边上的权值肯定是一正一负,这样是最优的.

所以我们可以尽量为每个顶点分配偶数条边,这个可以通过dfs树实现,对于一个儿子和当前点的边,如果儿子已经被分配了偶数条边就归自己,否则就归.这样我们就把每一个点的问题都丢给了根,然而显然根是消不掉的,因此我们就构造出了最优解.

细节就是注意先加后减.

难度:⭐⭐⭐⭐ 怎么又是2700

2025.5.6

咕咕咕…

CF404E 🆗

我们模拟,发现只能够放一块石头或者不放.因为如果放两块石头的话就会一定被困在这两个石头中间(因为两个石头都需要被碰到,否则就可以删去没有用的格子).没有新格子可以走了.

没有石头的情况是好办的,考虑有一个石头的情况:我们记录到左右的最远点,并记录到这里的最晚时间,我们发现,这个石头只会阻挡向这个方向走的路,所以原先能够走到极值点,现在也能走到(只不过是石头前)因此我们从到达极值时间开始向后走,这段路程并不会受影响,我们只需要判断最终的那个点是否被经过了多次,否就答案加一.

难度:⭐⭐有细节

2025.5.28

CF1924D

好像这是一个很常见的套路。

看到合法括号序列，套路的，我们想到使用栈，记录每一个位置操作后栈顶的位置，那么应该是一个折线。

我们发现这个长子序列可以贪心，左括号能加就加，右括号能删就删，那么这样匹配的应该是最多的。

我们注意到（但是我没有），这个折线应当开始于 $(0,0)$ 结束于 $(n+m,n-m)$ （不妨设 $n\geq m$，且没有无法匹配的右括号，因为有无法匹配的右括号就无法继续往下弹）。

我们想象它还能够弹成负的，那么不能加入的右括号个数就应该是整个折线所能够到达的最低点。根据题意，我们知道它是 $k-m$, 所以这个问题就被我们转化成了： 求最低点到达 $k-m$ 起止点为 $(0,0)$ 和 $(n+m,n-m)$ 的折线（每次都只能向上或向下走一个）个数。

我们发现不好统计，于是考虑差分一下，改为统计最低点不大于 $k-m$ 的折线个数，然后我们就好求了，我们仿照卡特兰数的方法，将最后一次接触 $k-m$ 的地方上下反转，这样就是一条从 $(0,0)$ 到 $(n+m,2\times k-n-m)$ 的折线，这种是好统计的，就是相当于要选出 $2\times k-n-m$ 次向一个方向的（不妨设向下），剩下 $2\times(n+m-k)$ 个两两配对，也有 $n+m-k$ 次向下走，因此总向下走的次数为 $k$ ，于是方案数就是 $\binom{n+m}{t}$ 。

难度：⭐⭐⭐⭐ 组合好题，但是看过就应该成板子了。

2025.6.12

CF1575G