VP NOI
要退役了，发现碰都没碰过以前 NOI 的题，所以需要 VP 一下。
NOI 2024
去年 VP 的，详见 VP NOI 2024 记录。
感觉这场要金牌要么切了 D2T2 要么 D2T3 得到 55 分，再加上 D1T3 的分比较高。Day1 需要提升速度，给 T3 多留一点时间。能不能切 D2T2 就看运气了。
upd on 2025.7.1：重新做了一下 D2T2，先是读错题了浪费了 1h 多，然后又完全不会。最终终于回忆起之前的做法了，总共用了 4h 才做完。看来当时并没有完全理解透题解。当时是记住了拆成前缀和这个 trick，但是没有记住这次卡我的枚举 min 这个操作。读错题还是太影响心态了，如果没读错可能会做的更顺一些。即使读对了我也很难在考场切掉这题，这一年还是太困难了。可能也不是把自己会的分都拿到就能进队吧。
NOI 2023
Day1
VP 于 2025.6.18 7:37。
开场发现 T1 是弱智题。T2 看起来不太可做，是我比较弱项的计数题。想了想把
Day2
VP 于 2025.6.21 7:30。
开场看 T1，想的方向就是利用子树大小是 nlogn 这个性质，然后很快想到了一个 log^2 的做法。看 T2，写出了判定条件，发现需要求 lcp，是一段 height 的 min。扫描线，将 min 拆开，好像切了。看 T3，这不乱搞题吗，把 T2 过了再说。写了 T1 之后重新思考 T2 的思路，发现假了。而且发现这个问题似乎非常难做。最终拼尽全力想出了一个看起来就过不去的 nsqrt(n)logn 做法。然后偶然抬眼看到了 R(s) 的定义。我忽略了右边子串的翻转。 破防了，重新思考发现直接用回文中心的半径，变成了不同起点的二维数点。发现可以用 bitset 做，但是需要分三段，而且还需要手写。感觉很恶心，但是这时时间已经不多了，于是我就写了这玩意。在最后半个小时内调了出来，但是被卡常了，最终本地卡到 1.4s 卡不动了。最后 4min 拼了一个 T3 10 分的暴力。100+[64,100]+10=[174,210] 遗憾离场（64、100 分别是洛谷、loj 的得分）。
总结
后来捋了一下思路很快就调出来了 D1T3，重新思考 D2T2 很快发现回文是可以延长的，于是 rk 就只与回文中心有关，然后就做完了。为什么我当时没多想一点点？可能还是读错题打乱了节奏，读错题至少耽误了 1.5h。我当时尝试思考别的做法了，但是我被读错题搞的已经想不动了。做 D1T3 也会了 30 分，如果场上有 2h 左右且心态比较好应该可以想到。
我发现我现在的主要问题已经不在思维上了，而是拿不到该拿到的分数。这两场一共会 100+35（至少）+72+100+100+30=537，已经稳金牌了。但是我写出来的比想到的少了 103 分。接下来的训练侧重点应该转向考场策略以及代码能力。另外考场已经要仔细读题，尤其是想了很久都不会或者瞬间就想到了都有可能是读题的问题。而且要写暴力，这次的 Day2 我是想着得 250 分翻盘的就没给 T2 写暴力，但是正式考试还是要稳一点的。以后的 VP 也要模仿正式考试，尽量多的得分，而不是将分数分为两段，非 1 则 0。
NOI 2022
Day1
VP 于 2025.6.24 7:35。
看 T1，发现直接随机化就行了，合并序列需要链表。之前知道不能开 1e6 个 deque，如果不知道没准我这题就挂了，这是 VP 无法模仿的因素。看 T2，发现可以长度 <=5，而且每个区间只会被操作一次，因此可以记录最近 4 个的减少次数，就可以判定了。但是算了一下没法过 k<=100 的部分分。li!=ri 的就更不能做了，因为我无法将一个情况压缩成一个状态，就没法计数了。不过也许大部分局面都是有解的。打算以后再想。看 T3，发现 A 性质就是猫树，B 性质似乎可以长链剖分，而且这样就可以做前两个点了。长剖的时候需要给一段后缀打 tag，但是这里没太想清楚。
写了 T1，犹豫了一会要不要对拍并造极限数据。最终还是写了非常难写的数据生成器，发现 5e5 RE 了。发现两个 tot 混用了。继续对拍。某个时刻发现拍不出来我已经打算关窗口了，但是突然就拍出来了，差一点就挂了。发现链表的右端点没闭合。之后又拍了一万组没挂就不管了。赛后实测 RE 的代码只有 65 分，调完 RE 后的代码只有 75 分。
感觉 T3 很难写于是先写 T3。写完 A 性质发现 windows 下无法运行交互库，于是改成直接在洛谷交，应该对分数没有影响。写 B 性质。写完之后是最痛苦的一段时间，只有 1.5h 了，完全看不出有什么问题。瞪眼法发现了几个问题之后终于不是 WA 而是操作不合法了。还是看不出来问题，凭着极大的决心快速手写了一份 info 并在本地对拍，拍出来了，调题终于有了点头绪。终于发现是 tag 合并的时候有点问题，改了之后终于对了，得了 30 分。这时候还剩 20 分钟，凭着极限手速 15 分钟冲出来了 T2 的 25 分，写完发现万一没冲出来，岂不是策略就有问题了。剩下 5 分钟还打算赶紧改出来 T3 的 n<=2000，但是发现数组比较难改，就放弃了。100+25+30=155。
Day2
VP 于 2025.6.26 7:30。
VP 前一天晚上失眠了。可能也不是失眠，只是中午睡多了导致生物钟延后了一个小时。最终睡了 6h40min，就当模拟一下失眠的考试状态了吧（但是相较真正的失眠睡的还是太多了）。实测一点影响都没有。
看 T1。感觉有点困难，搜索的话如果有一堆本质相同的叶子就寄了。如果使用哈希去重的话也需要枚举一遍，看起来就过不去。感觉正解可能是某种将本质相同的子树合并，比较复杂。但是部分分怎么这么多啊，k=0 直接判就行了，n<=150 应该也可以随便搜。先跳了。
看 T2。冒泡排序的次数不就是逆序对吗？难绷。B 性质和之前做过的一道 CF 题有点像，好像是决策单调性。但是冷静分析了一下本质上是每个位置的贡献是独立的，因为存在一种达到每个位置最优的方案是单调不减的，所以直接算就行了。考虑 C 性质，发现最小值肯定放在左端点，之后就转化成 B 性质了。再思考正解，发现直接从大到小枚举限制，标记哪些位置已经被限制住了，再对于区间删掉包含某个区间的区间限制，再从右到左，如果之前有则不管，否则让左端点的后继变成当前值就行了。这个过程可能复杂度比较高，一会再说。
看 T3。变量之间取值的约束很难做，看起来需要使用最小割。对于 G 的贡献转化为代价，那么需要对 pi-pj>=2 的都计算恰好一次代价。但是正常的切糕模型的贡献会被算 max(pi-pj-1,0) 次。我想到可以再减去 max(pi-pj-2,0) 就行了，这时候再加一条边就行了。算一下，大概有 50 分，太赚了。
回去写 T1。最开始想的是记录 dep 和每个点的儿子个数组成的可重集，这样修改的代价是 O(1) 的。但是写完了过不去样例 4。感觉可能还是需要一个靠谱点的哈希，于是每次修改的代价变成 O(dep) 了。花 30 多秒跑出来并过了。
写 T2。先写一个 C 性质看看对不对。怎么挂了啊？发现了一堆问题，但是改完了还不对，而且还比答案算小了。最终我把 a 数组都直接求出来并跑了一遍冒泡排序，答案还是小。我突然意识到限制还有一个要求是区间的所有数都大于等于 v，思路倒闭了。尝试了各种乱搞都还是挂了。我发现之前的做法是基于未填的数都是本质相同的，然后求了一个连续段这么做，但是这肯定是错的。于是现在考虑对每个数做。直接大胆猜想从前往后对每个数贪心找到最优的取值！看起来比较有道理，因为每个数可以取到无穷大，所以前面填的数看起来不会影响。写了，真的对了！
于是我继续写没有任何性质的做法。随便写了写，竟然一下过了所有样例！不过最后一个样例跑的时间比较长。发现求出每个点是否被选择为最小值以及每个点覆盖它的区间的 max 可以直接用 set 维护，这样这部分就是 O(nlogn) 了。对于后面的，我有两个想法：每个点的取值是可以三分的；整体的决策具有单调性。我先把前面那部分写了，回过头看发现后面的直接用线段树区间加，区间最小值就行了。于是飞速写完了，并通过了大样例。
重新思考 T3 的思路。我发现那种补偿的思路不太行，因为限制变成了或，而不是与，这时就不能切糕了。不过现在前两题的分数已经够多了，我打算先检查一下前两题。
我发现 T2 的极限数据要跑 1.5s 以上（造不出来非 -1 的数据所以还会更大），于是开始卡常。我把离散化和 vector 都删了换成了一个结构体的排序，不过没快多少。发现输入量巨大，于是默写了一下前几天刚背的 fread，变快了好多。觉得能过了，就不管了。
回去看 T1。发现可能删的点的 dep 只有 dep 的可重集相减之后剩下的。于是求出相减后的结果，搜索的时候就可以少搜好多点。这样写完之后大样例只花了 0.5s 就跑完了。
最后 20min 继续使用极限手速写完了 T3 的暴力搜索。
84+100+21=205，起飞！
总结
Day1 打的还是比较惊险，我误判了 T2 部分分的难度，那个 dp 其实是很好写的。T3 的部分分就非常难写，首先是我不会本地调试的函数式交互，而且还有我非常不擅长的长链剖分，以及以前从来没写过的在长链剖分上打 tag。最后调出来的时候都没想明白这个思路为什么是对的，这场打到 155 分还是比较幸运的。
Day2 我也不知道为什么就切了 T2，不过如果没切也有 64 分，如果 Day1 没调出来 B 性质，总分 100+25+10+84+64+21=304 也可以压上金牌线，这又说明了只要我把自己会的都打出来就差不多可以上金牌线。OI 的确是一个不求有功，但求无过的竞赛。
NOI 2021
之前写过两天的 T1，先跳了。
NOI 2020
Day1
VP 于 2025.6.30 7:32。
前一天晚上没睡够（7 个半小时左右），按理来说应该比 NOI 2022 Day2 那天更够一些，但是实际上没那天精神。可能是想到即将达到金牌线的肾上腺素让那天精神起来了吧。
看 T1。之前大概了解过这题的思路（虽然当时连题都没读），所以这次做的可能快一些。首先发现怎么着也得做边权为 1 的问题，然后发现直接矩阵快速幂就行了，对于 k 次节日就拆开时间做 k 次。可以使用经典套路做到 n^3logt+kn^2logt。然后发现可以将边拆成 5 个点。根据之前模糊记住的做法（拆边->拆点），发现可以将每个点的时间 %5 新开一个点，这样边权就只有 0 和 1 了。对于边权为 0 的边的处理，可以：对于任意一条边的终点，认为这条边可以走到只保留边权为 0 的边后连通的点。这样随便预处理一下就行了。
看 T2。这不一眼容斥吗，然后一下就有 40 分了，得分这么容易的吗？怎么感觉这题和 2023 年 D1T3 这么像啊。考虑树形 dp，发现限制放在下面的那个点上就行了，转移是取 max。然后取 max 可以转化为前缀和，就变成了对应位置相乘。但是这时候没仔细推转移，所以先放着了。
看 T3。这题之前也做过，当时拼尽全力只会四维莫队的 52 分。因为没看题解所以问题不大（不至于比当年的水平还差吧）。发现 A 性质是送的，甚至不用写分块或者莫队二次离线，直接跑莫队就能过。C 性质直接统计逆序对个数就行了。这样瞬间就有 52 分了。接下来思考没有性质的做法，想了半天竟然除了四维莫队什么都不会。终于想到了一个对序列分块，散块随便做，整块转化成 n^2/B^2 个莫队问题，复杂度是 mBlogn+n^3/B^2logn+msqrt(n)logn，即 n^{5/3}logn 的做法。如果有时间就写这个吧。
写 T1。这时候大概是 9 点，计划 9:30 写完。结果写挂了，调了半天，调出来之后写了个拍还拍挂了，后来发现是暴力写挂了。最终 10 点才结束。
先写 T2 的暴力。发现转化成前缀和之后只有区间乘、区间加、对应位置相乘三种操作。我突然注意到这样序列的连续段不会很多（是子树大小个），这样 dsu on tree 就可以双 log 了。我又大胆猜想直接线段树合并，如果两段都相同就不管，的复杂度是对的。又想了一下发现只需要一段都相同就可以给另一段打 tag 了，但是复杂度还是不太会证（没细想）。不过看起来就是对的，于是就写了这个做法。写完之后时间和空间都爆了。精细实现之后需要跑 3.5s。然后发现没开 ios。。。改了之后 2.3s，又发现净输入就花了 0.3s，于是改成 fread 之后就只跑了 1.9s。能不能过就富贵在天了。
这时只有 1h 了，我打算先把暴力、A、C 的 52 分先得到。写的非常顺，20 多分钟就写完了。这不得冲一下那个分块？还是写的非常顺，又花了 20 分钟左右就写完并调完了。发现随手写了 7kb，这就是写了很多 Ynoi 之后积累的码力吗？样例 3 非常快，但是本地造的 3e4,6e4 需要跑 5s。这时还没反应过来为啥。于是我开始调块长，但是调完块长空间就爆了，需要重标号使得空间 /2，还只能跑 5e4。但是更大的怎么着都过不去吧。 调块长的时候还有 5 分钟左右，改完只剩 2 分钟了，赶紧回去检查其他题。
这时突然有一种不详的预感，样例 3 那么快，不会这个做法能过特殊性质 B 的 >5e4 的点吧。没多想。
测试，T1 过了，T2 洛谷 T 了一个点，loj 过了，符合预期。T3 洛谷 60 分，loj 64 分，多过了 4e4 那个点。把改块长之前的那份代码交了一下。76 分，B 性质全过了。
破防了，乱改块长少了 12 分。
破防了，乱改块长少了 12 分。
破防了，乱改块长少了 12 分。
100+[96,100]+[60,64]=[256,264]。其实考的挺好的，但是少了 12 分让我完美主义情结发作了。遗憾离场。
Day2
VP 于 2025.7.2 7:27。
看 T1。什么玩意，怎么这么像猫粮？但是一个原材料可以拆。感觉可以将两个点组成的菜连一条边，自己组成就连自环，但是好像没有什么用。尝试分析图的性质，大胆猜想没有图没有非自环的环，否则可以用自环代替。尝试证明但不会，不过证明了 n=3 的情况是对的，感觉看起来很对吧。但是即使知道了树状的结构还是不会。
发现部分分有一个 m>=n-1，再一看原来有 m>=n-2 的限制，之前没看到。那先想想 m=n-1 咋做。发现通过总和的限制可以得到一些比较好的性质，比如最小值 <k。观察大样例发现没有 -1。模拟样例，最终想出来了每次将最小值与最大值匹配就是对的。甚至这个结论非常好证明，如果它们总和 <=k 则剩下的总和 >=(n-2)k，即一定存在一个 >=k 的值，与最大值矛盾。
接下来思考 m>=n-1 咋做。发现自环可以让边数减少但是点数不变，那只需要证明 m>=n 的时候一定存在 >k 的点就行了。发现要么存在 >k 的点，要么全都是 k，于是就可以转化为 m=n-1 的问题了。
花的时间有点多了，赶紧看 T2。题面很长，因为之前读错过题所以这次读的很仔细。发现 grow 本质上就是替换后的树包含当前的树。考虑分类讨论根节点的儿子情况。如果发现可以分成三类，而每类都是互不相干的。对于都有儿子的情况，两边好像也是独立的。这样就会 O(n^2) 了，因为递归的过程中每个点最多递归一次，而分类是 O(n) 的。真的是独立的吗？好像确实是。接下来思考正解，不太会，但是感觉可能加一个树哈希去重复杂度就是对的，没细想。
看 T3。这个对环的限制好奇怪。建点双，猜想环上两个点如果不是相邻则走任意一边都行。然后构造了一下发现假了。但是发现如果边权都相同的话就真了，简单地证明了一下。部分分表只有四种数据，连纯暴力的分都不给，看来是不可做题。想 B 性质，发现在链上而且每个点可影响的范围很小，直接 dp 就行了。最开始的 dp 状态是 i-1 与 i 是否相连，发现做不了，然后打算直接大力记录一下前面几个点的连通性情况，发现只需要记录 i-1 和 i 的连通性，于是 dp i,0/1 就做完了。仔细写了一下转移方程。在不可做题上得到 45 分，感觉优势在我啊。打算先把这题写了，以后可能就再也不看这题了。求出 s,t 的链很烦，不过还是很快写完了。
这时我打算先把 T1 的分写了。之前在 NOI 2022 Day1 得到过教训（虽然那场没爆）：T1 应该是好写的，只是我没想太清楚所以不想写；T2 可能不太好写，只是我想的比较清楚所以想写。这时候应该先去写没想清楚的。很快写完了 m>=n-1，手摸了一下样例没问题。我打算思考一下正解，因为我还没怎么想正解，而且这个暴力太难写了。模拟了一下样例，发现中间就有两个消掉了。那就可以转化成两个 m=n-1 的问题了。看起来很对，但是当时没有仔细想正确性（其实很简单，m=n-2 一定会形成两个连通块）。这样我只需要求出一个 sum=(大小-1)*k 的子集即可。直接 bitset 就对了。但是算出来怎么 1e9？好奇怪。冷静一下发现 m 不是 5000 而是 n 的级别，这样就完全对了。写了一下很快就写完了。测大样例，发现和答案的构造都几乎是相同的，看来做法太真了。
回来写 T2 的那个想法。发现这个做法还是好写的，之前的那个对教训的分析也不太对。但是测样例怎么挂了一组？模拟了一下发现同时有两个儿子的时候完全不是独立的！怎么可能是独立的呢？就像是 (1,n) 和 (n,1) 的矩阵覆盖不了所有点一样。这下就完全不会了。想到可能可以枚举深度比较小的所有树，然后暴力 check。然后列出来了一个 dp[i]=2dp[i-1]+dp[i-1]^2（实际上甚至还少算了一些），发现到 6 就爆了。而且求出来之后还要遍历每棵树，很难得分。然后想到可以随机生成一些树去判断。还想到可以可以将某棵树微调一下形成新的树去判断，但是仔细想了一下感觉很假。考虑最暴力的做法怎么做。对于有两个儿子的情况需要将这两个儿子都传下去，而且它们还有可能分裂，需要 vector 套 vector。对于空节点可以充当任何情况，还需要这些情况都传下去。这时候思考特殊性质 4，发现这时第二维的 vector 大小就只有 2 了。打算实现一下这个做法，写的时候发现根本不用传 vector，走到了某个分叉的时候必须存在两个儿子的子树大小都是 1 的点，否则直接再用两个分叉就卡掉了。这样用最开始的那个做法改了改就得到了新的做法。而且最开始的那个做法可能还能得到一些分。
不太想写其他做法了，打算稳一下，去检查其他题。造了一下 T1 的极限数据发现要跑 3s，但是我不想手写 bitset 啊。加了一个找到就退出的判断，变成 1s 了。基于这个思路，我发现可以先贪心地安排顺序让找到的位置尽量小。按照 |ai-k| 从小到大排序就只跑 0.2s 了。不管了，反正 NOI 的机子应该比本地快。
写了一个 T3 的暴力与特殊性质对拍了一下。特殊性质 A 挂了，但是猜测是图的问题，就不管了。
这时候是 12:02，不想罚坐了，就提前交了。
100+40+45=185。
总结
这场打的挺好的，比金牌线高了 95 分（快进到笔试爆零）。主要是切了 D1T2 和 D2T1 两道黑题。两道切一道都可以金牌，但是我无法保证再打一次切这两道题的至少一道。所以比赛就是存在随机性的，最小值总是可能达到的，但是我们更看重的是期望得分。总是想自己打比赛的最小得分可能是多少，然后与金牌线去比较是没有意义的，只会更加焦虑，增强“必须金牌”的压力。反正现在我可以说我有金牌的实力，但是能不能金牌还是一定程度上被运气决定。无所谓，什么样的结果都可以。
不过我现在感觉是不是这几年选手的水平提升太多了？至少大样例的加强以及 pretest 的引入会导致选手表现提升，而我正常都不会挂分，所以这样会弱化我的表现。或者说，我会发挥地比前几年的 NOI 差，所以前几年 VP 的成绩也不算什么。可能吧，比如 NOI 2024 我还是觉得金牌很困难。还是不去想“金牌”之类的事了吧，发挥出自己最好的水平就行了。
这场比赛在策略上我感觉没有什么问题。非要说的话，D2T2 那个显然是错的结论竟然在当时被我认为是正确的，看来人总是倾向于相信已经得到的结果而不是推翻它。以后还是要多写，用代码去一步一步地验证，而不是一下空想很多。
UNR 2024
感觉近些年的 UNR 的题目质量可能比更早的 NOI 高，所以开始 UNR 了，不过估计只能打这一年加上今年的，时间不够。
Day1
VP 于 2025.7.4 7:34。
看 T1。一眼看上去啥都不会啊，又是该死的神秘贪心。于是开始虚空思考，完全找不到题目的入手点。写了一个贪心（每个 1 匹配距离下一个 1 之间的最小值），挂了。又想了几个贪心也都挂了。终于在尝试证明某个结论发现排序会交换若干次逆序对，而这个操作相当于若干次长度为 2 的操作。这样终于找到了一点头绪。但是还是啥都不会。写了一个每个 1 找到后缀最小值并交换过来的贪心，也挂了。已经过半小时了，先看别的题。
看 T2。最开始看成了集合而不是集合大小不同，发现对每种数的出现次数算一下就行了，写了一个暴力意识到题读错了。不过对每种数的出现次数算仍然是正确的思路，每种数有 1 的方案贡献 1，1 的方案贡献 -1，2^cnt-2 的方案贡献 0。这样就会多项式复杂度了。接下来意识到一个区间的不同 cnt 只有根号种，想到了一个 dp，dp i,j 表示前 i 种 cnt 的总和是 j 的方案数，但是需要非常复杂的枚举。但是在转移中有一个 2^cnt-2，我发现当 cnt>=64，值都是 -2！接下来又想了想，发现 (2^cnt-2)^x 这个式子中 x 不会很大否则模 2^64 是 0，打了一下表真的是这样。这样大概搞懂这道题的考察方向了，就是利用模数减少状态。
看 T3。想了一个 O(Lnm) 的 dp，猜想卡常可以过 sub5。但是 n 很小完全不会，甚至 n=1 都不会，而压根没有这档分，太奇怪了。想了一下 dp 的转移过程，但是感觉平移、两个数组区间取 max 这种操作应该是经典不可做问题。怎么感觉这是要寄的节奏啊。我先写了一下这个思路。写完之后发现大样例挂了一个？？？重新读题发现路径只能向右或向下走，这样也确实看起来可做多了。但是我记得我之前验证过路径的形态是不是只能向右向下的，但是完全没有看到。看来我的读题可能真的有点毛病。接下来卡了一下常，sub5 的大样例跑 3.5s，但是数据没卡满，卡满就过不去了。
回去重新思考 T1。我终于想到了一个看起来比较正确的贪心：每个 1 可以匹配后缀的值，要求值不重复且总和最小。这个贪心唯一的问题是，如果 1 匹配了一个超过下一个 1 的位置，那么这段平移过去之后下一个 1 的选择多了 1。但是我猜想不会出现这种情况，感性证明了一下。这样的话直接从后到前维护一个优先队列就行了。写了一下发现过了。差点死在这题了，过了真是万幸。
接下来看 T2。冷静了一下发现我不需要记录总和是多少，只需要记录选了多少个 0 就行了，剩下的就是一个 C(n,n/2)。这样就有一个状态 64^3，转移 64 的做法了。写了一下。写的过程出现了很多问题，我发现 C(n,n/2) 没法直接求，因为阶乘无法求逆元，需要先把 2 提出来。据此我又猜想 n 比较大的时候 C(n,n/2) 是 0，但是打了一下表发现不是。接下来我写了一下之前想到的做法，但是挂了。后来发现 p 不是质数的时候不能用线性预处理逆元，需要写 exgcd。改了改就过了，sub3 勉强能过。接下来我大胆猜想状态中好多是 0，结果发现只有 64^2 级别的非 0 状态。我终于发现是因为 (2^i-2) 一定是 2 的倍数，所以选的树大于等于 64 后就一定是 0 了。这样改了改就变成 64^3 的复杂度了，卡了卡常可以过 sub4。发现是一个卷积的形式，但是我不会快速求模 2^64 下的卷积（如果用 FFT 估计比暴力还慢），就不管了。
继续思考 T3。我把整个字符矩阵的第 i 行向右平移了 i 个位置，这样路径就是从 (x,y) 走到 (x,y+1) 或 (x+1,y+1) 了，形式可能更优美一些。根据我的经验，这种匹配的问题很像能用 bitset 做的，而且似乎没有别的做法做。于是我想到了一个压位的做法：维护一个状态表示这一列有哪些点能到，每次 x=(x|(x<<1))&zt{i,s{i-y+p}}，zt 表示第 i 列某个字符匹配的情况。我感觉之前的暴力可能过不了，所以这个做法还是有价值的，写了一下，sub5 只跑了 0.2s。接下来我开始思考 n 比较小的情况。n=2 可以直接求 lcp 并走下去，但 n=3 我就完全不会了。最终终于想到了一个二分答案并分别求第一行的 lcp 和第三行的 lsp，再检查 s 和第二行的某个区间是否匹配的方法。本来要开始写了，但是冷静了一下发现检查区间是否匹配也没法做，除非 bitset，但是 bitset 还需要枚举每个字符，而且本身复杂度就巨大。于是我就放弃了 n=3。我又想了一下是否可以对某个点预处理从某个状态开始，匹配所有长度为 5 左右的字符串后走到的状态，以此实现一次跳很多个。但是仔细算一下就发现完全不行，状态数爆了。于是我写了一个 n=2 就弃疗了。
12:12 交的，因为什么都不会了。没挂分，100+80+24=204。但是居然排到了 100 名。我还以为 T2 那个 80 分的思路很奇妙呢，实际上很多人都会，可能是我做的过程比较奇妙（打表找规律）但是如果正常观察的话都能观察到。不过发现很多很强的人分数都比我低，感觉这场区分度可能比较奇怪，T3 要是想不到就是想不到。Day2 好好打，争取翻盘。
Day2
VP 于 2025.7.5 8:00。
看 T1。尝试求出连续段，但是发现消掉之后奇偶会合并，感觉还是不用连续段刻画好。然后发现一个士兵存活的时间只与前缀有关，然后就可以依次求出每个士兵的存活时间。我发现需要维护一个单调栈表示从后到前 ti 的 max。然后可以合并相同字符的，这样新加一个字符的复杂度就是 O(1) 的了。仔细分讨了一下。大胆猜想可以压状态并且状态数不多。发现直接 dp 已经有 60 分了，可能还能冲过去 n=100,k=100 或者下一个 sub。但是分析了一下 n 很大的时候可以构造出非常多种的状态，可能正解需要再压状态。
看 T2。发现可以直接用元旦激光炮的做法做到 nlogn 次，而且我那个做法好像没什么人写过（大部分都是接近 100 次，我的只需要 50 次），可能会有一点优势吧。但是 8e4 刚好过不去。分讨了一下具体情况。但是其他就完全没思路了，我利用不上竖向的单调性。
看 T3。那个式子可以对每个点求出向左、向右第一个小于或小于等于的位置，然后 O(n) 求。但是这两个信息在修改的条件下非常难维护。所以我还是考虑原来的式子。感觉可以分块，维护每两个块之间的贡献。块内是容易的，块间只需要处理它与其他块的贡献，我发现块内的修改是区间赋值，那么只需要求一个点与其他的贡献再覆盖即可，对每个块的数排个序就行了。冷静一下发现了很多问题，比如因为有中间的块取 min 的贡献，需要对所有跨过这个点的块的对都修改。另外修改也不一定是覆盖，数值可能变大，这时候就无法刻画了。而且还需要对于一个块的对需要在两个块那里都维护这样的信息，而修改的时候无法同步另一个块的信息。反正就是假飞了。我开始尝试 O(n^2) 卡过去，于是我分讨了一下修改对 L,R 的影响，发现可以 O(n) 维护（变大的时候需要维护一个指针）。于是我写了一下这个暴力，发现跑过了数据随机的点，因为期望修改的次数很少。但是造了一组数据不随机的时间就起飞了。考虑值域很小的部分分，可以对每个值域统计答案，只需要用线段树维护一个有多少区间内只有 1 的数量即可。从这里我想到是否可以值域分块，但还是不会。先把这道题的 40 分写了。
回去思考 T1。还是啥都不会，但是有概率得到 84 分还是感觉不太差。于是我写了一下。确实能过 n=k=100，但有一个点跑了 4 秒，于是我开始卡常，将修改变成 O(1) 的并维护哈希值。挺难改的，改完了就跑的很快了。然后我尝试测 n=k=100 的极限数据（全'?'），发现跑了 30 多秒。破防了，改了这么半天一点用都没有。考虑到出题人可能会全造 '?' 的数据，于是我可以打表。但是最终我也没打，只是将 n=k=100 跑出来的唯一一个数据贴上去了。
写 T2。写完之后我想到了一种卡常方法：每次只放进去 5000 个区间，等某个区间用完了再放进新的。写完了发现一点用都没有，然后才发现查询次数一点没变，太难绷了。之后从随机撒点的思路延伸突然想到了一种比较有前途，也能利用上列的单调性的做法：将整个矩阵分块，形成 500*500 的块，每个块的数取值在一段区间。然后将它们的取值放在左端点和右端点可以求出来不同的 kth，那么真实的 kth 一定在这个区间，然后将完全在左端点左边的和在右端点右边的删掉，再对每个块的每行拎出来，跑之前的做法。实现了一下这个做法，但是调了一年，还是对交互库的使用非常不熟练。在 12:50 左右终于调出来了，但是跑的结果比正常的差多了，调块长也没有用。不太会分析，可能这个做法就是比较劣。
最终 84+40+40=164 遗憾离场。然后发现 T1 过了大半场人。我完全做不明白这种题，看了一下正解，对 i 维护第一个 tj>=i 的位置我完全想不到，正常没有这么维护的。很难理解。剩下两道题可能是不可做吧。反正区分度极低，还把我区分下去了。
总结
这场还是让我意识到了实力的不足。D1T2 官方题解的做法我场上已经猜到了，但是式子中带一个 -2 让我这个做法优化不了，而正解是先使用生成函数将那个 -2 去了。我场上猜测到了生成函数可能可以但是我认为我无法推生成函数于是放弃了，但是这个问题的生成函数推导还是我能接受的。我总是在做题的过程中论证某个方法不可做而不是去尝试。 随着做题量的增多我越来越对此有感触了，很多题不是不可做，而是我把可做的做法否定了。出题人也是人，能提出的问题一定都是可以理解、可做的。
D1T3 也是这样，n=3 我场上找了一个例子就证明了 n=2 的贪心是错的从而否定贪心，而不是尝试修补这个贪心。这样强烈暗示做法的部分分就应该按照做法去做，而不是逃避。贪心可能是我认为我自己的弱项，但是其实很多贪心也都是可以理解的。其实我可能也没有什么强项和弱项，只有想做和不想做。数据结构我可能认为是我的强项，但是做题还是啥都不会。单纯只是写数据结构题让我很有成就感罢了。另外这道题的正解也不是很难，本质上就是一种递归的思想。这种 n<=10 的题显然就是让你一步一步地将问题归纳成更小的问题。我还是对这种思想的理解不够深刻。
D2T1 我还是无法理解。我确实是想不到。在和正解没有任何关系的情况下得到了 84 分也算是幸运了。
D2T2 和 D2T3 可能在考场上是不可做题。当然，还是要相信每道题都是可做的。还没补，补了再说吧。
UNR 2025
Day1
噩梦一样的经历，不想多说了。
主要就是不会 T1 给我心态搞炸了，反复确认 si=0 的边是同一条边的正确性，用暴力测试是对的，但是最后发现假了只是能过 n<=20。反正就是完全不会。
其他时间写了一个 T2 的 n^3，T3 的 n^2/w。以为是正解，结果发现假飞了，也不知道当时怎么想到这个错解的。
Day2
看 T1，出题人这么喜欢排列？？？这什么限制啊，完全没思路。想了半天也没想出来任何有价值的做法，顶多是找了找 k=0 前几个数的要求但是也没递推下去。
看 T2，不是哥们怎么又是排列啊？仔细看了一下，才发现把排列当成图论中环就好理解多了。想分块，没有什么思路。可能是看到了交互次数的限制，突然就想到了分治，每次只需要将两边合并起来，而且一层的可以单独做，只需要查 log 次。然后仔细思考合并的过程，但是似乎都需要二分，次数就爆了。但是可以将这些二分放到一起，即整体二分！这样就会好多分了。但是看起来好难写，需要将一层的放到一起，而且一条链的两个端点还需要拆开否则它们自己就匹配了。
看 T3，dp 好明显。然后就想到会有各种的乱搞，比如决策单调性或者三分之类的，看起来很可做。分析了一下发现只需要保留前后 k 个，这样算一个区间的答案就是若干个 log*k 了。
于是我就开始乱搞 T3，比如在上一个点的决策左右去选，或者根据上一个点的答案分析当前从 i 枚举到多少之类的。但是搞了一年没搞出来。其实构造一个单增的数组就能把这些乱搞都卡掉，我也没想出什么好的应对策略。
这时候心态已经崩了，T1 完全不会，T2 非常难写，T3 只有最暴力的分。想着要不就不认真打了，仔细想想这个 T3。除了会 k=2 的做法以外啥都没想出来。
写了一下 T3 的 n<=1000 和 k=2（n^2 暴力枚举但是可以过）。
我还是回去看了那个看都不想看一眼的 T1。写了一个暴力，尝试找规律。结果真的找出来了！打出 p1 的取值对应的个数之后找出来了 k=0 和 k=1 的递推式。然后再分析一下就会 k=2 以及更多的了。甚至还会生成所有的排列了。写了一下，得到了 62 分，挽救了心态。但是根据这种生成方法，之后的限制会有平移，没法 dp。先去写 T2 了。
T2 没有想象中的难写。很快得到了 57 分，接下来一直在卡常。有一个比较有用的优化是查询很少的时候直接算答案。最终优化到了 72 分。
总结
这场打的比较烂。虽然题目类型可能和 NOI 不太一样，但是还是说明了我和真正比较强的人的差距还是很大的。D1T1 又是一道全场切了的题没过。这道题一个 trick 是考虑树的重心，我可能没有真正学过这个知识点，做的题也比较少，就没想到。另一个 trick 是倒序枚举，这种思想虽然听说过但是没有应用过，所以考场的时候想不起来。我的知识广度还是有问题，应该多做一些题，看看 trick。D1T2 也是完全不会模拟费用流，这种算法之前没学过。考场时就猜到是这个算法了。也只能认了。高二的时候得把缺的算法都补上。
Day2 就算是在逆境中保持住差不多的水平的发挥了。T1 我至今不会做，就是碰上那种很不擅长的计数题了，也是没办法。但是凭借 T2 的优势苟到了 55 名。说明也不一定需要切签到题，把自己会的打出来就还可以。NOI 也是，不要被不会 T1 搞了心态。不一定要切 T1。