四月份训练手记

4.1 - 1 - Problem - H - Codeforces

思路

这道题主要是考察线段树的应用

不难发现，对于某一个字符串（不做修改），我们可以通过 DP 的方法来得到答案，只需要维护在某个点之前：

• 以 $1$ 结尾的答案总贡献和子串数量
• 以 $0$ 结尾的答案总贡献和字串数量

至于转移方法，我们只需要在新加入一个不同字符的时候更新贡献与子序列数量即可

那为了支持修改，我们需要使用线段树来维护以上信息，但线段树维护的是区间，而不是前缀

所以我们需要对子串的开头和结尾都进行分类

并且在合并的时候，考虑所有情况的贡献，减去那些中间字符相同（比如 $01$ 和 $10$ ）的两个串合并后的贡献是两个串的贡献相加再 $-1$

收获 & 反思

线段树的又一应用方法

对于区间上贡献具有一定的 “可加性” 或者 “分类可加性”，的时候，就要考虑使用线段树来维护

对于 “线段树是在维护幺半群上的信息” 这句话的理解又加深了一点

4.1 - 2 - Problem - I - Codeforces

思路

我们先考虑，如果是朴素的贪心，怎么来解决问题：

• 首先对于每一个有序对 $(x,y)$ 都可以用贪心统计答案：先遇到哪个字符，我就先加入序列
• 不难证明，这样找到的序列一定是最长的

思考一下，这样的贪心解法对于我们的解答有什么启发呢？

进一步地说，在这种贪心策略下，某一个位置的字符，在什么情况下才会被 “收录” 到某一个有序对 $(x,y)$ 的答案当中，进而对最终答案产生贡献呢？

考虑到我们贪心的过程，答案也是显然的：

• 在某一轮贪心中，只有这个字符与前一个相同字符之间，有一个目标字符（有序对中的另一个字符），这个字符才会被 “收录”
• 如果没有前一个字符（首次出现）则一定会被收录

那我们的贡献统计就变得简单起来了，对于每一个位置：

• 如果是第一次出现，一定会产生贡献， $cnt=m-1$ 之所以要减一是因为它不能和自己构成有序对（题目限制）
• 否则，我们找它和前一个相同字符之间，统计其中不同字符的个数，就是它的贡献值

问题又转化为了：如何统计区间上的不同字符个数

对于普适的做法，我们可以使用主席树（可持久化权值线段树）来统计区间上不同数值的个数

但这道题不需要那么复杂，因为我们要求的区间具有 右节点严格非降的后缀区间 性质，在这个条件下，就可以记录每个字符最后一次出现的位置，并且标记为 $1$ ，然后树状数组维护区间和与单点修改就可以了

收获 & 反思

思路相当值得学习！

这道题的几个关键点：

• 用贪心简化问题，便于考虑
• 用贡献法转化问题，使得枚举量变为 $O(n)$
• 利用待统计区间的特殊性质，用树状数组完成区间字符种数的统计

4.2 - 1 - Problem - G2 - Codeforces

超级神秘好题

思路

我们考虑对于一组数 $(p_i,p_j)$ ，它们满足要求的条件是 $ij\mid p_i{p}_j$

不难注意到，$p_i$ 和 $i$ 总是同时出现的，所以不妨预处理一下，令 $x_i=\frac{i}{\gcd (i,p_i)}$ ，$y_i=\frac{p_i}{\gcd (i,p_i)}$ ，其中有 $x_i\perp y_i$

于是题目要的条件就变成了 $x_i{x}_j\mid y_i{y}_j$ 由于 $x_i\perp y_i$ 并且 $x_j\perp y_j$ 于是条件进一步变为：

• $x_i\mid y_j$ 并且 $x_j\mid y_i$

一个很自然的想法就是，我们枚举所有可能的 $x$ ，然后枚举是 $x$ 的倍数的 $y$ 的值，对于这些 $y$ 来检查，然后统计答案

但是这样子做有一个问题：我们前两层枚举的时间复杂度是 $O(n\log n)$ 的，但是有可能对于某一个很小的 $x$ ，有相当多的点，这个时候检查的时间复杂度就会超出限制

如何才能保证时间复杂度严格低于限制呢？

我们考虑上一个方案的缺点是什么，就是对于一个体量很大的 $x$ （也就是有很多个 $i$ 都满足 $x_i=x$），我们在枚举可能的 $j$ 的时候，需要对每一个 $i$ 都去判断，效率是很低的

考虑使用预处理来提高效率

我们的检查是在做什么？是在检查每一个可能的 $j$ ，有几个 $i$ 能满足 $x_j\mid y_i$ ，也就是说其中有几个 $y_i$ 的因数包括了 $x_j$ ，那我们就可以提前统计出每一个因数出现的次数，然后每次直接统计贡献

为什么这样时间复杂度是正确的？

首先每个数只会在初始阶段被枚举一次，对应的就是二层的枚举量严格小于 $n\log n$，同时考虑枚举因子的开销，也是每一个 $y_i$ 只会被枚举一次，所以枚举因子的开销也严格小于 $n\log n$ ，证明完毕

收获 & 反思

这道题做法难度不高，但是其中涉及到了较为复杂的时间复杂度优化想法与时间复杂度的正确性证明

解决的方法有很多，但是其中相当一部分可以被精心构造的数据卡到 $TLE$ ，所以需要我们牢固掌握时间复杂度的分析和优化手段，设计出严格时间复杂度的 $Solution$

4.3 - 1 - Problem - E3 - Codeforces

这次会用倍增了

思路

看到这道题就想到了应该可以倍增，因为：

• $n$ 的范围巨大，显然无法直接计算
• 题目中对于转移的限制较低，可能可以转化为统一计算的方案

但是倍增的对象还需要精心选择：

• 如果选择每个木屋的方案数，在统计的时候并不方便，而且时间会超出限制
• 如果选择第 $i$ 天的方案数，则没有有效的转化手段

这个时候应该思考到：什么东西状态量少，可以倍增（可以转移），并且可以导出最终答案呢？

不难发现，如果抛开限制，我们既然每天都要前往湖心岛，那我们就可以把这个时候当作一个节点，从湖心岛出发之后再回来的方案数是可以计算的，还支持倍增

但是考虑到题目中的条件，那就要求我们前一次到达湖心岛与后一次离开必然有一次走短路，所以就可以分类维护出发与回来走的路的种类，然后进行条件转移

最后的答案就是考虑从 $1$ 号房子出发，有多少种方案到达湖心岛，最后一天又有多少种方法可以走到其他房子

收获 & 反思

合理设计倍增的对象，就可以变魔法！

4.3 - 2 - Problem - B2 - Codeforces

思路

因为 $a+b\mid b\gcd (a,b)$ ，两边同除 $\gcd (a,b)$ 后即为 $a^{\prime }+b^{\prime }\mid b^{\prime }\gcd (a,b)$，其中 $a^{\prime }\perp b^{\prime }$

所以也有 $b^{\prime }\perp a^{\prime }+b^{\prime }$ ，所以就有 $a^{\prime }+b^{\prime }\mid \gcd (a,b)$

于是我们就可以枚举互素的 $a^{\prime },b^{\prime }$，，再枚举 $\gcd (a,b)=k(a^{\prime }+b^{\prime })$ 因为要满足：

$$\{\begin{array}{rl}& a=a^{\prime }\times \gcd (a,b)=k{a}^{\prime }(a^{\prime }+b^{\prime })\le n\\ & b=b^{\prime }\times \gcd (a,b)=k{b}^{\prime }(a^{\prime }+b^{\prime })\le m\end{array}$$

所以合法的 $k$ 的数目就是：

$$\min \{\lfloor \frac{n}{a^{\prime }(a^{\prime }+b^{\prime })}\rfloor ,\lfloor \frac{m}{b^{\prime }(a^{\prime }+b^{\prime })}\rfloor \}$$

不难发现这里的 $a,b$ 均大于 $a^{\prime 2},b^{\prime 2}$ ，所以我们只需要在 $\sqrt{n},\sqrt{m}$ 的范围内分别枚举即可，时间复杂度 $O(\sqrt{nm})$

收获 & 反思

善于运用互素结论，可以更好的分析题目

4.4 - 1 - Problem - D - Codeforces

思路

赛时脑子抽了

其实就是一个背包 $dp$，很简单地考虑 $dp[i][j]$ 是只考虑前 $i$ 种字母，其中有 $j$ 个奇数位已经被占据的方案数

记每个字母的数量是 $cnt[i]$ ，字母总数是 $sum$ ，$cnt[i]$ 的前缀和是 $pref[i]$

那转移方程就是：

$$dp[i][j]=\{\begin{array}{rl}& dp[i-1][j]\times \left(\genfrac{}{}{0ex}{}{\lceil \frac{sum}{2}\rceil -(pref[i]-j)+cnt[i]}{cnt[i]}\right)\\ & dp[i-1][j-cnt[i]]\times \left(\genfrac{}{}{0ex}{}{\lfloor \frac{sum}{2}\rfloor -j+cnt[i]}{cnt[i]}\right)\end{array}$$

需要注意其中一些项的转移条件

第二种方法就是，先用数学方法推导发现奇偶性排列的方案与最终字符串排列的方案无关，故可以直接先求出方案数，最后再计算组合数，本质上是一样的

收获 & 反思

需要针对题目选择不同的解决方案

4.4 - 2 - Problem - D - Codeforces

思路

不难注意到，对于最大值我们是一定要选取的，证明如下：

• 如果不选最大值，那么至少会带来一点减益
• 此时去选最大值，最小值一定非降，$siz$ 至多减一，使用一定不会更劣

那么我们就可以考虑枚举我们要取到的最小值，我们可以把每一个数按照大小先排序，然后从大到小加入

我们可以用并查集来维护答案：

• 对于每一个连成一段的区间，我们最优就是每隔一个去选取，并且区间长度为奇数的时候，要从第一个开始选取
• 我们可以记录在这些区间里最大值出现了几次（偶数长度区间就取较大值）然后判断需不需要牺牲一个位置来取最大值
• 每一轮维护之后，答案就是 $max+min+siz$ 这里的 $siz$ 是各个区间统计的可以取到的最多格子数量，并且经过了判断是否需要减一（牺牲一个格子保证最大值）

收获 & 反思

维护最大值能不能被取到的时候，可以维护区间数量而不只是 “能或不能”，这样更方便维护

对于这样取最值的题目，充分考虑性质之后，可以使用动态方法维护 + 枚举部分条件的方法求解

4.4 - 3 - Problem - H - Codeforces

思路

这是经典的 2-SAT 问题，每个元素选与不选就是每个 $a_i$ 的值是 $1$ 还是 $-1$

然后，对应的，2-SAT 问题的子句就是对应的 B 矩阵中的每一个纵列，任何两个元素不能同时为 $-1$

收获 & 反思

学习了 2-SAT

使用 Tarjan-SCC 求解

4.5 - 1 - Problem - E - Codeforces

思路

很简单，一眼就是求 $kth$ 祖先的题目

首先判断，对于两个点，如果他们之间的距离是奇数，一定无解

其次，如果两个点重合，则任意一个点都可行

再次就是，如果两个点深度相同，那么他们简单路径的中点（也就是 $LCA$） 的子树外的所有节点也都可以满足条件

其他的点，也就是有解并且到 $LCA$ 的距离不相等，就只有其简单路径的中点的子树上，除去包含两点的子树后剩下的节点

收获 & 反思

倍增求祖先的简单运用，没什么好说的

4.5 - 2 - Problem - E - Codeforces

思路

赛时没做出来纯糖哇

这是一个 “合理拆贡献” 的好例题，如果不能合理拆分贡献，就会使得这道题很难做（当然你会 NTT 大力出奇迹当我没说）

首先明确题意：对于所有可能的排列，求出所有区间 $mex$ 值的总和

一个很自然的想法是，我们考虑对于每个区间，枚举其可能的 $mex$ 值并且统计对应的排列，但是这是 $O(n^3)$ 的，时间接受不了

所有我们需要改变求解思路，考虑贡献法

这里有一个很巧妙的转化，我们把所有区间的 $mex$ 值总和转化为：

$$\sum _{i=0}^n包含所有[0,i]中的数的集合数量$$

为什么这样是对的呢？不难发现，$mex$ 值为 $k$ 的区间，会对于 $i=[0,k-1]$ 均成立，也就是产生 $k$ 次贡献，所以这样计算是等价的

这是贡献法中的一种 “差分思想”，适用于条件和贡献具有一定单调性的情形

那我们该怎么统计这类集合呢？又该怎么求解呢？

首先我们注意到，如果要满足前 $k$ 个条件，必须要有前 $k$ 个数，并且其中一些数已经被固定了（在数组中给出）

所以我们在考虑区间可行的最大 $mex$ 值的时候，需要注意有没有在数组中的，小于 $k$ 值的数不被包含在区间里，如果有的话，那么我们的 $mex$ 值无论如何也不能超过这个数

换而言之，如果出现在数组中小于 $k$ 的所有数都被包含在了这个区间里，那么只要有足够多的空位，他是可以满足任何 $mex\le k$ 的条件的

所以，我们就可以统计出 $cnt[i][j]$ ，表示数组中小于 $i$ 的数（$i$ 在此取最大值）都在区间里，并且有 $j$ 个空位的区间数量

然后对这个数组进行第一维上的后缀求和，新数组 $cnt[i][j]$ 的意义就是数组中小于 $i$ 的数（$i$ 在此不一定是最大值，只是满足）都在区间里，并且有 $j$ 个空位的区间数量

然后对于 $cnt[i][j]$ ，如果空位数 $j$ 大于等于在 $i$ 前未出现在数组中的数的数量 $need[i]$，就可以排列组合出满足条件的区间，满足条件的区间数就是在 $j$ 个位置中选出 $need[i]$ 个，然后把这 $need[i]$ 个数与剩余的空位分别求排列数相乘，也就是：

$$\left(\genfrac{}{}{0ex}{}{j}{need[i]}\right)\times need[i]!\times (need[n]-need[i])!$$

就这样就做完了

4.6 - 1 - Problem - 1997E - Codeforces

思路

不妨把条件做一下转化：

• 对于第 $i$ 只怪物，如果前面发生过至少 $k\times a_i$ 场战斗，那么怪物会逃跑，否则将发生战斗

那我们不难发现，对于任意时刻，$k$ 大的时候，此时的战斗力一定不会更强，这一点可以使用数学归纳法证明

那么我们只需要计算对于某个位置，$ans [i] $ 记录当 $k$ 至少为多少的时候，战斗无法避免

也就是说，对于 $k$ ，在这个位置之前发生的战斗数量就是此前 $ans[i]\le k$ 的 $i$ 的数量

对于每一个位置，我们可以用树状数组维护并实现查询 $ans[i]\le k$ 的 $i$ 的数量，从而二分求取此处的 $ans[i]$

那么就做完了

收获 & 反思

很巧妙的转化思路，一些可能的思考启发是：

• 对于此类问题，考虑 “什么东西具有单调性”，在此处是每个点处的战斗力与 $k$ 的关系，进而是每个怪物是否会发生战斗与 $k$ 的关系
• 然后就是树状数组的应用，应该考虑到答案可以以什么形式来存储并维护

4.7 - 1 - Problem - D - Codeforces

思路

很巧妙的思路

对于 $n=1$ 特判

对于剩余情形：

• 若 $n$ 为偶数：
  • 我们令前 $\frac{n}{2}$ 个数与后 $\frac n2-1 $ 个数为'a' ，这样保证了所有仅由 'a' 组成的子串出现的次数均为奇数（前后出现次数相差一）
  • 然后令中间为其他任意字母即可
• 若 $n$ 为偶数
  • 与奇数处理方法类似，只不过中间两个字母为任意两个不同的其他字母

构造完毕

收获 & 反思

题目不难，但是思路很优美

考虑构造一个东西是奇数，就可考虑构造两个部分，使得这两个部分一个是奇数，一个是偶数（特别地，可以使得两个部分相差一）即可

4.7 - 2 - Problem - G - Codeforces

思路

很自然的想法是，我们无法确定什么时候可以出发，所以不确定通话在出发后多久开始，所以不妨将整个过程逆转，考虑从活动地点到家里的最短耗时，这样通话区间与出发时间的关系就是确定的了

我们考虑一个最快的流程应该是怎样的：

• 在通话开始前就可以到家
• 在通话开始前下车，在通话结束前步行到家
• 在通话开始前下车，在通话结束后步行或坐车到家

那我们就可以考虑分几个部分来解决问题：

• 先考虑在 $t_2$ 之前，坐车能到哪些位置，此时如果能直接到家则得到答案
• 然后新建一个图作为通话时的情形，建上所有步行边，同时从 $n$ 点向上述坐车能到达的点连一条有向边，长度即为花费的时间
• 再求一轮单源最短路，看看能不能步行到家
• 如果不能，我们就枚举打完电话后上车的位置，在打电话前花费的时间就是 $\max (dis,t_1)$ ，打电话后花费的时间就是坐车到家的最短开销

做完了

启发

对每个过程都做贪心处理，用有限的枚举充分考虑所有情况

4.7 - 3 - Problem - H - Codeforces

思路

用前缀和转化

一个是原矩阵的前缀和，一个是给所有数都乘上顺序权值的前缀和，还有一个给所有数按行乘上权值的前缀和

用这三个前缀和合理组合就可以计算出答案，没什么难的

收获 & 反思

没什么好说的（才不会告诉你 for 循环写锅了一次）

4.8 - 1 - Problem - 765D - Codeforces

思路

不难发现，如果有 $h(g(x))=f(x)$ ，那么令 $x=h(x)$ 就有 $h(x)=f(h(x))$ ，也就是说，$h(x)$ 的取值只能是那些 $f(x)=x$ 的 $x$ 值

然后考虑 $g(h(x))=x$ ，也就是说对于每一个 $h(x)$ 都要有对应的一个 $g$ 值为 $x$

那我们从必要条件入手，对于每一个 $f(x)=x$ 的值，我们建立一个其在 $h(x)$ 中的映射，并且由于第二个条件，对应编号的 $g(h(x))$ 必须等于 $x$ ，此时第二个条件已经完全满足

那就考虑第一个条件，除此之外，每一个 $f(x)$ 都需要被表示，那么就遍历检查：

• 对应的位置如果还没有确定映射关系：
  • 有没有可供映射的 $h(x)$，如果没有就 Fail
• 如果已经有映射关系：
  • 映射的值是否正确，如果不正确就 Fail

如果都满足，那么就是一组合法的解

收获 & 反思

不错的一道思维题，有点绕绕的，最重要的是抓住 “$h(x)$ 的取值只能是那些 $f(x)=x$ 的 $x$ 值” 这个突破口

4.8 - 2 - Problem - F - Codeforces

思路

首先转化题意，即求最大的一个子序列，使得左端点唯一严格最小，右端点唯一严格最大

然后我们将数组转化为二维点 $(i,v[i])$ 手玩一下，不难发现一个贪心策略：如果有 $i<j,v[i]<v[j]$ ，那么 $i$ 做为左端点在任何时刻都是优于 $j$ 的，同理有右端点的类似的贪心策略

也就是说，对于这样的 $i$ 和 $j$ ，$j$ 是一定不会作为左端点的，这是一个类似于单调栈的结构，于是我们可以筛选出所有可能作为左端点（右端点）的点

然后我们考虑一个点可以在取那些左右端点组合的时候产生贡献：

• 由于所有可能作为左端点（右端点）的点是单调的，所以这个贡献区间一定是形如 $[l1,r1],[l2,r2]$ 这样的连续区间
• 那我们统计贡献就可以转化为将其中一维化为坐标轴，对另一维扫描线计数，线段树维护最值即可

做完了，思路，，，好神奇，好优雅

收获 & 反思

很优美的思路，我可能还没办法总结出什么，但是有以下几点：

• 考虑可能的贪心，他可能带来让问题变得可解的关键性质
• 善于应用单调栈
• 善于考虑贡献的转化，能否用贡献求解
• 对于形如在两个维度上的连续区间的限制，可以转移到 “对一个矩阵区域有贡献” 上，进而可以使用扫描线处理（以其中一个维度作为坐标轴）

4.9 - 1 - Problem - 1666E - Codeforces

思路

看到求可行的最值，考虑二分

首先是二分路段的最大差值 $\Delta$，然后考虑能不能 check ，怎么 check ？

显然我们可以枚举这个差值下，路段长度的上下界 $[l,l+\Delta ]$

然后对于这个上下界，我们显然是可以判断出可行性，并且若可行，我们可以逆过来求出一组合法的解的

同时不难发现，如果不可行，必然是因为太长 / 太短，这是什么？这是宝贵的单调性啊！

也就是说，我们可以通过二分 $[l,l+\Delta ]$ ，来完成对 $\Delta$ 的 check

就做完了

收获 & 反思

"Stop learning useless algorithms, go and solve some problems, learn how to use binary search."

4.10 - 1 - Problem - 1458C - Codeforces

思路

这个考虑非常巧妙！！！

我们将每一个矩阵中的元素记作一个三元组 $(i,j,va{l}_{i,j})$ ，这样就完全表示了矩阵中的每一个元素

那么就不难发现，每一个元素在对应操作下的 “去向”：

• $L/R$ ：$(i,j\mp 1,va{l}_{i,j})$
• $U/D$：$(i\mp 1,j,va{l}_{i,j})$
• $I$ ： $(i,va{l}_{i,j},j)$
• $C$ ： $(va{l}_{i,j},j,i)$

于是我们记录这些变化的复合，最后对于每一个元素应用变化，就可以得到目标矩阵

收获 & 反思

如果发现对于一个矩阵上的元素很难维护 “每一个位置上的数”，不妨转而维护 “原来的数变成啥？都去哪了？”

这对于一些有固定变化方式的运算有奇效

值得好好学习的一道题！

4.11 - 1 - Problem - B3 - Codeforces

思路

关注到一个很重要的点：每一列有且只有一个房子，并且距离是在 $[0,n]$ 中任取

那么我们从第一列开始考虑，把第一个数放在 $(1,1)$，就有如果 $a_i<i$ 那么一定可以找到之前的某一列，和他直接匹配上，否则，就一定可以找到一个位置，和 $(1,1)$ 成功匹配

这样子我们就可以把之后的所有房子都成功匹配，但是问题来了，第一个房子怎么办？

很容易想到的是，如果数列中有某一个 $a_i=0$ ，那么把它放在第一个就可以让他和自己匹配

如果没有 $0$ 呢？也不难注意到，两个 $a_i$ 相同的话，把他放在第一和第二个，他们之间可以互相满足，也解决了第一个的问题

最后，如果没有 $0$ ，也没有重复，那就是一个 $[1,n]$ 的排列，这个时候我们去手玩一下，发现：

• 如果 $n\le 2$ 那么无解
• 否则，可以让 $1,2,3$ 分别位于 $(2,1),(3,2),(1,1)$ ，这样使得第一个可以合法匹配

到这里就做完了

收获 & 反思

需要注意条件的特殊性质，比如：

• 每一列有且仅有一个
• 根据 $a_i$ 的大小一定能找到解
• 构造特殊的开头使得第一个房子得以匹配

4.11 - 2 - Problem - D - Codeforces

思路

一个很自然的思路是，如果 $k$ 小于等于 $\lceil \frac{n}{2}\rceil$ 的话，我们可以直接把第一个摊位设为 $n-k+1$ ，第二个摊位设成 $1$ ，这样就一定满足条件

此外，如果 $k$ 大于这个数，那么我们可能整出的商品总数一定只能是 $n$ ，因为除此之外最大的就是把第一个设为 $2$ ，第二个设为 $1$ ，结果并不会比 $\lceil \frac{n}{2}\rceil$ 来得大

所以除了这两种情况就是无解

收获 & 反思

又是一个充分条件入手证明必要性的构造题

4.12 - 1 - Problem - E - Codeforces

思路

其实很简单：

• 不难注意到，其中的最大值一定同时作为（最后一个）前缀最大和（第一个）后缀最大出现
• 同时，第一个和最后一个也一定是前 / 后缀最大值
• 也就是说，不满足上面两个条件的，就一定是不合法的条件组

那我们考虑，其余情况都有合法的解吗？如果是，我们怎么统计解的总数呢？

我们首先明确，最大值左边显然不会有后缀最大值，同样的右边不会有前缀最大值

那就是把左右两边分开求解了，这种情况下，由于没有重复元素，所以无论怎么分配都是等价的

那我们只考虑其中一边，以前缀最大值为例：

• 既然已经确定了后一个前缀最大值在位置 $p_{i+1}$ （最开始的时候就是最大值的位置），那也就说明前面还有 $p_{i+1}-1$ 个数，再考虑前一个前缀最大值
• 因为前一个前缀最大值是往前首个前面没有任何数比他大的数，所以前面所有数中的最大值不能在他前面，也不能在他后面，所以他就是前面所有数中的最大值
• 那么还剩下 $p_{i+1}-2$ 个数可以被支配，且他们都比选出的数小，那方案数就是从中任选 $p_{i+1}-pi-1$ 个数随机排列放在前后两个前缀最大值中间
• 再往前也是一样的子问题形式，只需要将左右方案数都求出来，最后乘上最开始分配两边数的方案数即可

至此问题得解。

收获 & 反思

考虑把问题分解为子问题，不重复不遗漏，最简化问题建模，这是需要大量训练的

手动取模又出锅了调了快一个小时，我是傻逼

4.13 - 1 - Problem - E - Codeforces

思路

其实算是一道性质观察题？

我们不难发现，第一个放置的元素有一个特殊性：他将自己作为 “开销”，所以可能出现一个情况，就是虽然两个数的最大公约数是 $1$ ，或者一个很小的数，但两个数都很大，不管哪个放在第一个都不是一个很好的方案

那，我们是不是应该把最小的放在第一个呢？

我们考虑把这个感性的认知定量分析一下，假设 $m$ 是其中最小的数，$a$ 是任意其他数，就会有

$$\begin{array}{rl}m+\gcd (m,a)& \le m+\gcd (m,a-m)\le m+(a-m)\le a\end{array}$$

也就是说，把最小的数放在第一个一定是最优的

除此之外，我们还会利用一个 $\gcd$ 的重要性质 —— $\gcd$ 只会下降不超过 ${\log }_2$ 次，所以我们只需要进行 ${\log }_2$ 次以内的枚举，每次选择使 $\gcd$ 下降最多的元素填入，知道任何元素都无法再使得 $\gcd$ 下降为止，此时剩余的元素的贡献可以一并计算

收获 & 反思

善于观察，利用已知的结论和性质，对一些感性的 “贪心” 思路辅以证明，就可以光明正大的耍流氓了❤

4.14 - 1 - Problem - G - Codeforces

思路

一个很朴素的想法就是判断有没有负环，然后跑最短路

但是我们把目光放在题目的特殊条件上：

• 为什么 $x$ 只能是奇数，这是为了维持什么性质呢？
  • 边权的反对称性：一条路径倒着走，所有边的权值都变成了相反数

我们考虑这有什么特殊性，很自然会想到，如果有一个正环，那么倒着走就变成了负环

而只要有一个负环，我们就能走出负无穷，所以所有的环只能是零环

零环有什么性质呢？

• 环上给定两点间的所有路径长度均相等

在这个网格图中，不难发现，只要所有小方格都是零环，那么整个图就都是零环，换句话说，点到点的距离就具有 “势能” 的特性

所以，我们只需要检查所有小方格是否都是零环：

• 若是，从任意节点跑出所有点的势能，查询时输出答案
• 若不是，则是 “INVALID”

收获 & 反思

要特别关注题目中给出的特定条件，一定不是乱给的啊，都是 “有备而来”（马老师音）

需要洞察到 “零环” 与图的保守场特性之间的关系

4.15 - 1 - Problem - H - Codeforces

思路

一个很简单的二分答案，带一点点复杂度分析

题目的要求是求出特定 $x$ 下的最小中位数，不难发现，我们尽量地进行操作一定不会使答案更劣

所以 $a_i$ 在 $x$ 下的最终取值就是 $a_i\mathrm{mod}x$

那我们就可以二分整个中值，看看数组中是否有足够多（多于一半）的元素在对 $x$ 取模之后小于等于 $a_i$

每次枚举的开销是 $\lceil \frac{n}{x}\rceil$ ，我们再在 $[1,n]$ 中枚举 $x$ ，就可以知道时间复杂度约为 $n{\log }^{2}n$ ，其中一个 $\log$ 来自调和级数，另一个 $\log$ 来自二分

收获 & 反思

大概就是，嗯，没什么好说的，二分答案嘛，做不出来就该艾草了

4.16 - 1 - Problem - G - Codeforces

思路

哇还有匹诺康尼

其实是一道经典的扫描线，但是我脑子和傻逼一样

看到环考虑断环为链，然后就考虑把区间按左端点排序，当枚举的断点处在区间内的时候，把道路换为其补集

答案就是取每个点处的开销的最小值，开销的量就是 $n-1$ 再减去此时未被路径覆盖的道路数量，也就是区间上 $0$ 的数量

当时觉得不好维护，然后发现区间上的数一定非负，那只要统计最小值及其个数就好了

收获 & 反思

线段树可以维护最小值及其个数，但不好维护特定值的个数

4.17 - 1 - Problem - D - Codeforces

思路

还是一个二分答案，但是它的 Check 很巧妙

我们需要注意到一个性质：

• 每个删除区间的长度都是 $k$ 的倍数
• 所以每个保留下来的格子的编号在 $\mathrm{mod}k$ 之后一定是 $1,2,3\cdots$

基于这个特性我们就可以 $O(n)$ Check：

• 设会剩下 $m\le k$ 个元素，在设 $dp[i]$ 是取了前 $1,2,3\cdots i$ 这些元素时，其中最多的大于等于 $mid$ 的元素数量
• 对于对应下标为 $x$ 的 $i$ ，转移就是：
  • 如果当前元素大于等于 $mid$ ，$dp[x]=dp[x-1]+1$
  • 否则 $dp[x]=\max (dp[x],dp[x-1])$
• 最后看 $dp[m]$ 即可

收获 & 反思

动态规划作为 Check，并且有特殊性质

手玩几遍还是很有必要的，需要去看一些解题方法论了

4.18 - 1 - Problem - 1680D - Codeforces

思路

其实很简单，就是考虑一下贪心，我们的答案取决于最大值和最小值的差，那我们就尽量为最大值和最小值做贡献

注意到 $n$ 只有 $3000$ 于是可以暴力枚举 $n^2$ 次，考虑所有可能出现的最值位置

同时注意到，最后能回到原点，相当于所有的 $a_i$ 之和为 $0$ ，也就是所有填入的数的总和是固定的

那我们只需要在保证能凑出总和的同时，在最大值处之前尽量多 $+$ ，在最小值之前尽量多 $-$ ，用前缀和算出此时的最值更新答案即可

收获 & 反思

枚举答案来检查，没什么好说的，注意枚举不要遗漏即可

4.19 - 1 - Problem - 1442D - Codeforces

思路

首先可以观察到，至多只会有一个数组是 “不完整的”，也就是取了并且没取完的，原因如下：

• 如果有两个不完整的数组，放弃其中数字小的那一个，选数字大的一个，一定不会更劣

也就是说，我们可以考虑 $dp$ ，按照是否取过一个不完整的数组来分别转移

但是这样子时间复杂度是 $O(k\sum t_i)$ 的，所以一定要考虑优化

我们思考，是什么东西贡献了大量的开销呢？不难发现是每次对 “不完整数组” 的转移，因为完整数组只有 $1$ 个，而不完整数组有 $t_i-1$ 个，并且最后恰好凑齐 $k$ 个数的几率是很小的

一个很自然的优化想法就是，我们把不完整数组放到最后转移，这样对于大小为 $siz$ 的不完整数组，就只需要枚举一次 $dp[k-siz]$ 来转移，因为只有这样才能最后得到大小为 $k$ 的集合

这里的 $dp[i]$ 是除了这个不完整的数组之外的所有数组组成大小为 $i$ 的子集的最大总和，由于我们要枚举每一个数组作为 “不完整数组” 的情形，所以我们需要 $n$ 个对应的 $dp$ 数组，现在的问题就是怎么高效求取 $dp$

不难发现，对于 $d{p}_1$ 我们使用了 $2,3,4\cdots$ 来转移，也就是说每一个 $dp$ 都是少了某一步转移的产物，那就可以考虑 “批量转移”

具体来说，就是用线段树进行分治，对应 $[l,r]$ 区间的节点就是不进行 $[l,r]$ 这部分转移的 $dp$ 数组，这样一来每个数组最多贡献 $\log n$ 次转移，总的时间复杂度就是 $O(kn\log n+\sum t_i)$ ，是可以接受的

收获 & 反思

又一道考虑优化的 $dp$

又一道使用线段树优化转移 / 修改的题目

很色情啊

4.19 - 2 - Problem - G3 - Codeforces

思路

首先不难发现，我们如果要把原图分成两部分，要么是直接按连通块分，要么选择的连边只能是割边（桥）

那上来就是一个边双连通分量缩点！

再来一个简单 DFS 处理成若干棵树！

根据开销的计算方式不难推出，两部分的差值应该尽可能小

在缩点后的森林中，我们相当于可以选取若干棵树和其中至多一棵树的某棵子树来作为监狱的一部分

那就可以考虑 $dp$ ，直接转移的话，T 掉的可能似乎不小......

于是有请 —— bitset

这样一来时间复杂度就能被常数草过去了

收获 & 反思

第一次接触 bitset 优化 $dp$ ，该再去找点题目做做

4.20 - 1 - Problem - 525E - Codeforces

思路

直接爆搜的时间复杂度是 $n\times 3^n$ ，显然是会爆掉的

所以选择进行一个 meet in middle 时间复杂度来到 $n\times 3^{\frac{n}{2}}$ 可以草过去了

收获 & 反思

能暴力硬草就不要再想其他东西了

时间复杂度分析出来是正确的，就是可以耍流氓了

4.20 - 2 - Problem - D - Codeforces

思路

发现 $n$ 只有 $18$ ，所以可以暴力枚举所有情况

同时不难注意到，对于连续的一段改变的区间，我们一定可以通过若干次操作把它变成全为区间长度，这是取 $mex$ 后的最大化策略

同时我们可以通过递归来生成对应的方案

那解法就很显然了：

• 先枚举情况，计算最优方案的样式（保留 / 取为 $mex$ ）
• 然后对于最优方案，递归生成一个可行的操作序列

收获 & 反思

暴力硬草

4.21 - 1 - Problem - D2 - Codeforces

思路

首先注意到，假设每个数组中第一个未出现的整数是 $m$ ，第二个没出现的整数是 $M$

那么就会有：使用第 $i$ 个数组来转化，如果数字是 $m$ 那么会变成 $M$ ，否则就会变为 $m$

我们可以据此构建一个有向无环图 （DAG）

考虑一个数字在这样的规则下，可以怎样转化？

• 首先，如果一个数字属于 $m$ ，那么他一定可以转化为直接从这个 $m$ 出发达到的最大的数（DFS 查找即可）
• 同时，它还可以变为其他的 $m$ （不是他本身）：
  • 如果其他的 $m$ 只有一条出边（就是它对应的 $M$ ）的话，就无法继续走下去了
  • 如果有至少两条边（两个数组的 $m$ 都是这个值 ），那就可以利用其中一个完成转换，然后变为 $M$ ，也就是可以任意选择
• 如果不属于 $m$ ，就只能通过后者转换

于是我们统计有至少两条出边的 $m$ 能到达的最大值中的最大值记作 $m_{max}$ ，那么答案就是在 $m_{max}$ 与（如果属于 $m$ ）之间做选择，还要考虑什么都不做的情况，在大于一定数值之后这将绝对最优，直接对剩余部分等差数列求和即可

收获 & 反思

没有什么思路的时候，应该要所有情况都列举一下，说不定会发现问题会简单很多

4.21 - 2 - Problem - F - Codeforces

思路

考虑什么情况下一定无解：

• 对于任意集合，要么是其他集合的子集 / 超集，要么与其他集合无交集
• 换句话说，如果我们把集合从大到小排序然后一一检查，假如一个集合后仍然无解当且仅当这个集合与前面所有集合均为 “要么是子集，要么无交集” 的关系
• 也就是说，这个集合里的所有元素在此前都是同时出现同时不出现的

这就启示我们使用异或哈希来解决问题：

• 把每一个人映射为一个大整数
• 将每个爱好此前的出现情况定义为异或和
• 如果新考虑的一个人的所有爱好的异或和一样，就可以判断所有的爱好在此前同时出现 / 不出现，也就是无解，此时更新爱好的出现情况，继续查找
• 如果有两个爱好出现情况不一样，也就意味这在此之前一定有某个人只喜欢其中一个，并且因为从大到小排序，这个人一定还喜欢至少一个不在当前集合里的爱好，即一定有解

至此解决完毕

收获 & 反思

上一题的收获依旧适用：

• 没有什么思路的时候，应该要所有情况都列举一下，说不定会发现问题会简单很多

还有就是异或哈希的巧妙应用

4.22 - 1 - Problem - G - Codeforces

思路

简单的反悔贪心经典模型，没什么好说的

4.23 - 1 - Problem - G2 - Codeforces

思路

首先是要学会处理后缀函数，使用 Z Algorithm ，处理之后我们考虑怎么求取答案

显然直接逐个求取是会爆 T 的，我们考虑反向枚举 $LCP$ 的长度 ，然后再去求这个长度下最多能被分成几块，时间复杂度就是调和级数级别的

对于每一个枚举出来的长度，我们可以将 $LCP$ 长度大于这个的坐标加入 set ，然后在这里面二分查找即可

收获 & 反思

尝试转化问题，去获取正确时间复杂度的做法

善于运用二分

4.24 - 1 - Problem - F - Codeforces

思路

想了很久也没有想到应该怎么做，因为好像没有一个特别方便和正确的判断合法三角形方案的方法

于是考虑逆向思维，什么时候不存在合法方案呢？不难发现最劣的情况将形如斐波那契数列，再通过打表得知 $50$ 个数再往上一定有解

那小于 $50$ 个数，我们就可以暴力求解：

• 需要注意到将一个数列排序之后，若存在一个三角形，则一定存在连续的三个数组成三角形
• 对应的，要有两个三角形，就要求取出一个三角形之后一定存在连续的三个数，那就有两种情况：
  • 一是原序列中的三角形也是连续的三个数，且与另外三个区间不相交，可以直接枚举处理
  • 二是两个序列 “缠在一起”，形如 $112212$ 这样的，我们可以枚举连续的长为 $6$ 的区间来处理
• 于是就可以在 $O(50^2)$ 的时限内解决问题

收获 & 反思

尝试逆向考虑问题，考虑可能的上界 / 下界

需要掌握 “将一个数列排序之后，若存在一个三角形，则一定存在连续的三个数组成三角形” 的性质

4.25 - Problem - G - Codeforces

思路

一个小模拟，需要考虑合适的方案处理数据：

• 用模拟的栈来处理，考虑当前每一批牛奶将产生怎么样的贡献
• 每一批牛奶处理其 “消耗完” 和 “过期掉” 的时限，在此之前他就可以一直 “供应上”
• 如果这个时限超过了下一批牛奶的时间，就先消耗一部分，然后引入下一批牛奶
• 如果消耗之后不满足一天的量，就记在 $res$ 里面，这是一个常用的小技巧，但是需要考虑清楚情况

收获 & 反思

分类处理和留出的节点的数量需要有一个平衡，任何一方过分都会使操作麻烦得多

4.26 - 1 - Problem - H - Codeforces

思路

线段树的一道好题，原题题意等价于维护一个集合，求集合中足够长的一段全 $0$ 区间的最小左端点

显然权值线段树是可以维护这个数据的，每次查询只需要做一个 $FindFirst$ 就好了，时间复杂度 $O(n{\log }^{2}n)$

收获 & 反思

做之前好好考虑一下方法对不对

“人类对线段树的开发不足 $1\%$”

4.27 - 1 - Problem - F - Codeforces

思路

题意可以转化为：求 $A$ 图连通块的数量和 $A\cup B$ 图中连通块数量的差值

那我们就可以考虑将查询离线，对每条边划分 “生命周期”，然后线段树分治

具体就是：

• 将修改 & 查询全部挂载到线段树上
• 在线段树上 DFS 遍历，使用可撤销并查集维护连通性
• 在每个节点处统计答案

收获 & 反思

学习了可撤销并查集

拓展了线段树分治的 “业务范围”

4.28 - 1 - Problem - G - Codeforces

思路

主要还是利用线段树分治来挂载修改和查询，然后利用可撤销并查集维护

具体是需要维护偶数环的数量

具体维护方式有点巧妙：

• 因为考虑到最后会是一个基环外向森林，所以每棵树上最多只会有一次成环
• 所以我们可以使用带权并查集来维护集合内节点之间距离的奇偶性，在成环的时候就可以判断是奇数环还是偶数环了

收获 & 反思

可撤销带权并查集，线段树分治，基环外向森林，树上染色，闹麻了

4.29 - 1 - Problem - G - Codeforces

思路

巧妙的并查集好题

我们不难发现将 $A\&B$ 合并之后，绝对值不超过 $k$ 的组内可以随意交换，最优策略就是取每组最大的那些数

于是我们可以将查询离线化，然后按照 $k$ 从小到大处理，每次合并并查集，并更新答案

但是有一个小问题：我们如何维护每个集合内的最大若干值呢？

很简单，直接使用 set 模拟对顶堆并且维护总和

• 容易证明，每次集合合并的操作量不会大于小的那个集合的体量，所以总开销是线性的
• set 操作一定要注意先判断是否为空

收获 & 反思

set 的妙用

离线处理的魅力喵

4.30 - 1 - Problem - D - Codeforces

思路

考虑了蛮久的，发现其实很简单

因为只有两次 $True$ ，所以可以判断只可能是 $0\to 1\to 0$

每个限制条件可以看作是拓朴排序中的要求，同时要求不同类型的操作有序进行

加上一点点贪心 & 特判，就可以草过去了

收获 & 反思

还是建模能力不够

还是太傻逼了

题做少了