唐诗学校，还有宿管，晚上 $9:30$ 下课，$10:30$ 就熄灯，还是感叹我们学校的好。

第一天打得 NOIP 模拟赛，鉴定为打得太唐了。

发题。

浏览所有题目，发现都不是特别好做。但是 $B$ 题是原题，并且赛时还过了，那不直接拿下了？（埋下伏笔）。

思考了一会儿 $A$ 题，会了 $\mathcal O(nV)$，然后速速写完 $B$ 题，检查了一会儿就继续做 $A$ 题了。

首先思考了一下 $A$ 题最优情况下的形态，于是想到记录从上一个不变的位置 $\pm$ 了多少个 $d$。遂先打了一个 $\mathcal O(nV)$ 的暴力，然后实现了一下 $\mathcal O(n^3)$ 的想法。然而对拍一秒就出错了，于是一直打补丁，但是仍然不行。

继续对 $A$ 进行打补丁，但是大数据仍然一拍就错。有点慌了，先去看后面的题。

看了一下 $C$ 题，发现显然可以用 KMP 预处理加上状压 dp，环可以固定一个位置作为第一个串，最后处理一下就行了。

但是有点难写，准备再想想 $A$ 题。

突然想到在 WC2025 的 $C$ 题遇到了与 $A$ 题类似的情况，当时也是一个 $\mathcal O(nV)$ 的 dp，但是实际上第二维可能取到的最优值是有限的，因此可以将第二维离散化，复杂度就变成了 $\mathcal O(n^2)$。

然后再联想到之前错误的做法，观察到最有情况下的结构，只可能是某个 $a_i\pm kd$，其中 $k\in [-n,n]$，因此值域就被离散化为了 $\mathcal O(n^2)$，总复杂度 $\mathcal O(n^3)$。

过拍的时候还是比较激动。

突然忘记 KMP 了，于是想着先打一个 $D$ 题暴力，结果打得太慢，直接结束了？？？

100+20+0+5，$B$ 题之前做法假了，挂成了 $20pts$。

这场比赛能够沿用之前做过的一些题目的一些技巧，值得继续保持，但是这场 $A$ 题做的确实稍微有一些久了，争取能想清楚再写代码，不然花费大量时间在错解上很亏。

数据结构选讲，题目都还不错，有几道苟王分享过的原题，$\mathcal O(\log n)$ pushup 的线段树还是比较经典，之前做的并不多。最后一题的容斥启发也比较大。

树上问题选讲。问题都比较经典，然后了解到了一些“经典”的贪心（和 Aaron_Romeo想了很久，nikangle给出了证明）,事后和lm发现并不是很难猜到。

还有就是了解了一下长剖，我寻思着集训队论文LHF就是写的长剖，这东西真能考到？不过用来优化有关深度的 dp 还是很妙，可以直接从 $\mathcal O(n^2)$ 优化到 $\mathcal O(n)$。

NOI 模拟赛？$B$ 题不是纯纯糖题？想了一会儿就会了 $\mathcal O(m\log m)$，就是求一下内向基环树森林上两点的距离。但是发现过不了大样例，检查出来求两个点都在树上时有些问题，似乎需要求 LCA，然后就花了一些时间写了一下 $\mathcal O(1)$ 求 LCA。然后就 $10:20$ 了。

接着就在 $A,C$ 两题反复横跳，发现 $A$ 题怎么计数都不对，无法记录当前还有几个人没有满票，然后就似在了这里。$C$ 题一开始只会做 $k=r-l+1$，然后似乎可以 $\mathcal O(n^3)$。显然可以二分，但是没有进一步的思路。

于是就继续想 $A$ 题。$11:20$ 开始打暴力，并且意识到 $D$ 题 $\mathcal O(n^3)$ 的做法是假的，赶紧补了一个 $\mathcal O(n^4)$ 预处理，$\mathcal O(n^2)$ 的东西。

估分 $10+100+25=135$

下午来看，$B$ 题 $TLE$ 了，$100pts\rightarrow 60pts$，有点离谱。然后加了一个快读，还是 $T$ 了。突然想起来数组开得有点大，于是就只将求 LCA 的部分开了两倍空间，竟然快了 $1s$。

警示：千万不要图省事将所有数组大小开大，该开多大就多大！不然会收获意想不到的常数。

若干道 Ad-hoc，确实是杂题选讲了。

dp 优化第一讲。

其中大部分题目是观察题目性质并对于 dp 状态进行优化，比较困难，极具技巧性。

其中比较常见的两个优化方向是：可以跳过 dp 过程中某些无效的状态，从而缩减状态数；也可以对状态进行简化，只记录后面需要用到的信息。

还有的时候需要比较惊人的注意力和对题目性质的分析，这些题目就比较困难了。

附：被 Desant 这题搞红温了。

这题一开始记录了前面的数选没选，状态是 $2^n$。经过对于逆序对统计需要的信息的考察，将其压缩成若干段区间的数选了多少个数，发现状态数直接变成了 $3^{\frac{n}{3}}$，然后总复杂度就变成了 $\mathcal O(n^23^{\frac{n}{3}})$。

loj 上哈希表存状态只有 1e6+7 这个模数能过，luogu 上死活过不去。不过可以类似状压用一个整数存状态，那确实应该快得多。

dp 优化第二讲。

今天的题目大部分是针对转移的优化。第一题是 DP 套 DP 经典题目小N的独立集，观察到如果将 $f_{i,1}$ 的值表示为选或者不选 $i$ 号节点的最大独立集，那么就有 $0\le f_{i,1}-f_{i,0}\le k$。于是内层需要记录的状态就从 $n^2$ 优化到了 $nk$，总复杂度 $\mathcal O(n^2k^4)$。

后面几道题都有一定的难度，其中有一道题目ljr学长分享过，是关于优化dp转移和决策单调性的。

又是 $4$ 题，NOIP 模拟赛。发现 $B$ 题是个似乎比S组 T3 还简单的 dp，赶紧写完了。结果有一个大样例过不了，顿时有一些 joker，好在比较快的发现了错误，改了一个小地方就过了，用时 $20min$。

感觉 $A,D$ 题有一些困难，于是去看十分数据结构的 $C$ 题。首先发现对于全局询问是 cdq 模版，然后多组询问就不会了。中间想了很多种方法，但都未果。

这个时候回去想 $A$ 题，将题目转换为每次会选择一个数，将其 $+(y+1)$，求最小的操作步数使得所有数相等。设操作步数为 $opt$，期间 $\min a_i\ge opt$。注意到可以直接贪心，然后就通过了所有大样例，此时是 $10:00$ 左右。

然后 $D$ 题暴力都不太会，于是就准备冲 $C$ 题。但是中途想了若干个很有道理的做法，然而全都假了。于是在 $11:20$ 开始拼暴力分，本来以为能拿 $75pts$，然而发现 $q=1$ 的做法也有一些问题，然后就只写了 $30pts$。

100+100+15+0

$C$ 题并没有注意到 $n\le 5000$ 的点没有保证 $q\le 5000$，于是图省事写了 $\mathcal O(nq)$ 的东西，但是 $q\le 10^6$，于是 $T$ 了。

一定要看清楚部分分的数据范围，

几道题目都已经补完了，每道题目的质量都很高，其中有一些 Ad-hoc 和