2025 长训第一周 (0922 to 0929)

0922~0923 是行程日。

0924

「序列」相关问题

LOJ 6490

「最大子段和」一类的问题，常用手法是使用分治结构解决。

CF585E

通过各种数论知识将其进行简单处理，最后使用狄利克雷前后缀和解决问题。

LOJ 2876

发现连边后是一个经典的生成树问题。

可以考虑给地图按照最近点染色，然后色块边缘可以考虑给两个色块所属的根源进行连边，这样子就能避免完全图连边复杂度过高的问题。

CF1748E

是一个笛卡尔树结构。

AGC006D

遇到中位数相关的问题，套路地考虑 “钦定 $x$ 并对数进行「离散化」”。

LOJ2332

发现只有每个相邻项的差值会对答案造成互相独立的影响，那么只需要考虑加的区间的边界情况即可。

0925【模拟赛 #1】

模拟赛总结

赛时 T1 做了很久，因为比较抽象地使用了【哈希】求小区间代表的是哪个数。并且还因此忘记了一个特判，挂了 70 分。

写完 T1 大概过了一个小时。因为刚睡醒比较困。

然后开始做 T2，发现 T2 可以直接做，写了十几分钟就写完了。

然后开始做 T3，先写了个 $O(n{\log }^2)$ 的做法，发现过大样例要好久，又好像可以简单枚举优化，但是不太想想枚举，于是就跑去做 T4 了。

T4 看了一眼，发现可以框框过掉正解之外的 Subtask，于是就写了。

最后只剩下不到半个小时，把 T3 的枚举写出来之后发现没过大样例【其实是忘记了右端点对齐的情况也是需要判定的】，然后就结束了。

期望 $100+100+84+72=356$，实际 $30+100+37+72=239$。

三分常数太大了。ohno。

总结一下，感觉这场赛还是过于简单了？

做题的时候要注意细节判断，思路要缜密一点。

对于自己感觉【容易错的题目】，要多去检查有没有什么需要的细节判断。

感觉时间还是有点不够用，最主要的是做 T4 部分分的时候比较摆，以及做 T1 的时候比较摆。

策略上还需调整时间分配。

模拟赛 T1

考虑处理出对于两个序列的最长公共前缀长度与最长公共后缀长度。然后我们所选择的区间一定包含所有不在公共前缀/后缀的地方。

由于求数位和之后，最多只有 $9\times {10}^5$，也即只有 $6$ 位，所以我们可以直接枚举较短序列中哪些是数位和变来的。

然后通过长序列中的数位前缀和辅助即可求出某区间是否合法。

注意长度相关判断，以避免前导 0 造成的影响。赛时 $100\to 30$ 了。

模拟赛 T2

观察到两个 artist 能被区分，当且仅当他们出现的轮构成的集合不同。

关于这点，可以使用随机赋权和哈希快速判断。

一个 artist 能被分辨出来，当且仅当某轮后，没有与它出现的轮构成的集合相同的。

记录 map 中哪些位置发生了变化再一个一个 check 一下即可。

模拟赛 T3

观察到题显然可以二分。

然后，二分得到交集长度 $x$，不妨枚举区间 $[i,i+x-1]$，我们需要挪动每个区间使其包含 $[i,i+x-1]$。类似于一个问题：

给定数组 $a$，求使得 $\sum |a_i-x|$ 最小的 $x$。

我们发现它是单峰的，于是到这里可以三分求解。复杂度是 $O(n\log n\log w)$ 的。

但是我们可以直接枚举，$i$ 扫一遍过去，动态维护挪动所需 cost。容易发现答案只会在枚举的左/右端点与某个原有区间的左/右端点相同。在这些点判断是否存在满足条件的 cost 即可。

模拟赛 T4

问题可以看做操作使得区间不交（对于一些特定情况允许交 1 个元素）的最小操作次数。

不妨先按照总和排序。

设 $d{p}_{i,j}$ 为：截止第 $i$ 个人，在确认前面所有人的排名之后，右端点为 $j$ 时最小需要操作多少次。

然后考虑每个人能做什么转移：显然我们可以得出每个人能拼出的数字，也就能得出每个人能拼出的区间。使用背包，复杂度 $O(n{m}^{3}k)$。然后根据得出的就可以对 $dp$ 进行转移了。

但是还不能过，我们观察发现每个有用的区间左端点必须 $\ge$ 上一个人的数字总和，于是利用这一点对背包进行剪枝，然后就可以在 $O(m^{3}k\log k)$ 的时间得出这些区间。

然后就能过了。

0926

听了【括号序列】有关的课，以及【介值定理】。介值定理感觉挺有趣的？

都在另外的文章里面了。

0927【模拟赛 #2】

模拟赛总结

边吃鸡蛋饼边赶到教室。今天竟然没有迟到！

这一场打的很莽。

开局看 T1，写完代码发现看错了题，此时是 20min 左右。

然后发现本质上做法差不多，然后 40min 左右就过了样例。

然后 T2，想出了要倒序处理。

然后经过一会想到了 $d{p}_{i,l,r,x}$ 表示已经到达的区间为 $l,r$，目前在 $x$ 的方案数。

然后发现会算重复，不知道该怎么办。

后面想到了可以直接只管左右边界有扩展的，然后预处理一下可达性就行了，每次转移跨几个 $i$。

状态是 $d{p}_{i,l,r,0/1}$。

但是写起来有点史。然后 11:00 的时候写完了，但是没过样例。

于是红温了，直接弃疗，因为写出来也是暴力分。

然后后面也没认真打了，象征性地打了几个个位数分数的 subtask。

其实我的状态甚至再优化一点就是正解：只需要注意到我们只关心区间的长度就行了。

总结一下：

心态上还是要稳住啊。就算没有注意到正解，暴力能打还是要打的，以及多在状态信息取舍上想一会。

很难保证赛场上我会不会也像这样红温。

就算我没有写出 T2 正解，把那个暴力写了好像也有比较可观的分数。

不过这场的打法还是有点太冒险了：死磕 T2 导致 T2 打不出来之后直接红温，没有心思打 T34 暴力。

T3 甚至连想都没想，后面在听讲评的时候走神乱猜的结论居然还是对的，这 $O(k^2)$ 分数赛场上如果有认真去做的话肯定能拿到的。

总结就是：在难度大一点的时候，要能意识到暴力也是区分度的重要成分。不要死磕。

T1T2 感觉最多不能用两个小时，撑死 2.5 小时，不然心态太容易炸了。

模拟赛 T1

不难发现，我们肯定是先造出一个全 1 行，再用它去填充整个矩阵。

那么我们枚举每一行去看，以那一行为全 1 行的操作数。

全 1 之后填充整个图的操作数是显然的。只考虑一下全 1 之前。

首先如果存在一个列的第 $i$ 个值为 $1$，就可以直接用它填充，花费白点个数。

否则我们肯定可以先造一个列的第 $i$ 个值为 $1$，再填充，花费白点个数 $+1$。

然后加上全 1 之后填充的方案数即可。

模拟赛 T2

这种“填色，会覆盖”的问题套路地考虑倒序考虑。

显然填色了的是一个区间。

为了计数不计重，我们只在被填色的区间扩展的时候进行转移，这样可以防止点在内部走的时候也被计算方案。

那么我们可以设计一个粗略的方程：

设 $d{p}_{i,l,r,0/1}$ 表示直到倒数第 $i$ 种颜色，扩展区间为 $l,r$，目前在左端点还是右端点的方案数。

然后转移的话，对于 $i$ 枚举 $j>i$，检查新状态是否能从当前状态通过【只在限制区间内移动】的方式移动到某个地方，最后一步进行扩展。这个可以预处理一下。

如果能从当前状态进行移动到达目标状态的话，就贡献过去。

考虑优化，我们发现，我们并不关心 $l,r$ 的具体值，只关心区间的长度是多少。于是就能压缩一下了。

然后复杂度就变成了 $O(n^2{m}^2)$ 了，然后就能过了。

注意最后统计答案的时候不要忘记：长度为 $i$ 的区间贡献系数为 $m-i+1$。

以及从 $i=1$ 向别的地方转移的时候需要特判，因为这个时候同一个区间，从左往右与从右往左都是本质相同的，只要能从其中一种转移过去，另外一种就不要重复转移了。

模拟赛 T3

首先感性理解，选出来的答案的概率肯定是单调不增的。

其次可以用调整法证明，选出来的一定是一段前缀和一段后缀。

结论是 $L+R\ge 1$ 的时候扩展左边，否则扩展右边。

证明写在这里有点冗长且不必要（其实扩展哪边的结论必须得通过证明过程才能得到）所以就不写了。

另外，同个概率的数，要么只选一个，要么全都选，要么全都不选。（选一个和选多个后 $L+R$ 是相同的）所以枚举的时候判断当前加入与前面的 $L$ 相不相同，相同就把剩下一段相同的全部加进去即可。

详细证明见 P4110。

模拟赛 T4

P12559