丢人彩笔 oier 直播被 CF 2000 / AT 1500 干碎现场

记录一些做过的 cf 和 at 题。

Codeforces

tag 是自己给的，不是 cf 给的。

1684 (1+2)

A - C

略。

D $\small\color{blue}\textsf{1700}$ [greedy]

按照套路，这种一次操作之后往后加的考虑费用提前计算，跳过 $i$ 的收益是 $a_i-(n-i)$。

然后跳过一个之后，前面的元素费用提前计算部分少一单位，后面的元素本身费用多一单位，从而所有元素收益增加 $1$。

所以直接按 $a_i-(n-i)$ 排序然后从大到小选 $k$ 个出来跳了就行，$O(n\log n)$。

E $\small\color{orange}\textsf{2100}$ [greedy]

场上先写了个错解，大概是每次把最大的改到 mex。会被 $0,1,3,3,4$ 卡掉。

然后又写了个把二元组（出现次数，值）最大的改到 mex。好像是一个值改几个之后自己进入 mex 范围内的情况会有奇怪问题。

然后就想到了二分最大可能 mex，这个非常 sufficient，然后就写了。可能在通常情况下直接贪心看起来不太对的时候可以尝试套个二分啥的？

F $\small\color{red}\textsf{2600}$ [ds] [greedy]

首先观察到要改肯定是改成 $10^9+1,10^9+2,10^9+3,\cdots$ 这样的。

然后就是每一个元素只能留一个，然后变成左端点落在一段区间里面的时候对右端点有限制，用线段树维护区间取 $\max$ 单点求值。

注意判边界，场上因为第一次有 $l>r$ 无限递归的问题重新交了一发，有点亏。

事后证明第一次能过 system test，所以如果我没重交我没准就 GM 了（

赛后把自己 uphack 了，于是喜提人生中第一次成功 hack（（（

G,H

看不懂官方题解/yun

1685 (1)

A $\small\color{grey}\textsf{1100}$ [constructive]

这种不太能相邻交换的排序题自然就是捏几个样例然后手动枚举策略。

这个题还是挺显然的。

B $\small\color{purple}\textsf{2000}$ [greedy]

搞了 1h+，裂开。

首先如果两个相邻位置字符一样就从中间断开。

然后把所有交错段排序，长度为偶数的排前面，然后偶数和奇数各自按照长度升序。然后偶数 A 开头先贪心往里面填 AB，再贪心填 BA；其余都先贪心填 BA，再贪心填 AB。

如果把所有 AB 和 BA 都填完了，并且 A 和 B 的数量是对的就判定 YES，否则判定 NO，$O(n\log n)$。

不知道为啥是对的，思考方式大概就是枚举了几个排序策略然后只有这个能过样例。

C $\small\color{red}\textsf{2600}$ [greedy] [constructive]

又搞了 1h+，完全裂开。哦 2600 啊，那我 1h+ 合理合法。

按照套路，( 对应 $+1$，) 对应 $-1$，画出折线。

然后 reverse 一段相当于把那一段拿出来旋转 180 度再放回去，那么只要这一段的 max 小于等于两端相加就不会有点被折到下面。

那么任意字符串都可以 2 次操作变为合法匹配：找到折线的最高点，如果左边/右边需要翻就翻一下。这样由于一段的 max 在端点上，所以肯定没法折到下面。

然后只需要判 0、1 次是否可行。

0 次就是初始合法，1 次就是找到最左边的负位置 $L$ 和最右边的负位置 $R$，然后找 $L$ 前面的最大值 $l$ 和 $R$ 后面的最大值 $r$，如果 $l,r$ 能翻就翻 $l,r$，1 次。

$O(n)$。

D1 $\small\color{red}\textsf{2800}$ [constructive]

好像比 C 还简单点。

把这个 $p$ 当作一堆环来考虑，能重合的肯定尽量重合，那么唯一产生代价的地方必定是从一个环跳到另一个环。

手玩一下发现如果 $u,u+1$ 分别在环 A、环 B 里面，那么在环 A 上走，下一步走到 $u$ 的时候走到 $u+1$，产生 $1$ 的代价；然后在环 B 上走，下一步走到 $u+1$ 的时候走到 $u$，再产生 $1$ 的代价。显然这是从一个环跳到另一个环的代价最小的方案而且必然可行。

同时我们可以发现这个跳环的过程可以嵌套，所以就规定跳到另一个环的时候一定是跳到那个环上编号最小的点，然后 DFS 到 $u$ 的时候如果 $u+1$ 是某一个环上编号最小的点就跳过去。

从 1 开始 DFS 一遍然后倒序输出就可以了。

D2/E

先鸽。

总结：千万别碰 antontrygub 的场。

1672 (1+2)

A - D

没做，有时间看看。

E $\small\color{orange}\textsf{2200}$ [interactive] [greedy] [binary-search]

首先注意到如果取一个很奇怪的行数，那么如果空的很多就很浪费，不如直接压到一行。

然后就很容易发现多行能比一行优就必须能省掉几个空格，而且 $h$ 行一定无法省掉多于 $h-1$ 个空格。

那么我们只需要知道 $w=1$ 时的答案 $r$，然后枚举行数 $h$。如果能压进 $\lfloor r/h\rfloor$ 列就更新答案，否则没用。查这个就直接查 $\lfloor r/h\rfloor$，看返回的东西是不是比 $h$ 大就行了。

二分 $r$，交互次数 $n+\log(n\max l)$，可以通过。

写的时候有一发在枚举行数的时候不小心调用了两遍 query，后面几发被 $n=1,l=1$ 卡边界了。吐了。

F1 $\small\color{purple}\textsf{2000}$ [greedy] [constructive]

吐了，阴间构造能不能爬啊。

首先注意到两个一样的元素不能被串在一个置换环里面。如果有的话交换一下两个相同元素的出边一定还是合法的，但是可以把一个环分裂成两个。

然后朴素的想法是把所有元素第一次出现的位置串起来转一下，把第二次出现的位置串起来转一下，以此类推。

这个做法的问题在于两个环中间可以连出另一个环的时候，剩下的东西里面一旦有重复元素就可以分裂成更多的环，然后答案就小了。

但是我们注意到只要随便定一个顺序就不会出现相同元素。

当然可能存在三个环串起来的情况，但是我们可以只考虑其中的两个环。

从而按照出现次数降序定序即可，一样的瞎定就行。

挂的一发是上面那个假做法。

F2 $\small\color{red}\textsf{2800}$ [constructive]

不太理解评分，我觉得 F1 比 F2 难多了。

显然如果能找到一个环上面没有出现次数最多的数就肯定寄了，否则肯定可以。

于是建一个图，如果 $a_i=b_j$ 且不是出现次数最大的数（有多个就任意选一个），就连一个 $i\rightarrow j$ 的边。这样边数是 $n^2$ 的，但是可以每一个值 $v$ 开一个点，然后 $i\rightarrow a_i$，$b_i\rightarrow i$ 就可以优化到线性。

对新图跑拓扑排序，如果有环就 WA，否则 AC。

挂了一发数组开小了 /px。

总结：

1. 自己的构造果然只有 1600 水平，还是得练。
2. 赛场上记得手动测一下最小数据范围会不会挂，拍的话一定要记着拍小的然后保证 gen 能随到下界。记得所有东西最大数据范围开 sanitizer 跑一遍。

1548 (1)

C $\small\color{red}\textsf{2500}$ [combinoratics]

设 $f_{m,x}=\sum_{k=0}^n\binom{3k-m}{x}$。

由加法递推，有 $f_{0,x}=f_{1,x-1}+f_{1,x}$，$f_{1,x}=f_{2,x}+f_{2,x-1}$。

又由著名恒等式，有 $f_{0,x}+f_{1,x}+f_{2,x}=\binom{3n+1}{x+1}$。

然后就做完了，$O(n+q)$。

D1 $\small\color{orange}\textsf{2300}$ [geometry]

由皮克定理，$S=n+\dfrac{s}{2}-1$，考虑到所有坐标都是偶数，则 $S$ 是偶数，又要求 $n$ 是奇数，则 $s$ 必须是 $4$ 的倍数。

于是所有坐标模 $4$ 之后暴力即可。

最后一步没想到……遇到这种限制和小模数相关的就往暴力上面想一下吧……

1470 (1)

D $\small\color{orange}\textsf{2200}$ [constructive]

在原图上两个黑点不能相邻，于是每次确定一个黑点就把它的邻居全设成白点。

强制 $1$ 是黑点并把邻居设成白点，对所有白点向外 BFS。

对于一个白点，遍历其所有邻居，如果颜色未确定就置成黑点，并把黑点的所有邻居置成白点。

最后把整个图搜完就对了，复杂度线性。

C $\small\color{red}\textsf{2500}$ [interactive] [brute force] [randomization]

这个变换的值乱七八糟的，但是可以观察到乱掉的值会逐轮向外扩散。

所以在环上随机撒点直到撒到一个乱掉的点，以高概率这个过程在 $O(\sqrt n)$ 步内结束。

考虑只要我们逐步模拟这个过程，那么每一次查询到乱掉的点的时候都可以大幅缩小答案的取值范围。于是我们从这个点开始向两侧搜，那么取值范围就可以以足够快的速度缩小到一个数。这块随机会在 $k=2$ 炸掉，因为 $k=2$ 的时候扰乱点取值都是 $1$ 和 $3$。如果是现场比赛的话记着测最小数据范围。

具体不会分析，但是最大的点只跑了 845 次，比标算还快了不少。

1361 (1)

C $\small\color{red}\textsf{2500}$ [constructive] [binary search] [graphs]

二分答案 $k$，然后把所有点权对 $2^k$ 取模。注意到现在只能在相同的点之间连新边，从而我们可以视为能从原有的一条边走到另一条边上当且仅当它们有一个端点相同。

现在需要把所有边串起来成一个环，跑欧拉回路即可。

复杂度 $O(n\log\log v)$。

挂了两发欧拉回路没写对。

D $\small\color{red}\textsf{2900}$ [greedy]

显然最后是个树，然后选 $k$ 个点最大化树上距离，有朴素 $O(nk)$ DP 做法，但是无法通过。

考虑到这个树肯定是根上挂一堆链，然后观察样例可以猜出大概有两种情况：要么是每一个链选一个后缀；要么是一个链选一段前缀和后缀，然后不在链上的点全选，而且后缀长度恰好为 $k/2$。

可以思考一下类似山区建小学的调整来说明这玩意是对的。

然后分类讨论。第一种情况按照套路拆贡献，对自己下面的点的贡献是负的深度，对其他点是正的深度，然后下面肯定都选上了，所以可以计算。

第二种情况直接找最长链然后填就行了。

复杂度 $O(n\log n)$。

挂了两发假做法。这题在考场上可以写个 $2^n$ 的来对拍。

1697 (2)

E $\small\color{red}\textsf{2400}$ [combinatorics] [brute force]

solution。

F $\small\color{red}\textsf{2800}$ [constructive] [2sat]

按照套路，和两个元素相关的限制考虑建图，值域很小考虑拆点。

拆点之后为了保证限制只关系到两个元素可以把 $(i,j)$ 的意义设为 $a_i\leq j$。

然后发现问题变为 2SAT，然后做完了。

复杂度 $O((n+m)k)$。

1693 (1)

A $\small\color{green}\textsf{1300}$ [greedy]

略。

B $\small\color{blue}\textsf{1700}$ [greedy] [dp]

考虑到这是若干条从根到底的路径加，考虑树形 dp，记 $f_{i,j}$ 表示 $i$ 子树内有 $j$ 条路径时，$i$ 的值最大是多少。

同时注意到只有 $j$ 最小的一个状态有用，因为如果子树里面可以少一个路径，那么根单出来一定不会增多路径数，同时可以让 $i$ 的值取到最大值。

于是就可以把 $f_i$ 记成一个二元组，转移的时候把所有孩子的二元组的两维分别加起来，然后如果第二维小于 $l_i$ 就把它改为 $r_i$ 然后给第一维 $+1$，否则把第二维和 $r_i$ 取 min。

复杂度 $O(n)$。

挂了两发认为只能传一个路径。

C $\small\color{orange}\textsf{2300}$ [shortest paths]

首先有朴素 DP，设 $f_i$ 为 $i\rightarrow n$ 的最小的最大可能代价。转移就是枚举所有出边中截断多少条，然后取没截断的最大的。

现在转移带环，注意到转移过程中代价必然增大，用类似 dijkstra 的方法优化转移即可。

复杂度 $O(n\log n)$。与 Intergalaxy Trips 比较相似。

D $\small\color{red}\textsf{2800}$ [dp]

考虑朴素的 dp。这个 dp 有两个性质：

• 一个点最多有 4 种取值：无解 / 只有一个序列贡献两种，然后以递增为例，如果 $i$ 是最大的满足 $a_i>a_{i+1}$ 的 $i$，那么递增的 dp 值只能取到 $a_i$ 和 $a_{i+1}$。（证明：首先不能取到前面的，因为这两个元素无法同时放到上升序列里面；然后如果取到后面的，那么它一定是下降序列的最后一个元素（因为后面都更大），所以一定可以把它改到上升序列里面。）
• 一个位置的 dp 值不变则后面的都不变。（显然）

于是倒着枚举左端点，每次暴力重新 DP，然后如果到一个位置 DP 值一样了就 break。由于 DP 值肯定是单调递增/递减变化，于是复杂度线性。

完全看不出这个性质啊。算了 EI 不会的题我也没必要会。

901 (1)

B $\small\color{orange}\textsf{2200}$ [math] [constructive]

显然模一次至少减少一次，于是我们希望它只减少一次。

然后取 $F_0(x)=1,F_1(x)=x,F_{n+2}(x)=xF_{n+1}(x)\pm F_n(x)$，$\pm$ 就取合法的一侧（即加完满足系数 abs $\leq 1$）即可。

不知道为啥是对的，但反正只有 150 打个表就能证。

C $\small\color{orange}\textsf{2300}$ [graphs] [ds]

按照套路，看到奇怪限制尝试猜测充分必要条件。可以观察到这个图是个点仙人掌。（否则两个环套起来肯定会生成一个偶环）

然后就是一个环里面最小点和最大点不能同时出现，随便写个数点维护一下就完事了。

D $\small\color{red}\textsf{2700}$ [constructive] [graphs]

做法写脸上属于是，观察到这玩意叫 weight a tree，但是题里面给个图，自然考虑生成树。

正常来讲，构造都是从简单方法出发，先考虑只拿个树出来剩下全 0 行不行，发现不一定，因为根没有向上的边给他调整。

那么我们考虑用非树边来凑一下让根剩下的正好是 0。注意到两端深度奇偶性不同的边无法改变根值，因此我们找一条两端深度奇偶性相同的边，然后让它把根调成 0。

如果能调成 0，再跑一遍树做法即可。否则输出无解。复杂度 $O(n+m)$。

1242 (1)

C $\small\color{red}\textsf{2400}$ [graphs] [bitmasks] [dp]

一个点往它踢出去的那个元素连边，由于元素互不相同所以至多一个入边。

然后找环，覆盖，即可。

找环方便起见可以把边倒过来。

挂了一个细节和一发 ll。

1229 (1)

C $\small\color{red}\textsf{2400}$ [graphs] [brute force]

看错题了/px，考场上记着对样例模拟一下。

按度数根号分治，小的直接暴力反向。大的可以暴力反向两个大点之间的边，但是大点到小点比较难处理。

如果只反向需要反向的边，那么由于它再被反回来必定是修改了小点，于是均摊 $O(m\sqrt m)$，就做完了。

D $\small\color{red}\textsf{2700}$ [ds] [math]

首先可以转化成 120 个数的一个群运算。

然后从左往右扫，维护每一个数第一次出现的位置，然后倒着扫过去，每次扫到一个使群扩大的元素就暴力扩张。由于每一次扩张至少增大两倍，于是总复杂度 $O((k!)^2+nk!k\log k)$。

809 (1)

C $\small\color{red}\textsf{2600}$ [dp] [math]

瞪眼观察得到 $a_{i,j}=(i-1)\oplus (j-1)+1$，然后数位 DP。

这个结论和 SG 定理等价。

D $\small\color{red}\textsf{2900}$ [dp] [ds]

按照套路，问题有三个维度：前 $i$ 个，LIS 长度 $j$，最后一个数是 $k$。枚举最优化哪一维。

然后发现最优化 $k$ 的时候，$f_{i,j}$ 对任意 $i$ 关于 $j$ 严格单调。于是可以平衡树优化维护。然后就做完了。

E $\small\color{black}\textsf 3\color{red}\textsf{100}$ [number theory] [dsu on tree]

solution

挂了个手残的地方。这题考场上随便写点啥都能对拍。

1667 (1)

C $\small\color{red}\textsf{2400}$ [constructive]

先把半后视作车，那么 $n\times n$ 的棋盘上面放 $m$ 个车会留下一个 $(n-m)\times (n-m)$ 的子矩阵覆盖不到。考虑用斜线覆盖它们，由于只有一个方向，所以需要至少 $2m+1$ 条斜线。

然后考虑到国际象棋里面后的一些性质，尝试用马的走法来覆盖，然后枚举一波就能构造出来。

D $\small\color{red}\textsf{2900}$ [dp] [constructive]

随便取一个点当根，设每一个点 $u$ 的父亲为 $f_u$。

设 $p_{u,0/1}$ 表示在 $f_u$ 除了向 $u$ 以外连了偶数 / 奇数条边的时候能否删去 $u$ 子树内的所有边以及 $f_u\leftrightarrow u$。

然后考虑从儿子转移。分四种情况讨论。

情况 1：$u$ 有偶数个孩子，转移到 $p_{u,0}$。

那么可以在删去 $0,2,4,\cdots$ 个孩子的时候删掉 $u\leftrightarrow f_u$。

设依次删去 $v_1,v_2,\cdots,v_k$。

那么如果在删去 $0$ 个孩子的时候删去 $v_i$，那么依次从 $p_{v_1,1},p_{v_2,0},p_{v_3,1},\cdots,p_{v_k,[2|k]}$ 转移。如果在删去 $2$ 个孩子的时候删去 $v_i$，那么第二个下标分别变为 $0,1,1,0,1,0,\cdots$。$4$ 个孩子同理变成 $0,1,0,1,1,0,1,0,\cdots$。

注意到 $0$ 的个数和 $1$ 的个数恒定。又由于我们可以自由排列 $v_{[1,k]}$，所以能否删去只和个数有关。于是统计个数即可转移。

其余三种情况类似，因此我们可以在 $O(n)$ 时间内完成整个 DP，并判断解的存在性。

考虑输出方案。

我们可以递归输出方案，然后每次分配一下哪些孩子取 0，哪些孩子取 1，然后向儿子依次递归，在我们希望删除向父亲的边的时候删除它。

于是整个题就 $O(n)$ 做完了。实现的时候一个比较好的方法是取叶子当根。

E $\small\color{black}\textsf{3}\color{red}\textsf{000}$ [combinatorics] [fft]

考虑枚举一个点 $u$ 强制它是重心。

那么计数的结构就是从 $u$ 后面选一些点放到 $u$ 的子树外面（与 $u$ 前面的点划分到一起），再将其余的点划分为若干 $u$ 的子树，要求划分出来的所有集合满足其大小 $<\dfrac{n-1}{2}$；然后把每一个集合串成一个树。

首先考虑对所有 $s$ 计算将 $s$ 个点连成若干棵树，且每一棵树均满足大小 $<\dfrac{n-1}{2}$ 的方案数。

枚举编号最小的点所在树大小转移：

$$f_k=\sum_{i=1}^{\frac{n-1}{2}}\dbinom{k-1}{i-1}f_{k-i}\cdot (i-1)!$$

然后考虑计算答案，枚举前面的点在后面选了多少个：

$$p_i=\sum_{k=0}^{\frac{n-1}{2}-i+1}\dbinom{n-i}{k}f_{n-i-k}\cdot(i+k-2)!\cdot (i-1)$$

（需要特判 $i=1$，$1$ 的答案与 $2$ 相同）

暴力是 $O(n^2)$。

首先对于 $f$ 的计算，可以拆组合数得到如下形式：

$$\dfrac{f_k}{k!}=\dfrac{1}{k}\sum_{i=1}^{\frac{n-1}{2}}\dfrac{f_{k-i}}{(k-i)!}$$

可以实时维护前缀和做到线性。

然后对于 $p$ 的计算可以类似拆组合数得到数列卷积形式：

$$p_i=(i-1)(n-i)![x^{n-i}]\left(\sum_{i=0}^n\dfrac{x^i}{i!}\right)\left(\sum_{i=\frac{n+1}{2}}^{n}\dfrac{(n-i-2)!}{i!}f_ix^i\right)$$

使用 FFT 计算即可 $O(n\log n)$。

1696 (1+2)

感谢 feecle 送我上红。

A - C

略。

D $\small\color{purple}\textsf{1900}$ [greedy] [ds]

首先有显然贪心，每次一定向右走尽量多。

然后拿个支持区间 max/min 的数据结构找到向右最多走到哪就行。

E $\small\color{purple}\textsf{2000}$ [combinatorics]

找规律发现是一堆组合数上指标前缀和，于是做完了。

F $\small\color{red}\textsf{2600}$ [greedy] [constructive]

首先如果已知一条边 $u,v$，那么可以利用 $d(u,v)=d(w,v)$ 找到所有 $v,w$ 边。

然后枚举一条边 $1,x$，BFS 出整个树，然后 $O(n^3)$ 暴力 check，就 $O(n^4)$，就做完了。

1225 (1+2)

E $\small\color{orange}\textsf{2200}$ [dp]

solution

F $\small\color{red}\textsf{2500}$ [greedy] [constructive]

考虑一次操作至多让最大深度 -1，于是得到操作次数的一个下界为点数减最大深度。

然后发现可以构造到这个下界，具体就是类似于每次把包含最深点，而且位置不对的往上拉一下。

G $\small\color{black}\textsf 3\color{red}\textsf{100}$ [bitmasks] [dp] [greedy]

考虑将问题转化为如下形式：对每一个 $i$ 规划一个 $b_i$，然后要求 $\sum a_ik^{-b_i}=1$。

不显然的是从 $b$ 构造出一组方案。这种配对构造方案形式的东西一般可以考虑简单贪心（？），于是枚举一波策略，发现每次选指数最小的两个合并就是对的。（类似的有 noi2020 制作菜品）

然后 bitset 优化状压 dp 即可。$O(2^nnk/w+2^nk)$。

1286 (1)

E $\small\color{black}\textsf 3\color{red}\textsf{200}$ [strings] [brute force]

首先每次的增量就是 border，然后就是 fail 树上的一堆祖先，但是因为链不能一一对应，因此不合法的 border 可以不连续，从而无法直接遍历并去除不合法 border。

于是以下一个字符为区分，记个祖先即可。维护答案可以使用单调栈+树状数组。

复杂度 $O(n\log n)$ 或 $O(n\log n+n|\Sigma|)$。

1292 (1)

C $\small\color{orange}\textsf{2300}$ [greedy] [dp]

考虑 mex 本质是一种 min，min 求和按套路拆成枚举 $k$ 求和 $\geq k$ 的方案数。

那么首先注意到如果 $\geq k$ 有方案，那 $<k$ 的边的所有端点的虚树必须成链。然后观察到把它们都聚到一起比散开更优，然后就可以 dp，设 $f_{u,v}$ 表示路径 $u,v$ 上面填了 $0$ 到 $d(u,v)-1$ 的所有数，求和到 $d(u,v)$ 的最大值。

枚举删掉两端的一个点转移即可。复杂度 $O(n^2)$。

F $\small\color{black}\textsf 3\color{red}\textsf{500}$ [greedy] [dp] [combinatorics] [number theory]

首先考虑如何求出最小值。这个模型可以如此刻画：有一个 DAG，满足若 $i\rightarrow j$ 有边，$j\rightarrow k$ 有边，则 $i\rightarrow k$ 有边。初始所有点是黑点，选择尽量少的点改白，然后对于任意三个点 $u,v,w$，如果 $u,v$ 都是白点，$u\rightarrow v,w$ 均有边，则可以把 $w$ 改白。

在任意 DAG 上似乎无法避免状压所有点，但是考虑那个性质，首先所有没有入度的点必须直接改白，然后对于一个弱连通块，任意一个有入度的点都至少存在一个没有入度的点能够到它，那么就至少存在一个没有入度的点与它直接连边。

那么就只需要压没有入度的点，然后就可以用一个高维前缀和来算出每一个点集能够覆盖多少个点，然后再记下来已经改掉了多少个点即可。

然后大于 $n/2$ 的点如果没入度必然孤立，小于 $n/2$ 按 $/2$ 拼，抽屉原理，最多 $n/4$ 个点没入度，就做完了。复杂度 $O(2^{n/4}n^2)$。

1699 (2)

D $\small\color{orange}\textsf{2300}$ [dp]

差点被 2D 干碎了。

考虑到这玩意类似括号匹配，可以考虑前缀 dp，设 $f_i$ 表示强制 $i$ 保留，$[1,i]$ 最多剩多少个一样的。如果 $[1,i]$ 中没法删到全和 $i$ 一样，则 $f_i=-\infty$。

转移枚举上一个保留点，就只需要支持快速判断区间是否可以被删空即可。因为被一个强制保留的东西隔开的两部分独立。

再考虑括号匹配，有理由猜测一个区间可以被删空当且仅当长度是偶数并且不存在绝对众数。事实上如果满足这个条件一定可以匹配。

然后就可以快速预处理，然后就 $O(n^2)$ 做完了。

E $\small\color{red}\textsf{2600}$ [dp] [two-pointers] [brute force]

感觉比 D 还简单点。

考虑双指针，枚举最小值 $x$，然后可以 dp 出每一个数分解为 $\geq x$ 的数，最大的数最小是多少。

然后发现倒着枚举最小值的话每次只需要转移 $x$ 的倍数，然后就可以均摊 $O(m\log m)$。于是只需要维护所有出现过的数的最大 dp 值。观察到这个值单调不升，于是开个桶，每次发现桶空了就暴力减小最大值即可。

复杂度 $O(m\log m)$。

1030 (1+2)

G $\small\color{red}\textsf{2900}$ [number theory] [greedy]

打个表发现每一个数的循环节要么是 $p$，要么是 $p-1$，要么是取 $a=0$ 形成一个链长和环长都是 1 的 p。

然后贪心，先尽量放 $p$，然后从大到小改 $p-1$，再有浪费就给答案 +1。

复杂度和一堆实现细节有关，反正都能过。

1266 (1+2)

F $\small\color{red}\textsf{2900}$ [greedy]

手摸一下得到奇数的形态一定是一个中心点往外挂一堆长度一半上取整的链和最多一个短一个点的链，偶数一定是一个中心点或者一个中心边往外挂一堆长度一半的链。

然后可以维护出每一个点支出去的子树的深度，然后把深度一样的缩起来暴力就过了。

复杂度显然有 $O(n\sqrt n)$ 上界，不过根本跑不满。

1558 (1)

A $\small\color{green}\textsf{1300}$

略。实在不知道该给啥 tag。

B $\small\color{purple}\sf 1900$ [dp] [brute force]

略。

C $\small\color{purple}\sf 2000$ [constructive]

每次复位 $n$ 和 $n-1$：

• 把 $n$ 转到 1；
• 把 $n$ 转到 $n-1$ 左边；
• 把 $n$ 和 $n-1$ 反过来；
• 把 $n$ 和 $n-1$ 转到头；
• 把 $n$ 和 $n-1$ 转到尾；
• 复位完成，剩下递归。

D $\small\color{red}\sf 2600$ [ds]

每次就是把一个元素插到一个位置，然后在旁边放个小于号，最后插板，平衡树维护即可。

1534 (1+2)

E $\small\color{orange}\sf 2300$ [bfs]

注意到答案一定是所有询问的答案 xor 起来，然后注意到每一个数没有区别，于是只需要记录选择了多少个数即可，容易使用 bfs 求出最小步数。

复杂度 $O(n^2)$。

F2 $\small\sf\color{black}3\color{red}000$ [greedy] [graphs]

准备写个题解，先鸽。

1781 (1+2)

发 cf 上了。

1817 (1)

C $\small\color{red}\sf 2400$ [math]

考虑前两项，设为 $A(x)=a_nx^n+a_{n-1}x^{n-1}+(A(x)\bmod x^{n-1})$ 和 $B(x)=b_nx^n+b_{n-1}x^{n-1}+(B(x)\bmod x^{n-1})$。

则 $A(x+s)$ 的前两项是 $a_nx^n+(a_{n-1}+nsa_n)x^{n-1}$，则我们要求 $b_n=a_n$ 且 $b_{n-1}=a_{n-1}+nsa_n$。

由于题目保证 similar 所以第一个等式没用，只需要使用第二个解出 $s=\dfrac{b_{n-1}-a_{n-1}}{na_n}$ 即可。

$a_{n},a_{n-1},b_{n-1}$ 用线性插值求，总复杂度 $O(n)$。

话说回来，数据是咋造的，多点求值硬跑 5e6？

1835 (1)

D $\small\color{red}\sf 2900$ [math] [graphs]

由于 $n^3<k$，相当于我们只需要求出一个 SCC 内所有环的大小的 gcd，设为 $D$。

自然的想法是枚举一个染色数 $k$，DFS 染色，对于边 $(u,v)$ 将 $v$ 染成 $u$ 的颜色 $+1$ 再模 $k$，如果染色后没有边颜色冲突则有 $k|D$。

这样是 $O(n^2)$ 的。为了解决这个问题，直接随便搜一个环出来，然后枚举这个环的大小的约数。

复杂度 $O(nd(n))$。

E $\small\sf\color{black}3\color{red}500$ [combinatorics] [dp]

solution

1827 (1)

E $\small\sf\color{black}3\color{red}400$ [ds]

如果 $u,v$ 无法相互到达，则在 $u$ 以 $v$ 为根的子树里面任意取一个叶子，$v$ 以 $u$ 为根的子树里面任意取一个叶子，它们两个一定也无法相互到达。

于是只考虑叶子。现在可以对每一个叶子考虑包含它的所有路径的并（总共只有 $O(m)$ 条路径）。要求任意两个叶子对应的路径并有交。

考虑每一个路径并在树上都是一个连通块，考虑每个连通块的 LCA。如果存在一对 LCA 没有祖先关系则这两个连通块对应的叶子无法互相到达。

否则只需要考虑每个连通块是否与 LCA 深度最大的连通块有交即可。

复杂度 $O(n\log n)$。

1738 (1+2)

F $\small\color{red}\sf 2400$ [interactive] [greedy]

solution

G $\small\color{red}\sf 2900$ [greedy] [constructive] [dp]

相当于选出 $k-1$ 条不交的左下到右上的 1 路径覆盖所有 0。

于是对 0 求 LIS，有 $k$ 以上就输出 NO，否则以左下角为起点，右上角为终点，贪心地优先往右走，覆盖所有 LIS 长度为 $k-1$ 的格子，再以左下角往上一格为起点，右上角往左一格为终点，贪心地优先往右走，覆盖所有 LIS 长度为 $k-2$ 的格子，以此类推。

复杂度 $O(n^2\log n)$。

1887 (1)

C [ds]

在序列上从左往右扫，线段树上维护每一个时刻的值。每次在线段树上把大于 min 且不是 $+\infty$ 的位置推成 $+\infty$，线段树上维护区间 min/max 做类似势能线段树的处理即可 $O(n\log q+q\log q)$。

D [dnc]

对序列分治，每次处理跨过中间点 $m$ 的询问。

考虑分界点在左半边的情况，递减枚举分界值 $x$，设 $r$ 是最大的满足 $[m+1,r]$ 内任意数 $>x$ 的值，$l$ 是最小的满足 $[l,m]$ 内任意数 $>x$ 的值。这两个值可以双指针维护。

然后二分求出最小的 $l_0$ 使得 $[l_0,l)$ 内任意数 $\leq x$，则对于询问 $[l',r']$ 满足 $l'\leq m<r'$，如果其满足 $l_0\leq l'<l$ 且 $r'\leq r$，则其答案为 $1$。可以把所有 $[l_0,l)$ 求出来挂在 $r$ 上然后扫描线一遍来处理。

分界点在右半边对称。使用树状数组维护扫描线，复杂度 $O(n\log^2n+q\log n)$。

E [interactive]

按照经典套路，行到列连边转成一个二分图，由于给定 $2n$ 个位置，必定可以成环。

目标是求出一个 4 元环使得边的颜色互不相同，于是先随便找一个环，每次连的边把这个环劈成两半，无论染成什么颜色，一定有一半的所有边的颜色和新边的颜色都不同。于是每次环长减半，做 log 次就做完了。

---

---

---

AtCoder

CF 做多了也有点审美疲劳（大雾）

难度是按 Dan 数标的，较接近更高一档的会标上 $^+$。10 Dan 往上 200 分升一档。

ARC121

E $\color{orange}\small[\textsf{4}]$ [dp] [combinatorics]

考虑容斥，然后对于一对违反限制的点，在上面计数，就可以树上背包 $O(n^2)$。

F $\color{red}\small[\textsf{5}^+]$ [dp] [greedy]

考虑贪心，发现先缩 and 边就是对的。感性想法是先缩 or 的话对缩 and 的过程无法产生实际影响（即，即使它能变成 1，我先全缩起来也没关系）。

然后要求至少存在一个全 1 的 and 连通块，直接 $f_{i,0/1,0/1}$ 表示 $i$ 子树，根所在连通块是否全 1，不与根连通的连通块里面是否存在全 1，方案数。暴力转移即可。$O(n)$。

AGC005

F $\color{goldenrod}\small[\textsf{8}]$ [combinatorics]

设 $1$ 为根，设 $S_u$ 为 $u$ 的子树大小。考虑在边上计数连通块大小之和。

$$A_k=\dbinom{n}{k}+\sum_{i=2}^n\left(\dbinom{n}{k}-\dbinom{S_u}{k}-\dbinom{n-S_u}{k}\right)$$

这玩意可以化成差卷积，用 FFT 计算即可。复杂度 $O(n\log n)$。

ARC141

F $\color{gold}\small[\textsf{11}]$ [constructive] [strings]

solution

太 TM 难了，再也不做金牌题了/dk

ARC144

D $\color{orange}\small[\textsf{3}]$ [combinatorics]

观察到构造一个满足条件的序列等价于给 $n$ 位分别赋一个权值 $w$，满足 $\sum w\leq k$，然后枚举对应位是取 $0$ 加 $w$ 还是取 $1$ 加 $w$，再整体平移。

于是枚举 $\sum w$，枚举 $w=0$ 个数，枚举划分，枚举取反，枚举平移量可以直接得到答案式：

$$K+1+\sum_{S=1}^K\sum_{i=1}^n\dbinom{n}{i}\dbinom{S-1}{n-i-1}2^{n-i}(K-S+1)$$

交换一下求和顺序然后用几下恒等式就可以 $O(n)$ 算了。

ARC150

D $\color{orange}\small[\textsf{3}]$ [combinatorics]

考虑套路性转化，枚举一个点，计算它和根连通之前期望被选几次。

这玩意只跟深度有关，写个状压打个表发现是调和级数，于是 $O(n)$ 做完了。

ARC162

E $\color{orangered}\small[\textsf{4}^+]$ [combinatorics] [dp]

相当于按 $B$ 一样的划分集合，再对每个集合分配一个颜色。

于是按 $A$ 排序后 dp，设 $f_{i,j,k}$ 为当前划分大小为 $i$ 的集合，已经划分了 $j$ 个集合，划分的集合的总大小为 $k$。

转移的时候，枚举划分 $c$ 个集合，所有 $a_x\geq i$ 的位置 $x$ 里面有 $k$ 个已经被占用，所以设 $S_i=\sum_{j}[A_j\geq i]$，则集合划分的方案数是 $\dfrac{(S_i-k)!}{c!(i!)^c(S_i-k-ic)!}$。

所有 $a_y\geq i$ 的颜色 $y$ 里面有 $j$ 个被占用，则染色的方案数是 $(S_i-j)^{\underline{c}}$。

于是转移就是拿上面两项乘上 $f_{i,j,k}$ 转移到 $f_{i-1,j+c,k+ic}$。初始状态 $f_{n,0,0}=1$，答案 $\sum_{j}f_{0,j,n}$。

复杂度不太好算，但是容易证明不高于 $O(n^3\log n)$。

ARC156

D $\color{orange}\small[\textsf{3}^+]$ [dp]

solution

ARC149

D $\color{red}\small[\textsf{5}^+]$ [ds] [brute force]

不难发现所有的棋子会逐渐集中。

然后就是类似第二分块的处理，维护一个并查集，每次移动把区间分成两块，小的那块往大的那块合并。

E $\color{crimson}\small[\textsf{6}^+]$ [sortings]

设值域线转 0/1。可以分析出对 01 序列的操作是把前 $m-1$ 个 1 集中到一起然后不断往后推。于是将序列还原回去之后，第 $m$ 个 1 之后的所有位置的 01 必须对上，直接用这个做即可。

ARC160

F $\color{goldenrod}\small[\textsf{7}]$ [dp] [brute force]

设值域线转 $0/1$。

然后一个排列可以转化为 $n+1$ 个 $0/1$ 序列，这个排列被排序当且仅当所有 01 序列均被排序。

于是我们可以建一个 $2^n$ 个点的 DAG，每一个点对应一个集合 $S$，$S$ 向所有 $S\cup \{x\}(x\notin S)$ 连边。定义一个点 $S$ 是合法的当且仅当它对应的 01 序列能够被完成排序，那么一个合法的排列就对应一条从 $\varnothing$ 到 $\{1,2,\cdots,n\}$ 且只经过合法点的路径。

暴力是 $O(2^nm)$ 的。

为了优化这个过程，开 $n^2$ 个 vector 对每一对位置 $i<j$，有哪些初始 01 序列在完成一系列交换之后 $i,j$ 位置构成一个逆序对，采用懒惰删除。由于每一次交换最多会增加 $n$ 对位置，所以这部分总复杂度 $O(2^nn^3)$。

计数合法点路径时，当 $S$ 从不合法变为合法，只需要更新 $T\supset S$ 的路径个数，暴力即 $O(3^nn)$。

总复杂度 $O(2^nn^3+3^nn+m)$，由于不需要取模可以轻松通过。

ARC157

F $\color{goldenrod}\small[\textsf{8}]$ [dp] [greedy]

三个分一组，分类讨论可以得到答案至少为 $\dfrac{2}{3}n$。

于是直接跑 LCS 的 dp，把两个位置中间的串状压下来，即可做到 $O(2^{\frac 1 3 n}n^2)$。