xya 与 OI 的故事

前言

感觉自从 NOIP 打完之后整个人都很摆，不知道自己在干什么，很多时候想写题但是找不到思考的感觉了，也没有做到适合的题，慢慢的整个人就变成：听别人讲思路看题解，写代码甚至可以说是默写代码，调不出来了，对着题解查错，最后写完一个题。整个过程，甚至都没有办法称得上是代码复制机器。其实个人感觉，或许真的需要好好休息一下，但是离寒假还很远，而且寒假也未必会好好休息，所以，可能我自己也不知道该怎么样去调整。

写这个类似回忆录的东西，才发现好像这一年对我而言并记不住任何值得回忆的事情，而只有每天都在重复的日常，日复一日，好像并没有任何偶然事件，也没有任何能够令人印象深刻的事情。

感觉写的很乱啊，写的也一点也不好看，后面的发生的事情更像是说给自己听的一些东西，不管了。

回到正题

这篇文章究竟要写什么呢？感觉或许记录一下这一年里的种种琐事，记录一下自己学 OI 这一年半的时间里所经历的事情，也记录下自己的心得吧。

比较重要的同学 / 朋友

这一点多里，固然交到了很多的朋友，认识很多新的同学，在这里面自然有形形色色的不同的人，而每个人也会带给我们不同的感受。

KSCD_ - 个人中心 - 洛谷

炜哥应该可以排的到前面，学 OI 的这些时间里，不管是学习方法上的、心态上的甚至于是写专栏等种种习惯，很大部分都是深受炜哥影响的。一方面来说，我个人认为我们两个的经历是很相似的，这让我们之间有非常多共同话题，也容易引起共鸣。可是也许我没有炜哥勤奋、没有炜哥有毅力，亦或者说就是命中注定，总而言之，炜哥可以真正称得上是一个榜样，或者更确切来讲，应该是一个引路人。

炜哥很扎实，这是大家公认的，这可能也是他能很好的在 sale 上发挥出来，而我最终没有调出来的原因之一，但是人与人之间总是有很多不同的。可能在同一个时间，面对的是不同的处境，心态也不尽相同，但归根到底，炜哥带来的影响是巨大的，虽然或许我们相处的时间并不是最长的，希望炜哥能顺利进队吧。

Iceturky - 个人中心 - 洛谷

杰哥和炜哥很相似，在他们的身上都有踏实、质朴、善良所在的，但是和杰哥熟悉或许比炜哥更晚，细说起来大概是从初三暑假开始的。和炜哥比起来，杰哥应该更安静、更平淡、更细腻。杰哥非常好相处，爱听音乐喜欢各种游戏还是动漫人物的图片，这也算是他的一种精神寄托。杰哥教会了我很多，更多的是操作系统以及一些小技巧方面的东西，也带来了很多乐趣。

希望杰哥炜哥都能顺利进队吧。 除此之外还有很多学长，比如 zhu_wen，chb，ryp，cybrex，zibenlun 等等很多人，这里没有一一列举，但是他们之间的情谊，远比 OI 本身更加珍贵。

说完几个学长，再来说几个同级同学吧。

Dtw_ - 个人中心 - 洛谷

Dtw_，我心中的 rk1。如何讲起呢，可能我们之间回忆中并没有多少起伏，没有多少被铭刻的瞬间，而绝大部分都是 OI 生活的点滴小事。他应该是除了 zhu_wen 以外我最先认识的人。和 Dtw 相处的时间应该占了我目前为止 OI 生活的大多数，以至于不知道从何讲起。

比起和炜哥之间的经历相似，和 Dtw 之间更多的是一个不断磨合的过程，每天从早读、上课到下午训练、晚上晚自习的全部时间都在一起，慢慢的我们都习惯了彼此，性格也慢慢变得相似。在国庆之前，我一直都把 Dtw 视作我努力的对象，在我看来，如果有人能够达到 Dtw 的水平，那么就可以称得上是了解 OI 的程度了，感觉这个表述并不恰当，总之，我认为 Dtw 可以看作是不冲省选选手的极高水平了。

在整个 OI 的过程中他教给我了很多东西，除去简单知识层面的影响，他对待生活、对待学习、对待放假休息的种种态度与看法，也或许让我真的触摸到了真正的生活应该具有的层面。我一直都认为他将会是陪我走过 OI 生涯最久的一个人，这种令人沉浸的幻想一直持续到国庆，他选择省一回归 whk，而我选择了继续打 OI，这些选择并不能说清楚为什么，而是漫长岁月中积累出的结果。在 wfbczx 的两个月，我们彼此之间更加了解，也更加珍惜难得的相处时间，珍惜在一起玩、讨论的时间。

希望 Dtw 明年能取得自己想要的成绩，在 whk 学习也能蒸蒸日上啊！

Handezheng - 个人中心 - 洛谷

对于 hdz，我可以给他以下几个标签：智多星，"运气"也是实力的一部分。为什么这样说呢？hdz 对于数学和 OI 问题的理解能力，以及思考能力是很牛的，虽然平时总给人一种划水的感觉，但到了关键时候总是能打出不错的成绩，可能我们会说这里面确实有运气成分在，但不可否认，hdz 在认真学习的过程效率是极高的，以至于总是给人一种不切实际的感觉。

和 hdz 相处更多是生活、娱乐的一些方面，打球是我们几个之间的主旋律，娱乐之余也有不少相互之间的陪伴，不管是 mxbj 还是在学校的很多时候，hdz 都给我带来了很多启发与影响。

syc，数竞老哥

这是为数不多我非常熟悉的除了信竞以外其它的同学，最开始认识 syc 是初三每天体育课打球认识的，慢慢的就熟了。可能每天在一起的时间总是被不同科目给分割的刚刚好，我们之间的关系非常融洽，在一块干的事情也很纯粹，就只有打球和聊各自竞赛的一些事情。

以及 Pigsyy，lzx 等等一系列同学，由于下午讲题突然没那么无聊，没那么消沉了，所以就不继续写下去了。

发生的一些事情？

说完了同学，说说这一年多里发生的很多事情。要说很多事情，实际上我认为的 OI 生活是十分平淡，是不断地重复同样的事情的。

寒假去了 qbxt，感觉并没有收获极大，但是怎么说呢，收获倒也还蛮大的，最起码听说过了很多新的东西。从 qbxt 回来的训练本质上没有什么改变，和 24 年刚开学时一样，没有方向、没有目的，就只是在散碎的各种各样的题里找几个做，要上课了就听，需要学啥就学，也没有很多长进或是提升。

一直到 25 年的五一，又去了一次 qbxt，可能是自己的实力也略有所提高，加上上课难度不大，所以在课上能很清楚的跟上思路，大量地思考让我懂了非常多新的东西，也开始记录、研究一些 trick 或者是数据结构。五一回来之后学了点分治，点分治真好玩！当时并不理解点分治到底是怎么做的，至于我和点分治的故事后面再讲。

五一之后就准备回去复习中考了，实际上只回去复习了两个月，加上没有上过几节课，多半都是自己琐碎的学一点，以至于中考两周前我还没有学会很多电学方面的东西，化学也几乎一窍不通，好在是政治历史并不担心，这两科多看了几遍就吃老底场上乱编了，真到了考场上发现其实答得还不错。就这样补课学了两个周就匆忙去考试了，学的太匆忙导致没有时间去做练习，我的数学成绩起伏非常明显，甚至于在 $[110,150]$ 之间来回剧烈波动，其余科目也并没有见过非常多的套路。

不久就去中考了，Day 1 好像是语文政治历史？总之 Day 1 整体做的还蛮不错，感觉没什么问题。转折发生在 Day 2 的数学，场上很顺利地做完了第一张，但是在做第二张的时候被摩天轮卡了很久，最后一问的黄金分割也卡了很久，出场后发现自己的二次函数好像也求错了，心态很崩。

但是还是稳住了心态，下午物理非常简单！主要是电学比较简单，所以卷子我都会，化学就一塌糊涂了。很快出分了，很出乎意料数学居然还是 A+，但是化学是 B，总而言之也还不错吧，毕竟已经一年没有学了。毕竟是 OI 回忆录，whk 部分就一笔带过了。

中考回来之后，才意识到自己的 OI 生涯再不努力就没时间了，于是开始变得认真学习了。倒也不是之前没有认真学，可能是彻底摆脱了 whk 的束缚能全身心投入进去，也慢慢能想出来一些常见的小 trick，每天就是在听课、做题、模拟赛，倒也很忙碌。

要非要说有什么留下深刻印象的事情，可能要从中考过后开始说起。

六月中旬学校搞了毕业典礼，时间很短，但是还挺不错的？总而言之，算是给初中画上了一个圆满？的句号吧。

暑假去了 mxbj，感觉在 mxbj 的时间是我从之前啥也不会的阶段转折到慢慢能知道一些 trick，能自己做出来一些题的阶段。在 mxbj 认识了 ez_lcw，神仙人物啊！以及 zj 和很多其他的人。lcw 上课很多人不听，这是好事啊！lcw 非常自然的就认识我了，lcw 讲课真的好啊！从头开始一步一步讲，每一步都讲得很细致，并且 lcw 经常询问听懂情况，由于没太有人听，慢慢得 lcw 貌似就变成看我有没有听懂了。经常吃饭的时候找 lcw 打球，慢慢和 lcw 熟起来了，很喜欢 lcw，lcw 也经常给我鼓励。

暑假最后又回去学校了，9 月一个月是非常黑暗的时期，学校的同学略有些混乱导致训练效率并不高，但好在是时间足够多，感觉这一个月进步还是非常大的。到了月底很多人去了 lca，我也去了 mxbc，认识了 tby 以及 qaz 和 xz 等人，在 wfbczx 的两个月应该提升是巨大的，训练量上来了，难度上来了，效果也慢慢出来了，我开始慢慢在模拟赛做出来 T1、T2，但是总归是拼尽全力无法战胜，OI 还是太难了。

CSP 的几天是非常快乐的，主要是能和同学呆在一起，S 打的并不好，但是总归，其实也还不错。

CSP-S 2025 游记 - 洛谷专栏

不久就 NOIP 了，也慢慢意识到好像很快就要和身边朋友说再见了。当时前一晚并没睡很好，但是并无所谓，毕竟人体的调节能力是非常强的，进场之后很快切了 T1，本身目标是奔着三倍队线去的，场上预计的三倍（也就是去年 $272$）大概是 $248$，因为 T3 $8pts$，T4 $40pts$ 都是很快就已经写完了，T1 是个签，T2 当时场上很快就推出正解来了，但是没有想到 T2 这么难调，当时场上留了 3.5h 来写 T2，放在一般题很快就想出思路了，3.5h 是完全够了的，但是场上调出几处错误之后大样例始终大 $1$，不知道该怎么办了。看着时间一点一点过去，很无奈但是也没有办法，在半个月之后再看才发现是自己没有处理好相等的情况，可能场上加上一句 if(a[i] != a[j]) 就能进两倍了呢？但是所有的东西都回不去，也没有后悔的余地。

NOIP 2025 游记 - 洛谷专栏

NOIP 之后整个人好像都变了，看不到未来，看不到翻盘的希望，每次都在思考当时 T2 为什么没有处理好，其实细想想这一年多并没有好好休息一下，自从中考过后好像也没有放过 $2$ 天的假期了。整个人其实是非常希望能有一个长假来调整一下的，但是过年还有很久，年后也没有很多时间了，每天都在模拟赛浑浑噩噩并不能有什么改善，每天的状态就像刚开头写的一样，很疲惫，很摆，好像每天干了很多事情，但是又没干什么事情，只是一个代码搬运机器。

可能休息，更多的是需要放下手头的事情，放下心中的执念，去到一个新的地方，去做一些随心所欲地事情，不受限制的到处乱转，亦或者是在家玩上几天，总之，或许我们需要的休息并不是睡多久的觉，而是真正能不被约束、放下手头要做的事情、暂时的放下那些所谓的目标和理想，放空心灵、随心所欲而不需要考虑任何的目的，可这却也是最珍贵的、最难以得到的境遇。

总而言之，对待生活、对待学业，我们唯一能做的，就是在迷茫、朦胧中，去记录、去做这些拥有所谓意义的事情，去试图找到调整的方法，去感受这过程中好的、坏的、种种一切。

写一篇这样流水账，记录一些有趣的算法，不去在意那些成绩与评议，只是在平淡的生活里去追求有意义的事情，或许我们才能够感受一切的意义。

过去已经凝固，我带着回忆向前

只是时常疏于保管，回忆也在改变着各自的形态。

这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-17 14:11:11

那咤 2 系列赛 题解

题目并非按照难度升序排序

谢罪

NOI 风格的 PDF 太难做了，有些公式放进去爆炸了（比如 T2 的 K），以及题面数据范围有误，谢罪。

疏忽考虑，奇怪原因导致 T1 SPJ 无法正确返回结果，谢罪。

T3 搬大样例搬串了，谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪……，错了哥。

没想到会换机房，科研做法忘记改存储地址了，谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪谢罪。

太多了谢不开了，错了哥。

第一次办模拟赛，经验不足，望原谅（想骂就骂吧，错了哥）。

网球君

P5959 [POI 2018] Plan metra - 洛谷

首先考虑树的形态，只会有两种情况：

• $1$ 与 $n$ 直接连边，其余点连向 $1$ 或 $n$。
• $1$ 与 $n$ 的路径上有一些点，其余的点都挂在这条链上。

对于第一种情况，要求所有的点的 $\left| d(1,i) - d(i,n) \right|$ 均相等。

考虑第二种情况，在 $1$ 号点与 $N$ 号点之间，必然有一条路径，在这条路径上的点 $i$ 都满足 $d(1,i) + d(i,n) = d(1,n)$。那么 $d(1,n)$ 就应该为

$$\min_{i = 1}^{n} {d(1,i) + d(i,n)}$$

如果我们选择了一个更大的作为 $d(1,n)$，那么小于它的点就无法放置了。

接下来我们需要做的操作就是在这条链上挂上一些节点，我们考虑在点 $i$ 上挂上点 $j$，那么需要满足 $d(1,j) - d(j,n) = d(1,i) - d(i,n)$。

我们设 $i,j$ 之间的边权为 $w$，那么 $d(1,j) = d(1,i) + w$，$d(j,n)$ 同理，两个减一下就有了这个式子。用 map 存一下即可。

大战

P12738 [POI 2016 R2] 口吃 Stutter - 洛谷

在这里我们称题目中要求的 $K_{2\times i} = K_{2\times i - 1}$ 的两个数称为一个配对。

时空均为 $O(n ^ 2)$ 的做法应该是好想的，看原题题解是设 $f_{i,j}$ 表示 $A$ 序列前 $i$ 个，$B$ 序列前 $j$ 个元素，满足条件的最大长度，转移的时候像其他公共子序列的题目一样转移就好。

这里我最开始想到的状态是 $f_{i,j,0/1}$ 表示 $A$ 序列前 $i$ 个，$B$ 序列前 $j$ 个，当前已经配对完成 / 还没有完成配对的最大长度。

转移时，对于 $A_i = B_j$ 的情况，我们记录 $A_i$ 和 $B_j$ 上一次出现的位置，记作 $pre_i$ 和 $pr_j$，那么转移就有：

$$f_{i,j,0} = \max(f_{i,j,0},f_{pre_i,pr_j,1} + 2)$$

发现当我们从最近的一个转移过来是不劣的，而由于转移时我们已经保证了 $A_i = B_j$，所以我们不需要再考虑 $i$ 的限制，只需要从 $B$ 序列中 $j$ 前面第一个与 $j$ 相同的位置 $k$，从 $f_{x,k}$ 转移过来即可，我们维护前缀最大值，直接转移即可。

题解：P12738 [POI 2016 R2] 口吃 Stutter - 洛谷专栏

首先考虑一个时空复杂度都是 $O(n^2)$ 的做法：

首先求出 $a_i,b_i$ 中的每一个数下一次的出现位置 $nxta_i,nxtb_i$。类似于正常的 LCS，设 $dp_{i,j}$ 为考虑 $a$ 的前 $i$ 项，$b$ 的前 $j$ 项的最长公共口吃序列长度，考虑向后转移，显然有以下转移：

• $dp_{i+1,j}\leftarrow dp_{i,j}$，$dp_{i,j+1}\leftarrow dp_{i,j}$；
• 特别地，若 $a_{i+1}=b_{j+1}$，则 $dp_{nxta_{i+1},nxtb_{j+1}}\leftarrow dp_{i,j}+2$。

由于空间限制只有 32MB，而当前的状态转移又无法进行滚动数组优化，考虑重新设计状态。

仔细分析转移过程，考虑如何将第二步写成能够滚动数组优化的形式。现在的转移过程是 $i\to nxta_{i+1}$，$j\to nxtb_{j+1}$，不如我们先将 $j$ 一步移动到 $nxtb_{j+1}$，并对当前状态进行标记，代表 $i$ 目前只匹配了一次，在转移的过程中，不断将 $i$ 往右移，不改变 $j$ 的值，直到发现 $a_i=b_j$（此时的 $j$ 就相当于原来的 $nxtb_{j+1}$），完成一次匹配。

这样我们只会从 $dp_i$ 转移到 $dp_{i+1}$，可以使用滚动数组优化。具体的转移可以参考代码。其中的一个细节是，若发现 $a_{i+1}=b_{j+1}$，我们只能将 $dp_{i+1,nxtb_{j+1},1}$ 更新，但是此时 $a_{i+1}=b_{nxtb_{j+1}}$，因此我们完成匹配时判断的是 $a_{i+1}$ 和 $b_j$ 是否相等。

魔丸

P7215 [JOISC 2020] 首都 - 洛谷

做法 $1$

可以考虑一种颜色 $c$，将它作为目标颜色，将它的所有结点从树中取出来。

这样可以确定最小的一棵连通子树使得所有颜色为 $c$ 的结点都在这棵连通子树上。

但是连通子树上会存在许多其他颜色的结点。这样可以确定很多形如“必须将颜色 $d$ 归为颜色 $c$ 才能达成目标”的颜色之间的关系。然而只将所有 $d$ 变成 $c$ 是不够的。

将这样的颜色关系进行连边。$c$ 连向 $d$ 表示 “必须将颜色 $d$ 归为颜色 $c$ 才能达成所有颜色为 $c$ 的结点组成一棵连通子树”。

根据这样的依赖关系，对所有颜色都去尝试连边，然后将图建立出来。

可以发现，想要满足“所有颜色为 $c$ 的结点组成一棵连通子树”，必须要将点 $c$ 可以到达的所有颜色都变成 $c$。答案等价于点数最少的缩点之后出度为 $0$ 的强连通分量的点数。

而连边可以使用重链剖分+线段树优化建图，建立同色结点形成的连通子树可以使用类似虚树的建立方法。

这种方法的时间复杂度是 $O(n\log ^2n)$，瓶颈在于线段树优化建图和确定连通子树上，这些的常数是低于点分治的，效率良好。

更优的理论复杂度

首先考虑一个 $n^2$ 的暴力，我们考虑对于每种颜色的点，维护一个队列，最初将所有与它颜色相同的点加入队列，随后将他的所有父亲节点加入，以及所有与它父亲颜色相同的点，这样相当于将所有必要的点都加入了，时间复杂度 $O(n^2)$。

发现有这样一条贪心性质：如果以 $y$ 为根时选到了颜色 $x$，则以 $x$ 为根的答案一定不会更劣。

换句话说：如果我们在统计点 $x$ 时发现要选颜色 $y$，但我们已经知道了以 $y$ 为根的答案，则无需继续统计这个 $x$，因为选择 $x$ 一定要选择 $y$，所以选择 $x$ 一定会包含选择 $y$ 的所有贡献，因此选择 $y$ 更优。

有了这个结论，我们考虑点分治，考虑选择分治中心作为这个点的最小次数，依旧维护队列，如果发现队列中元素位于当前子连通块外，则直接返回即可，否则假如有关的点，计算贡献取 $\min$ 即可，由于对于每个子连通块计算是 $O(size)$ 的，因此总时间复杂度 $O(n\log n)$。

掌牧松

CF1393E2 Twilight and Ancient Scroll (harder version) - 洛谷

考虑暴力，直接设 $f_{i, j}$ 表示前 $i$ 个字符串，第 $i$ 个删了第 $j$ 个字符的合法方案数。

直接暴力枚举前一个，然后暴力比较 $O(L^3)$。

然后可以将比较换成 hash 加二分比较时间复杂度 $O(L^2 \log L)$

然后考虑将 $s_{i, j}$ 排序，$s_{i, j}$ 表示字符串 $i$ 删除第 $j$ 个字符，这可以贪心排序，就是考虑字符串 $i$ 第一个不同的位置，如果 $a_i<a_{i+1}$ 那么删掉 $1\sim i$ 中的某个字符一定比删除 $i+1 \sim len$ 的某个字符字典序小，所以将 $1 \sim i$ 设成字典序前 $i$ 小；如果 $a_i > a_{i + 1}$ 是类似的。然后将前 $i$ 个字符删掉，继续重复即可。

然后现在设 $f_i,j$ 表示前 $i$ 个字符串，第 $i$ 个是 $s_i,k$ 中的吃第 $j$ 小时方案数。

然后 $f_{i,j}$ 一定由 $f_{i-1}$ 的某个前缀转移过来，而且如果 $j$ 增加，那么它能从 $f_{i-1}$ 转移过来的区间长度也增加。

所以那个指针扫一下，然后二分判断即可做到 $O(L\log L)$。

然后发现只会比较相邻的字符，维护三个数组，分别是偏移量为 $0,1,-1$ 时的 lcp，然后就可以 $O(1)$ 比较了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-15 15:07:45

P5994 [PA 2014] Kuglarz 题解

P5994 [PA 2014] Kuglarz - 洛谷

确实是一道非常深刻的题目。

感觉其他题解都没有讲出要点，或者讲明白我的疑点，于是记录下来，希望有所帮助。

题解主要说明了，如何想到建图，以及如何把区间询问问题转化为前缀问题，再转化成最小生成树的问题。

先来看这个问题

你有一个序列 $A$，现在你知道 $n$ 个区间 $[l,r]$ 的区间和。

同时给出 $Q$ 次询问，问你能否根据给出的 $n$ 个提示，求出 $\sum_{i = 1}^{x} a_i$ 的值，输出 yes 或 no。

我们考虑把给出的区间和转化为前缀和。设 $pre_i = \sum_{j = 1}^{i} a_j$，其中我们已知 $pre_0 = 0$。每次给出的信息相当于是给出 $pre_r - pre_{l - 1}$，于是我们只要知道了 $pre_{l - 1}$ 或 $pre_r$ 中的一个，就可以推出另一个。

我们将相互可以推出的 $pre$ 看作点，将给定的操作看作边，连边之后，同一连通块内的点可以相互推出值。

比如给出下面三个区间：

1 2
2 3
2 2

我们可以得到这样的图：

当知道了 $pre_0$，就可以知道 $pre_2,pre_3,pre_1$，发现这个东西可以使用并查集维护，位于同一集合内的点可以相互推出值。

这段参考了 (前缀和/并查集)代码源每日一题 Div1 区间和 - 知乎，并对题面进行了一点修改。

问题中的操作和建图有什么关系

看完前面的题目，好像和这道题目并没有什么关系。但我们发现，询问奇偶性的操作其实可以看作一段区间的异或值。也就是在下文中，奇偶性和异或和实际上是等价的。

设 $A_i = 0/1$ 表示第 $i$ 个杯子中有（没有）球，那么在本题中我们询问一个区间奇偶性相当于知道了区间异或和（这里可以自己思考一下）。

这里就解释了我不理解的第一个问题，为什么区间询问问题可以转化为前缀询问？

联系到上一题上，发现区间异或和操作可以转化为前缀异或和操作，令 $B_i = \oplus_{j = 1}^{i} A_j$，即前缀异或和，那么本题中一次询问就变成了上一题中给定的一个提示，询问 $[l,r]$ 后,在图上 $l - 1$ 与 $r$ 就联通了，也就是在图上 $l - 1$ 和 $r$ 之间连一条边。

我们考虑对于 $i$ 位置，想知道它有没有球，必须要选择一个 $j$，询问区间 $[j,i]$ 和区间 $[j,i - 1]$ 的异或和（这里应该是好理解的）。

发现询问区间 $[j,i]$ 的答案实际上就是询问 $B_i \oplus B_{j - 1}$，而 $[j,i - 1]$ 实际上就是询问 $B_{i - 1} \oplus B_{j - 1}$，我们只关心这两个的值是否相同，如果相同则 $i$ 没有球，否则有球。

以及第二个问题，为什么需要最小生成树？

由于只关心是否相同，所以两式子同时 $\oplus B_{j - 1}$ 是没有影响的。于是对于每个杯子 $i$ 求是否有球的过程，就转化为了询问 $B_i$ 与 $B_{i - 1}$ 的值，也就是我们需要求出每个 $B_i$。

换句话来说，想知道 $i$ 有没有球，最终都可以转化为询问 $B_i$ 和 $B_{i - 1}$ 的值，也就是我们需要在若干次询问之后做到能够知道 $B_i$ 和 $B_{i - 1}$ 的值。

由上一题我们已经知道，这样连边之后，对于同一连通块内的点可以相互求出值，也就是我们希望能把 $B_i(i \in [0,n])$ 连成一个连通块。

于是问题就转化完成了，即：

给定 $O(n^2)$ 条边，每条边 $(i - 1,j)$ 的边权为 $c_{i,j}$，需要找到一种最小花费使得 $0,1,2, \cdots ,n - 1,n$ 联通，于是把边存起来，做最小生成树就做完了。

#include<bits\/stdc++.h>
using namespace std;
#define int long long
struct note{
	int u,v,w;
}edg[4000010];
bool cmp(note x,note y) {return x.w < y.w;}
int fa[2010];
int getf(int x)
{
	if(fa[x] == x) return x;
	return fa[x] = getf(fa[x]);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n;
	cin >> n;
	int cnt = 0;
	for(int i = 1;i <= n;i++)
		for(int j = i;j <= n;j++)
		{
			int w;cin >> w;
			edg[++cnt] = {i - 1,j,w};
		}
	sort(edg + 1,edg + cnt + 1,cmp);
	int ans = 0;
	for(int i = 1;i <= n;i++) fa[i] = i;
	for(int i = 1;i <= cnt;i++)
	{
		int u = edg[i].u,v = edg[i].v,w = edg[i].w;
		u = getf(u),v = getf(v);
		if(u == v) continue;
		fa[u] = v;
		ans += w;
	}
	cout << ans;
	return 0;
}

使用了 kruskal，可以修改成 prim。

希望对你有所帮助。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-20 10:44:55

P12480 [集训队互测 2024] Classical Counting Problem 题解

P12480 [集训队互测 2024] Classical Counting Problem - 洛谷

题意

给定一棵 $n$ 个点的树，可以进行以下操作：

• 选择当前树上编号最大或最小的点，删除它以及以它为端点的所有边，并任选一个连通块作为新的树。
• 记 $min$ 为当前树上编号最小值，$max$ 为当前树上编号最大值，$size$ 为树上节点数量。定义一棵树的权值为 $max \times min \times size$，求能通过上述操作得到的非空树的权值和，答案对 $2^{32}$ 取模。

Solution

拿到题目，很难找到入手点，因此我们先来考虑一个性质：

• 一个 $min$ 和一个 $max$ 能够确定唯一的树。

我们考虑它的条件，$l,r (l \le r)$ 能确定一棵树的充要条件是，$l,r$ 路径上所有点编号都在 $[l,r]$ 之间。若不在则 $l,r$ 不能够作为 $min$ 和 $max$，否则可以从这条路径不断向外扩展，直到边界 $<l$ 或边界 $>r$，于是我们确定出一棵唯一的树。

此时我们容易得到一个 $O(n^3)$ 的做法，枚举 $l,r$，并 check $l,r$ 能否构成一棵合法的树。固定其中一个，移动另一个就可以做到 $O(n^2)$，可能需要带个 $\log$。

发现还需要继续优化，考虑拆贡献，可以将权值中的 $size$ 拆开，拆成对所有合法的 $(l,r,x)$ 三元组计算贡献，每个三元组的贡献就是 $l \times r$。问题转化为求树上有多少三元组 $(l,r,x)$，满足 $l,r$ 能确定一棵树并且 $x$ 位于 $l,r$ 确定出的树上。

考虑 $(l,r,x)$ 的关系大概是像下图中这样，按照 ez_lcw 课上讲的名字，称之为 “风车形”。

考虑点分治，对于每个风车，在风车上所有点中，点分树上深度最小的点上统计答案。假设红色点 $u$ 是统计答案的分治中心，需要满足 $l,r,x$ 均位于 $u$ 在点分树上的子树内，且其中至少两个点不在同一棵子树，也就是下图的两种情况。

其中 $u$ 是这个风车上，点分树上深度最小的点。

接下来问题变成，我们如何统计子树内所有 $(l,r,x)$ 三元组的贡献，我们设 $mi_u$ 表示从分治中心到 $u$ 的路径上最小值，$mx_u$ 表示从分治中心到 $u$ 路径上的最大值，首先可以发现合法的 $l,r$ 满足 $mi_l = l,mx_r = r$。

$$\begin{cases} mx_l \le r \\ mx_x \le r \\ mi_x \ge l \\ l \le mi_r \end{cases}$$

考虑扫描线，对于每个 $r$ 处统计答案，统计合法的 $(l,x)$ 对的贡献。

考虑该怎么处理得到的限制关系。把子树内每个点 $u$ 维护在 $mx_u$ 的位置，从前往后扫描线，这样我们就解决了前两条限制关系。考虑维护一棵线段树，线段树需要维护三个信息：

• 对于每个位置 $i$，$l = i$ 的 $l$ 的编号和 $sum$。
• 对于每个位置 $i$，$mi_x = i$ 的 $x$ 的数量 $cnt$。
• 对于每个位置 $i$，$l = i$ 的合法 $(l,x)$ 对的贡献和 $val$。

那么对于每个限制 $4$，也就是 $l \le mi_r$，相当于是在一段前缀 $[1,mi_r]$ 查询合法 $(l,x)$ 对贡献，我们把拆完的贡献中的 $\times min$ 在这里计算。

接下来考虑如何统计 $(l,x)$ 对的数量，这里就要用到第三条限制关系，考虑加入一个点，这个点作为 $x$ 和作为 $l$ 的情况。

• 这个点作为 $x$，此时对于 $l \le mi_x$ 的所有 $l$，$x$ 都能与之配对产生贡献。对于所有合法的 $l$，它能增加的贡献值也为 $l$，要对这些 $l$ 的 $val$ 加上他们对应的 $sum$。同时插入 $x$ 后，$mi_x$ 处的 $cnt$ 也要 $+1$。

• 这个点作为 $l$，此时我们需要计算这个 $l$ 能和多少 $x$ 产生贡献，发现就是询问 $mi_x \ge l$ 的 $x$ 的数量，由于前面我们对每个位置 $i$ 维护了 $mi_x = i$ 的 $x$ 的数量，这里可以直接区间查询，同时 $l$ 位置的编号和也需要增加。

对于第一类，我们需要对贡献值区间加对应的 $val$，同时需要区间查询 $val$，因此需要线段树维护 $val$ 区间加，区间求和。同时需要对 $cnt$ 单点加，因此需要维护单点加的 $cnt$。

对于第二类，需要询问区间 $cnt$ 和，对 $cnt$ 线段树维护区间和，同时需要对 $sum$ 单点加，因此对 $sum$ 维护单点加区间查。

想通如何维护之后这道题目就很简单了，实现不难，维护出需要的信息即可。每层维护线段树，复杂度为 $O(m \log m)$，其中 $m$ 为点的数量，总复杂度 $O(n \log ^ 2 n)$。

实现细节

• 注意到模数是 $2^{32}$，可以直接使用 unsigned int 存储，这样就不需要取模了。
• 对于每层值域需要离散化，否则每层都是 $O(n\log n)$ 的，总时间复杂度会变成 $O(n^2 \log^2 n)$。
• 要先加入 $l,x$，再询问 $r$。
• 由于需要去重，如果对每棵子树减去贡献，注意路径 $\min$ 和 $\max$ 的初始值。
• 该清空的要清空，该赋值的要赋值。

代码（常数巨大）

#include<bits\/stdc++.h>
using namespace std;
#define int unsigned int
int n,ans,rt,tot;
const int maxn = 1e5 + 10;
bool vis[maxn];
vector<int> G[maxn];

inline int read()
{
	int x = 0,f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch <= '9' && ch >= '0')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x * f;
}

inline void print(int x)
{
	if(x > 9) print(x \/ 10);
	putchar(x % 10 + '0');
}

struct note{
    int s[3],tag;  \/\/ s[0]:最小值之和, s[1]:计数, s[2]:贡献和
    note() {s[0] = s[1] = s[2] = 0;}
}tr[maxn * 13];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l + r) >> 1)

void pushup(int rt)
{
    for(int i = 0;i < 3;i++) 
        tr[rt].s[i] = tr[lson].s[i] + tr[rson].s[i];
}

void build(int rt,int l,int r)
{
    if(l == r)
    {
        for(int i = 0;i < 3;i++) tr[rt].s[i] = 0;
        tr[rt].tag = 0;
        return;
    }
    build(lson,l,mid);
    build(rson,mid + 1,r);
    pushup(rt);
}

void pushdown(int rt)
{
    if(tr[rt].tag)
    {
        \/\/ s[2] += tag * s[0] (最小值之和)
        tr[lson].s[2] = tr[lson].s[2] + tr[rt].tag * tr[lson].s[0];
        tr[rson].s[2] = tr[rson].s[2] + tr[rt].tag * tr[rson].s[0];
        tr[lson].tag += tr[rt].tag;
        tr[rson].tag += tr[rt].tag;
        tr[rt].tag = 0;
    }
}

void update(int rt,int l,int r,int x,int k,int id)
{
    if(l == r)
    {
        tr[rt].s[id] = tr[rt].s[id] + k;
        return;
    }
    pushdown(rt);
    if(x <= mid) update(lson,l,mid,x,k,id);
    else update(rson,mid + 1,r,x,k,id);
    pushup(rt);
}

void upd(int rt,int l,int r,int x,int y,int k)
{
    if(x <= l && r <= y)
    {
        tr[rt].s[2] = tr[rt].s[2] + k * tr[rt].s[0];
        tr[rt].tag += k;
        return;
    }
    pushdown(rt);
    if(x <= mid) upd(lson,l,mid,x,y,k);
    if(y > mid) upd(rson,mid + 1,r,x,y,k);
    pushup(rt);
}

note query(int rt,int l,int r,int x,int y)
{
    if(x <= l && r <= y) return tr[rt];
    pushdown(rt);
    note res, lss, rss;
    if(x <= mid)
    {
        lss = query(lson,l,mid,x,y);
        for(int i = 0;i < 3;i++) res.s[i] += lss.s[i];
    
    }
    if(y > mid)
    {
        rss = query(rson,mid + 1,r,x,y);
        for(int i = 0;i < 3;i++) res.s[i] += rss.s[i];
    }
    return res;
}

int siz[maxn],f[maxn];
void getroot(int u,int fat)
{
    siz[u] = 1;f[u] = 0;
    for(int v : G[u])
    {
        if(v == fat || vis[v]) continue;
        getroot(v,u);
        siz[u] += siz[v];
        f[u] = max(f[u],siz[v]);
    }
    f[u] = max(f[u],tot - siz[u]);
    if(f[u] < f[rt]) rt = u;
}

vector<int> vec;
int m,a[maxn * 3];
vector<int> q[maxn * 3];
int mi[maxn],mx[maxn];

void dfs(int u,int fa)
{
    mi[u] = min(mi[fa],u);
    mx[u] = max(mx[fa],u);
    a[++m] = mx[u];
    a[++m] = mi[u];
    a[++m] = u;
    vec.push_back(u);
    for(int v : G[u]) if(!vis[v] && v != fa) dfs(v,u);
}

int getans(int root,int fa)
{
	int res = 0;m = 0;
	vec.clear();dfs(root,fa); \/\/ 求出子树信息
	sort(a + 1,a + m + 1);
	m = unique(a + 1,a + m + 1) - a - 1;
	build(1,1,m);\/\/ 线段树建树是 O(size)
	
	for(int i = 1;i <= m;i++) q[i].clear();
	for(auto u : vec) 
	{
		int wz = lower_bound(a + 1,a + m + 1,mx[u]) - a;
		q[wz].push_back(u);\/\/ 离线扫描线 
	}
	for(int i = 1;i <= m;i++)
	{
		for(int u : q[i]) \/\/ add
		{
			\/\/ u 作为 x
			int mip = lower_bound(a + 1,a + m + 1,mi[u]) - a;
			update(1,1,m,mip,1,1);
			upd(1,1,m,1,mip,1);
			\/\/ u 作为 l
			if(mi[u] == u)
			{
				int p = lower_bound(a + 1,a + m + 1,u) - a;
				update(1,1,m,p,u,0);
				int ss = query(1,1,m,p,m).s[1];
				update(1,1,m,p,ss * u,2); 
			}
		}
		
		for(int u : q[i]) \/\/ query
		{
			if(mx[u] == u)
			{
				int mip = lower_bound(a + 1,a + m + 1,mi[u]) - a;
				res += query(1,1,m,1,mip).s[2] * u;
			}
		}
	}
	return res;
}

void divide(int u)
{
    mi[u] = mx[u] = u;
    ans += getans(u,u);
    vis[u] = 1;
    
    for(int v : G[u])
    {
        if(vis[v]) continue;
        ans -= getans(v,u);
    }
    
    for(int v : G[u])
    {
        if(vis[v]) continue;
        tot = siz[v];
        f[rt = 0] = 1e9;
        getroot(v,0);
        divide(rt);
    }
}

int solve()
{
    n = read();
    for(int i = 1;i < n;i++)
    {
        int u = read(),v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    tot = n;
    f[rt = 0] = 1e9;
    getroot(1,0);
    getroot(rt,0);  \/\/ 重新计算size
    divide(rt);
    
    print(ans);puts("");
    return 0;
}

signed main()
{
\/\/	ios::sync_with_stdio(false);
\/\/	cin.tie(0);cout.tie(0);
    int t = read();
    while(t--) 
    {
        solve();
        \/\/ 清空
        for(int i = 1;i <= n;i++) G[i].clear(),vis[i] = 0;
        ans = 0;
    }
    return 0;
}

希望对你有所帮助。

本人 $900$ AC 祭，伟大的点分治！伟大的 ez_lcw！

祝各位 CSP - S rp++。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-27 07:24:37

写在前面

一道非常不错的题目，侧重思维的 DS 好题，这篇题解是写给自己的题解，应该会比较详细 有错误或疑问可以私信或评论。

题意

P14311 【MX-S8-T4】平衡三元组

给定一个长度为 $n$ 的序列 $a$，并给出 $q$ 次询问，询问有两种。

• 给定 $l,r$，你需要选择 $l \le x < y < z \le r$ 的 $x,y,z$，满足 $a_y - a_x \le a_z - a_y$，求最大的 $a_x + a_y + a_z$。
• 给定 $l,r,x$，对 $i \in [l,r]$ 内每个元素 $a_i$ 加 $x$。

$n \leq 10^6,q \le 5 \times 10^4,a_i \le 10^9$。

Solution

首先转化一下题目条件，实际上是要求 $2a_y \le a_x + a_z$，由此我们发现，当 $a_x$ 和 $a_z$ 更大的时候是一定不劣的，我们可以枚举 $y$，维护前后缀最大值，则 $a_x$ 一定是 $[l,x)$ 的最大值，$a_z$ 一定是 $(x,r]$ 的最大值。

有了这个做法，我们不难发现，$a_x$ 与 $a_z$ 中一定有一个是区间最大值，考虑分两种情况分析：

• 当 $a_y$ 取得全局最大值，由于 $2a_y \le a_x + a_z$，所以 $a_x$ 和 $a_z$ 只有和 $a_y$ 相等才会合法。
• 当 $a_y$ 不为全局最大值，此时 $a_x$ 和 $a_z$ 包含了前缀和后缀最大值，也就是包含了整个区间，所以一定有一个是全局最大值。

由此，我们可以先钦定 $a_x$ 作为最大值，统计答案，对于 $a_z$ 的情况同理，只需要反过来做一遍就行了。

考虑 $a_x$ 作为最大值，此时找到 $(x,r]$ 的最大值，记他的位置为 $k$。

• 当 $z = k$ 时，也就是 $z$ 作为 $(x,r]$ 的最大值，此时 $a_x$ 和 $a_z$ 已经是区间 $[x,r]$ 的最大值，因此对于所有 $y \in (x,k)$ 都有 $a_y \le a_x$ 且 $a_y \le a_z$，直接查询区间最大值统计答案即可。
• 当 $y = k$ 时，发现 $z$ 越大一定是不劣的，因此我们需要在 $(k,r]$ 的区间内找到一个最大值，设为 $p$，并尝试统计答案。

对于第二种情况，如果它已经合法，那么对于其它的 $z \in (k,r],z \neq p$，一定不优于 $p$，直接统计答案就结束了。

否则由于它不合法，而 $z = p$ 已经取到 $(k,r]$ 的最大值，$(k,r]$ 内不会有数能够与 $x,k$ 构成合法的三元组，因此只能考虑在 $(k,r]$ 内重新找到一个 $y$，再按照这个方法找到 $z$，直到找到一个合法方案或区间长度不合法。

不难发现我们进入了一个类似的子结构，直接递归查找即可，$a_z$ 作为全局最大值的情况同理，使用线段树维护区间最大值及其位置，维护区间加操作即可。

复杂度分析

这里参考了官方题解的复杂度分析，考虑设 $[l,r]$ 的最大值为 $x_0$，位置为 $p_0$。设区间 $(p_0,r]$ 的最大值为 $x_1$，位置为 $p_1$，依此类推，可以得到 $x_2,x_3 \dots x_m$。

考虑确定 $x$ 为区间最大值，一对 $y,z$ 不合法的条件是 $a_x + a_z < 2a_y$，即 $x_0 + x_2 < 2a_1$，移项得 $x_2 < 2x_1 - x_0$。

考虑递归进下一层，依旧不合法的条件是 $x_0 + x_3 < 2 x_2$，移项得 $x_3 < 2 x_2 - x_0$。

联立得出的两个式子，可得 $x_3 < 2x_2 - x_0 < 2 \times (2x_1 - x_0) - x_0$，也就是

$$x_3 < 2x_2 - x_0 < 4x_1 - 3x_0$$

归纳一下这个式子，也就是

$$x_i < 2^{i - 1}x_1 - (2^{i - 1} - 1)x_0$$

$$x_i < x_0 - 2^{i - 1}(x_0 - x_1)$$

当 $x_0 = x_1$，不妨从 $x_1$ 开始归纳，而当出现 $x_0 = x_1 = x_2$，则直接统计答案就是最优的。由此，递归层数只有 $O(\log V)$ 层，可以直接递归统计答案。

Code

#include<bits\/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 10;
int a[maxn];
struct note{
	int lx,rx,mx;
};
note tr[maxn << 2];
int tag[maxn << 2];
#define lson (rt << 1)
#define rson (rt << 1 | 1)
#define mid ((l + r) >> 1)
void pushup(int rt)
{
	if(tr[lson].mx == tr[rson].mx)
	{
		tr[rt] = tr[lson];
		tr[rt].rx = tr[rson].rx;
		return;
	}
	tr[rt].mx = max(tr[lson].mx,tr[rson].mx);
	tr[rt] = (tr[rt].mx == tr[lson].mx ? tr[lson] : tr[rson]);
	return;
}
void build(int rt,int l,int r)
{
	if(l == r)
	{
		tr[rt].mx = a[l];
		tr[rt].lx = tr[rt].rx = l;
		return;
	}
	build(lson,l,mid);
	build(rson,mid + 1,r);
	pushup(rt);
	return;
}
void pushdown(int rt)
{
	if(!tag[rt]) return;
	tr[lson].mx += tag[rt];
	tr[rson].mx += tag[rt];
	tag[lson] += tag[rt];
	tag[rson] += tag[rt];
	tag[rt] = 0;
	return; 
}
void update(int rt,int l,int r,int x,int y,int k)
{
	if(x <= l && r <= y)
	{
		tr[rt].mx += k;
		tag[rt] += k;
		return;
	}
	pushdown(rt);
	if(x <= mid) update(lson,l,mid,x,y,k);
	if(y > mid) update(rson,mid + 1,r,x,y,k);
	pushup(rt);
	return;
}
note query(int rt,int l,int r,int x,int y)
{
	if(x <= l && r <= y) return tr[rt];
	pushdown(rt);
	note res,ls,rs;
	int cnt = 0;
	if(x <= mid) ls = query(lson,l,mid,x,y),cnt++;
	if(y > mid) rs = query(rson,mid + 1,r,x,y),cnt += 2;
	if(cnt == 1) return ls;
	if(cnt == 2) return rs;
	if(ls.mx == rs.mx)
	{
		res = ls;
		res.rx = rs.rx;
	}
	else
	{
		res.mx = max(ls.mx,rs.mx);
		res = (res.mx == ls.mx ? ls : rs);
	}
	return res;
}

int ans;
int n,q;
void ql(int l,int r,int mx)
{
	if(l >= r) return;
	auto it = query(1,1,n,l,r);
	if(it.lx != r) ans = max(ans,mx + it.mx + query(1,1,n,it.lx + 1,r).mx);
	if(it.rx == l) return;
	auto xx = query(1,1,n,l,it.rx - 1);
	if(2 * it.mx <= mx + xx.mx) 
	{
		ans = max(ans,it.mx + mx + xx.mx);
		return;
	}
	ql(l,it.rx - 1,mx);
}

void qr(int l,int r,int mx)
{
	if(l >= r) return;
	auto it = query(1,1,n,l,r);
	if(it.rx != l) ans = max(ans,mx + it.mx + query(1,1,n,l,it.rx - 1).mx);
	if(it.lx == r) return;
	auto xx = query(1,1,n,it.lx + 1,r);
	if(2 * it.mx <= mx + xx.mx) 
	{
		ans = max(ans,it.mx + mx + xx.mx);
		return;
	}
	qr(it.lx + 1,r,mx);
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	cin >> n >> q;
	for(int i = 1;i <= n;i++) cin >> a[i];
	build(1,1,n);
	for(int i = 1;i <= q;i++)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			int l,r;
			cin >> l >> r;
			ans = -1e9;
			auto it = query(1,1,n,l,r);
			int mx = it.mx;
			ql(l,it.rx - 1,mx);qr(it.lx + 1,r,mx);
			if(ans == -1e9) cout << "No\n";
			else cout << ans << "\n";
		}
		else
		{
			int l,r,x;
			cin >> l >> r >> x;
			update(1,1,n,l,r,x);
		}
	}
	return 0;
}

本人代码常数较大，祝大家 CSP-S2025 rp++。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-30 16:55:00

考前注意事项总结

CSP-S 2025 rp++

常规要求

• 进场 40min 不能写题，把所有题读一遍看一遍，不准碰键盘，先读完题，估计自己能有多少分，分析好策略。
• 不要对题目难度和自己发挥有任何预设，分析好部分分，规划好时间，打出自己的真实水平就好，不要对线有任何预设，只要发挥好自己水平就行。
• 考试做完每个题要备份一次，每写完一个题备份一次，复制一遍，防止编译覆盖文件。
• 结束前 10min 不能再写代码了，检查文件，检查文件输入输出，检查 CE 等。
• 想到什么尽快写出来，不要全都压在手里，到最后写不完。
• 写代码时，防止错误？写完每个部分或每个函数之后把自己上一个函数读一遍，检查代码，减少错误概率。
• 卡题了可以先想想别的，考场上不要乱搞，平常怎么打就怎么打。
• 前两题一般是签，分析一下可以直接考虑冲正解。
• 稳住心态！！！

算法等注意事项

• 关流 cin 不能和 scanf printf getchar putchar 等混用。
• 手写快读记得判断需不需要判负数，define int long long 要注意计算空间，不 define int long long 要把所有可能需要的地方都开 long long。
• 不要看到觉得简单就开始死扣，及时验证算法正确性。
• 点分治不能处理定根路径。
• 写 1 << k 注意要不要写 1ll << k。
• 扫描线记得判断询问区间是否合法，使用线段树记得判断查询及修改区间。
• 线段树调试优先输出 rt,l,r 观察，判断边界条件。
• 写代码要先理清逻辑，不要模糊不清就直接开写，这样非常容易卡住。
• 多测清空，可以适当多清一点，尽量把所有的都清空。
• 注意边界条件，注意下标，注意区分 $n,m$，尤其是在 kruskal 的时候。
• STL 访问时判断是否存在元素。
• 扫描线加入元素的时候不要把 while 写成 if。
• ST 表如果要维护贡献区间算贡献，对于有重复的部分，记得钦定在左端或右端计算贡献！具体的，前后两边单调栈一个 $\leq$，另一个 $<$。
• 不要有任何预设！！！！打出水平就好

系统使用

• Linux 下编译指令 g++ a.cpp -o a -O2 -std=c++14 -Wall -Wextra，一定注意不要把 a.cpp 和 a 写反，否则会直接覆盖掉，无法找回代码。
• Windows 下记得开栈开 O2。
• 调试记得先把同步流打开，否则看不到输出。
• 可以把大样例文件夹粘过来，但是要看一下是不是相同的名字（一般相同吧）。
• 记得先看好题目时间限制和空间限制，写之前先计算好。
• 能用的时间很少，一定要把握住每一分钟！！！不要空想！！！不要想着休息一下！！！不要想着时间还有很多！！！

考前思维及 trick 选记

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-02 19:02:35

写在前面

也算是正式开始训练之后参加的第一届 CSP 了，感觉发挥并不好，好在是有进步，也算一个不错的开始

只怕幸福眼看完整，我的心却早已冰冷。

省流：打的不好，但也算预期之内，可惜去不了 WC。

浮云一别后，流水十年间。

Day.-4 （10.27）

考前一周感冒了，一直精神状态不佳，做不进去题了，好在应该比赛时就恢复了。在 wfbczx 呆了一个月，感觉提升还是蛮大的，最后一周细算也糊弄了 $10$ 场模拟赛，但是打的都很烂。

Day.-2 （10.29）

最近太累了，决定开摆，回了 wfyz。下午举行了赛前神秘仪式，吃了一些东西（疯狂打球），终于又见到 KSCD_ 和 Dtw_ 以及其他同学，玩的很开心。

仪式上 lxn 用出了 zms 专武，"无所谓，我不 care"，感觉很搞笑。

人生天地间，忽如远行客。

Day.0 （10.31）

早上终于睡了懒觉，睡到 $7:30$ 才醒，吃完饭去学校。上午去找了 typ，还得到了合照。下午去酒店，环境和条件都非常不错，点赞。KSCD_ 分到了同层的亲子房，笑发财。

吃完饭在酒店，刚洗完澡被 KSCD_ 爆破了两次，吓哭了。 下车时还发现自己鞋子和 KSCD_ 是同款，连买的时间都是一样的，牛牛牛。

晚上去试机，遇到了 wfbczx 的同桌以及同考场的 xz，随机到一个非常好用的键盘，应该是 J 组小朋友给换的，非常高兴，出场拍了很多合照。

回酒店刷了会视频，$23:00$ 就睡了，但是想了很多东西，晚上醒来好几次，还做梦梦见自己 T2 不会，T1 也写麻烦了，最后 $70 + [68,84] + 20 + 30$ 离场，吓哭了。

Day.1 （11.1）

Day 1.3

早上起的很早，起来打了缩点板子，结果建图又建错了，遂开摆，上午去 Iceturky 屋玩，滑梯很刺激，Dtw_ 说要回去学马拉车和 KMP，感觉 KMP 不会考，所以给他讲了讲马拉车，没有复习 KMP。

Day 1.6

下午去考场，中午醒的很早，心里怦怦跳，看来正式比赛来了还是会紧张。

进场很顺利，没有需要排队，发现自己键盘还在。

开题，按照 tby 的要求前 40min 不能写题，可能是我没有理解好，前 40min 只在想前两个题，导致没有做好规划。

看到 T1，想到了之前自己做过的一个，但是那个题只有 $2$ 类，考虑了一会反悔贪心，发现如果 A 不合法了那么 BC 无论怎么放都是合法的，所以直接最开始放到最大的，然后反悔一下就好了，进场只看了 30min 就开始写了 T1，调了一下细节过掉了大样例。

此时 $15:10$，信心大增，吃了一块士力架（怎么感觉旁边人一直看我屏幕），然后看到 T2，最开始嘟错题了，一直想错了，甚至想出了加边最小生成树，发现嘟错题后开始急了，很久没有新思路，旁边 xz 貌似还出事故了，监考老师有点吵。

觉得不能就这样弃了， $16:00$ 以为已经 2h 了，开始急了，于是出去洗了把脸强制自己冷静下来，想了一会又想到了 Tree-MST，于是想到了类似 Boruvka 的东西，写了复杂度 $O(m \log m + 2^k nk(\lpha + \log n)$，也就是枚举之后排序，场上没有想到更好的优化方法，于是大样例 $0.9s$ 就直接开后面的了。

Day 1.75

屋漏偏逢连夜雨，船迟又遇打头风。

此时决策失误了，犯了场上大忌，开始对题目算法有预设了，看到 T3 题面感觉要用到 KMP 之类东西，于是看了看 T4 部分分，看到至少以为要用到二项式反演，于是粗略浏览一下觉得自己只会 $n!$ 的做法，于是去看了 T3。

T3 感觉写个特殊性质跑路就比较不错，想了一下决定先去开特殊性质 B，想到了一个类似扫描线的东西（好像和正解是差不多的？），写完已经还剩 40min 了，但是样例挂了，此时开始慌了，不敢赌自己的代码能力，于是开始写暴力了，写了 $L_1 \times L_2$ 的最低档暴力，又写了 T4 阶乘，此时时间不多了，又没有看 T4 暴力而是去调 T3，于是最后都只剩下最低档暴力。

Day 1.8

似此星辰非昨夜，为谁风露立中宵。

出场有点茫然，感觉自己打的很烂，不知道该何去何从，也不知道还能不能继续冲，又被吓哭了。

知道自己 WC 是不用想了，预计只有 $100 + [80,100] + 25 + 8$，大家好像打的都不太好，貌似 T2 都读错题了，KSCD_ 貌似发挥的不好，但是 chb 好像 AK 了。回去路上玩了一路，但是太卡了连跪了，回家没有困意看了很久视频，很晚睡觉了。

晚上做梦梦见自己 T2 挂大分，只剩 $15$ 了，又双叒叕被吓哭了。

Day.2

起床就听到手机一直在响，打开原来是云斗已经出批量评测了（芸豆还是太强），发现云斗 T3 居然给了 $55$，云斗评测 $100 + 80 + 55 + 12$，貌似也算预期之内，只能说发挥不好但也没有全崩掉。

下午突然回忆自己 T2 快写会不会没写 ll，依旧吓哭了看到云斗的提交发现虚惊一场。

知道 KSCD_ 和 Dtw_ 打的都不好，好在是 CSP，相信 NOIP 会赢的。

后记

知不可乎骤得，托遗响于悲风

在看自己题解的过程中，发现很多题自己并没有吃透，总结来说还有很多需要加练的地方。至于心理上与心态上的短板，想必是需要时间慢慢打磨。

过去已经凝固，我带着回忆向前。

只是时常疏于保管，回忆也在改变着各自的形态。

这给我的追忆旅程带来些许挑战。

我该在哪里停留？我问我自己。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-07 09:51:36

前言

由于自己的排列组合能力实在太差了，感觉计数类问题很多原理都是相互纠缠的，于是写一篇学习笔记记录，也便于自己以后复习。

Part.1 基础知识

• 组合数 $$\binom{n}{m} = C_n^m = \frac{n!}{m! (n - m)!}$$
• 排列 $$A_n^m = \frac{n!}{(n - m)!}$$

Part.2 二项式定理

$$(a+b)^n = \sum\limits_{i=0}^{n} {n\choose i} a^i b^{n - i}$$

:::success[推导] $(a + b)^n$ 可以写成 $(a+b)(a+b)(a+b)\cdots(a+b)$，考虑把它展开的过程，实际上就是从每个 $a+b$ 种选择 $a,b$ 其中一个乘进去。

式子中共有 $n$ 个 $a+b$ 因此每一项的次数均为 $n$，枚举 $i$ 表示多少个 $a+b$ 选出乘的是 $a$，剩下的 $n - i$ 个则为 $b$，于是就有了二项式定理的式子。 :::

Part.3 组合数递推公式

$${i\choose j} = {i - 1\choose j} + {i - 1\choose j - 1}$$

:::success[组合意义证明] 我们先从组合意义理解这个式子，考虑 $i\choose j$ 的组合意义为从 $i$ 个选出 $j$ 个的方案数，考虑第 $i$ 个元素有两种情况：

• 选第 $i$ 个元素作为第 $j$ 个被选出的，则前 $i - 1$ 个元素中选出了 $j - 1$ 个，即为 $i - 1\choose j - 1$。
• 不选第 $i$ 个元素，相当于前 $i - 1$ 个元素中选 $j$ 个，即为 $i - 1\choose j$。

运用加法原理把两种情况方案数相加，即可得出递推式。 :::

:::success[代数证明] $$ \begin{pmatrix} a - 1 \ b - 1 \end{pmatrix} + \begin{pmatrix} a - 1 \ b \end{pmatrix} $$

$$ = \frac{(a - 1)!}{(a - b)!\cdot (b - 1)!} + \frac{(a - 1)!}{(a - b - 1)!\cdot b!} $$

$$ = \frac{(a - 1)(a - 2)\cdots(a - b + 1)}{(b - 1)!} + \frac{(a - 1)(a - 2)\cdots(a - b)}{b!} $$

提公因式，得原式

$$ = (a - 1)(a - 2)\cdots(a - b + 1)\cdot\left(\frac{1}{(b - 1)!} + \frac{a - b}{b!}\right) $$

$$ = (a - 1)(a - 2)\cdots(a - b + 1)\cdot\left(\frac{b}{b!} + \frac{a - b}{b!}\right) $$

$$ = (a - 1)(a - 2)\cdots(a - b + 1)\cdot\frac{a}{b!} $$

$$ = \frac{a(a - 1)(a - 2)\cdots(a - b + 1)}{b!} $$

$$ = \frac{a!}{(a - b)!\cdot b!} = \begin{pmatrix} a \ b \end{pmatrix} $$

证毕！ :::

如何预处理组合数

• 当数据范围较小时，我们可以直接递推预处理组合数，即使用上面的公式递推，注意处理边界情况。
• 当数据范围较大，此时我们就不能 $O(n^2)$ 处理，需要更优的复杂度。考虑使用 Part.1 的定义式，直接预处理阶乘和逆元，每次可以 $O(1)$ 计算组合数。

Part.4 杨辉三角与组合数之间的关系

在初中数学课本上经常出现杨辉三角与 $(a+b)^n$ 各项系数之间的关系，之前一直没有搞懂。

:::info[杨辉三角图] :::

:::info[杨辉三角与组合数？]{open} 我们令杨辉三角行列均从 $0$ 开始编号，设 $f_{i,j}$ 表示杨辉三角第 $i$ 行第 $j$ 列得值，考虑杨辉三角得递推式 $f_{i,j} = f_{i - 1,j} + f_{i - 1,j - 1}$，发现这个式子和组合数递推公式 $C_i^j = C_{i-1}^j + C_{i - 1}^{j - 1}$ 是相同的，由此我们可以得出 $f_{i,j} = C_i^j$，也就是杨辉三角第 $i$ 行第 $j$ 列的值就是 $i\choose j$。 :::

:::info[杨辉三角与二项式定理？]{open} 由二项式定理的式子 $$(a+b)^n = \sum\limits_{i=0}^{n} {n\choose i} a^i b^{n - i}$$ 我们就不难看出，展开后每一项的系数其实就是 $n\choose i$，由上面杨辉三角与组合数的关系，可以发现对于 $(a+b)^n$ 的各项系数实际上就是杨辉三角第 $n$ 行每一项的值。 :::

Part.5 组合数的性质

:::info[对称恒等式]{open}

$${n \choose k} = {n \choose n - k}$$ 考虑选出 $k$ 个数之后，能确定出唯一的补集，于是得出这个式子。 :::

:::info[吸收恒等式]{open} $${n \choose k} = \frac{n}{k} {n - 1 \choose k - 1}$$ 组合意义不太好想，考虑把 Part.1 的式子拆开，就能得到这个式子。 :::

::::info[杨辉三角行求和]{open} $${n\choose 0} + {n\choose 1} + \cdots + {n\choose n} = 2^n$$ :::success[推导] 考虑组合意义，从 $n$ 个元素中选出任意个的方案数之和，那么就是每个元素选或不选，总共 $2^n$ 种方案。

代数的证明，我们取二项式定理中 $a=1,b=1$ 的特殊情况，那么有 $(1 + 1)^n = \sum\limits_{i=0}^n {n\choose i}$，即上面的式子。 ::: ::::

::::info[杨辉三角列前缀和]{open} $$\sum\limits_{i = k}^n {i \choose k} = {n +1\choose k + 1}$$ :::success[推导] 考虑讲 $\sum$ 展开，变成了

$${k\choose k} + {k + 1\choose k} + \cdots + {n\choose k}$$

其中 ${k\choose k} = {k + 1 \choose k + 1}$，由组合数递推公式，依次合并相邻两项，得原式

$$= {n \choose k + 1} + {n\choose k}$$ $$= {n + 1\choose k + 1}$$ ::: ::::

::::info[范德蒙德卷积]{open} $$\sum\limits_{i = 0}^k {n\choose i}{m\choose k-i} = {n + m\choose k}$$ :::success[推导] 证明考虑使用二项式定理。

$$\sum\limits_{k = 0}^{n + m} {n + m\choose k} x^k = (x + 1) ^ {n + m}$$

$$= (x + 1)^n(x + 1)^m$$

$$= \sum\limits_{r = 0}^h {n\choose r} x^r \sum\limits_{s = 0}^m {m\choose s} x^s$$

$$= \sum\limits_{k=0}^{n+m} \sum\limits_{r=0}^k {n\choose r} {m\choose k - r} x^k$$

可得 $$\sum\limits_{r=0}^{k} {n\choose r}{m\choose k-r} = {n+m\choose k}$$ ::: ::::

::::info[不知名性质]{open} $${n\choose m} {m\choose k} = {n\choose k} {n - k \choose m - k}$$

:::success[推导] 组合意义上，考虑这个式子，实际上是先从 $n$ 个元素里选出 $m$ 个，再从这 $m$ 个中选 $k$ 个。

考虑先选出这 $k$ 个作为 $m$ 的一部分，然后从剩下的 $n-k$ 个中选出另外的 $m - k$ 个，也就是这个式子。

::: ::::

Part.6 多重集排列

$n$ 个球有 $k$ 个种类，每一类有 $a_i$ 个完全相同的球，求这 $n$ 个球的排列数。

这里用一种类似容斥的考虑方式，由于同一种类之内的排列是相同的，这一类被算重了 $a_i!$，因此我们考虑从 $n!$ 种排列内去掉每一类算重的贡献。

具体的，对于每一类 $i$ 我们要从 $n!$ 除掉这一类的贡献 $a_i!$，最终答案也就是

$$\frac{n!}{\prod\limits_i a_i!}$$

Part.7 两道简单题

Shaass and Lights

:::info[Hint] 发现点亮的灯会把整个序列划分为若干连续段。 ::: :::success[Solution] 做过的第一道多重集排列！

发现连续段之间互不影响，因此考虑对于每个连续段计算方案数，发现连续段只能从两个端点向内扩展。

因此每个连续段 $i$ 内方案数为 $2^{len - 1}$，然后考虑总排列数，由于同一连续段内方案数已经固定了，要从总排列数中去掉，最终答案大概就是

$$\frac{n!}{\prod\limits_i len_i!} \times \prod\limits_i 2^{len_i}$$ 需要注意处理两端的边界情况，边界只有一种点亮方案。 :::

Count Sequences 2

:::warning[一个并不正确的做法？] 场上很快就想到了一个多重集排列做法，设 $s = \sum\limits_{i = 1}^n c_i$，则最终方案数为 $$\frac{s!}{\prod\limits_i c_i}$$ 这也就是这个题多重集排列的理解方式，但我们发现模数是给定的，不保证质数也不保证互质，因此不好处理逆元，于是考虑换种做法。 :::

:::success[Solution] 考虑每次从剩下的位置中选择 $c_i$ 个位置放上，然后剩余的位置就会减少 $c_i$ 个，直接从 $1$ 到 $n$ 依次做即可。 :::

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-09 13:20:19

11.3 ~ 11.8 集训记录

做题记录

P14362 [CSP-S 2025] 道路修复 / road（民间数据） - 洛谷

S T2，场上只写了 $80$ 的做法，把所有边预排好序就可以少一只 $\log$，可以通过。

P14361 [CSP-S 2025] 社团招新 / club（民间数据） - 洛谷

反悔贪心，场上想了一会发现只会有一组不合法，所以反悔贪心就行了。

P14363 [CSP-S 2025] 谐音替换 / replace（官方数据） - 洛谷

比较难实现的题，思路比较清晰。

首先发现 $s_1,s_2$ 不同的部分一定与 $t_1,t_2$ 不同的部分相同，另一个限制是，$s_1,s_2$ 的公共前缀是 $t_1,t_2$ 公共前缀的后缀，同时后缀是公共后缀的一段前缀，于是考虑搞到 trie 树上，对于每个询问相当于查询有多少合法 $s$ 使得 $t$ 位于 $s$ 的子树内，相当于给定若干个矩形，查询每个点被多少个矩形覆盖。

P7416 [USACO21FEB] No Time to Dry P - 洛谷

一道扫描线，有以下做法：

• 莫队
• 离线到右端点，$i$ 从左向右扫的过程中维护 $j \le i$ 的每个 $[i,j]$ 的答案，设 $pre_i$ 表示上一个和 $i$ 颜色相同的位置，则 $\min_{j = pre_i}^{i} a_j$ 决定这一段要不要新染色，区间 rmq。
• 考虑对每个点维护 $pre$ 表示上一个相同颜色位置，如果这之间有更小的数则需要染两次，考虑把所有需要单独染色的区间重新编号，询问变成了查询区间颜色数，离线扫描线算贡献即可。

P9196 [JOI Open 2016] 销售基因链 / Selling RNA Strands - 洛谷

和 CSP T3 有点像的题，考虑查询同时包含前缀和后缀，把所有串插入一棵 trie，同时把串反转插入另一棵 trie，每次查询相当于是正反串分别位于两棵子树，把正反串在相应 trie 上的 dfn 看作 $x,y$，相当于是二维数点问题，然后就做完了。

P2163 [SHOI2007] 园丁的烦恼 - 洛谷

P6801 [CEOI 2020] 花式围栏 - 洛谷

P10096 [ROIR 2023] 扫地机器人 (Day 1) - 洛谷

三个比较简单的扫描线题。

P7554 [COCI 2020/2021 #6] Index - 洛谷

首先考虑一个 $\log^2$ 的做法，建出主席树，发现符合单调性，直接二分答案 check 即可，大常数，但也能过。

考虑直接在主席树上二分，每次查找区间后缀是否有 $mid \le k$ 个数合法，这样就是单 $\log$，跑得飞快。

11.4 模拟赛

T1

AT_joisc2013_joi_poster JOIポスター (JOI Poster) - 洛谷

简单计算几何，但是出题人没有卡精度，其实可以两边同时平方一下，这样就可以避免浮点数运算。

T2

P9906 [COCI 2023/2024 #1] Kocke - 洛谷

模拟赛 T2，观察到最后贡献的是一段区间，记录区间长度以及最后一个数是什么，转移即可。

T3

P10230 [COCI 2023/2024 #4] Lepeze - 洛谷

首先考虑次数是好算的，因为原本连接的边一定不会再动他，设 $ind_i$ 表示 $i$ 连接的对角线数量，次数就是 $n - 3 - ind_i$。

接下来考虑方案，手模一下会发现，这些原本连接的对角线会把整个多边形分成若干个块，每个块内的方案数是独立的，发现各个三角形之间的顺序形成了一棵树形结构，那么最后方案数也就是对这棵树的拓扑序计数。

考虑树的拓扑序数量是 $\frac{n!}{\prod_i siz_i}$，现在问题在于如何维护 $siz_i$。

注意这样一个结论，对于以 $l,r$ 为端点的一段区间（多边形上一段弧），它所包含的三角形数量，也就是 $siz$ 为 $r - l - 1$，于是我们需要考虑如何维护。考虑设 $mul_i$ 表示不经过 $i$ 的区间 $l,r$ 的 $siz$ 的乘积，那么每次询问就是 $fac_{n - 3 - ind_i} \times inv_{mul_i}$。难点在于如何维护 $mul$，考虑加入一条对角线相当于是对两端的所有点都乘上对面弧的贡献，删除相当于是乘上逆元，区间修改单点查询，可以差分一下变成单点修前缀查，树状数组维护即可，注意实现的时候梳理好区间端点，细节比较多。

T4

P10209 [JOI 2024 Final] 路网服务 2 / Road Service 2 - 洛谷

这场模拟赛总结下来，前面简单题花费太多时间，而且被卡题了，但是 NOIP 时间比较长，所以要抓住时间做事情，做好时间分配。

11.4 晚 限时训练

20251104限时训练 - Virtual Judge

比较简单的几个题：

A

直接维护每个数字出现次数，维护贡献即可。

B

考虑枚举 $a^b$ 的 $b$，然后 check 一下就好了。

C

考虑分别维护出每种情况出现的方案数与贡献，乘起来即可。

D

考虑枚举行的区间，发现对于每个数作为最小值贡献区间多选一定不劣，于是维护单调栈和前缀和即可，相似的题还有奥林匹克楼梯。

E

上面写了，主席树上二分即可。

11.3 上午 限时训练

11.03限时训练补题 - Virtual Judge

T1

CF1006F Xor-Paths - 洛谷

看到数据范围，直接折半搜索在中点处合并即可。

T2

P14192 [ICPC 2024 Hangzhou R] Fuzzy Ranking - 洛谷

首先不难想到建图之后把强连通缩起来，这样同一个强连通内的点对之间都是模糊的。

接下来需要注意到一个性质：对于每个序列相当于图上的一条链，而一条链上同一个强连通内的点是连续的。

考虑到这一点之后，我们就可以直接维护答案，对整个的区间进行前缀和，每次查询把整个区间的贡献和两个端点处的贡献加起来即可。

T3

AT_arc166_c [ARC166C] LU / RD Marking - 洛谷

考虑每个正方形格子的左上和右下是没有影响的，所以可以从对角线切开，发现对于同一斜线上的三角形，他们的方案数是斐波那契数列，预处理出来，并且统计一下中间整块的贡献就做完了。

下午和同学 VP 了一场 CCPC？感觉 J 题还不错。

The Hanged Man - Problem - QOJ.ac

发现找到一个偶数度数的点，我们认为他是天赋异禀的，然后从他开始进行配对即可。

另外有一个性质，发现只会被分割成若干长度为 $2$ 和 $3$ 的链，且只有一条长度为 $3$ 的，可以考虑枚举这条链。

11.6 模拟赛

进场看题之后感觉 T1 应该不难，但是 T2 应该需要组合数推式子，感觉 T3 是个简单题 \lh，T4 应该不好做。

看到 T1 之后想了几个贪心发现都不对，尝试刻画限制条件，发现限制条件的顺序没有确定好，没有想到正解的维护方法，去看了看 T2，发现这个东西可以根号分治，但死活想不出来 $k \le \sqrt n$ 怎么做，于是看了 T3。

最开始想了一个显然不对的做法，只使用前缀和后缀的点的 Floyd，但是其实可能会从左边走到右边再回去。

又想到了分治 Floyd，其实是正解，但是场上不知为何写挂了，耽误了很多时间，又去想了前两个题无果。

以后在做出前两题之前尽量不花很多时间开 T3，注意策略。

T1

Problems

首先一个比较显然的性质是 $\max(\sum a,\sum b) \le ans$，考虑 $ans$ 还有什么限制，发现如果一个人的助攻和进球都特别多，就可能不合法，于是发现 $a_i + b_i \le ans$，很好理解，其他人最少进它助攻数量个球，他进了进球数，所以是 $a_i + b_i$。

考虑这东西并不好对每个位置都维护，所以还需要发掘性质。发现一个 $id$ 能产生这种贡献的条件，一定是 $b_i > \sum a - a_i$，$a$ 同理，于是我们只需要找出 $a,b$ 的区间最大值的位置，对这两个位置计算贡献即可。

T2

容易想到根号分治，难点在于 $k \le \sqrt n$ 的部分，这个需要大力组合数推式子并解方程，不擅长数学，不会。

T3

最短路径 - Problem - QOJ.ac

首先有一个 trick，缺一分治，也就是需要统计去掉一个东西的贡献，例如删掉一条边维护连通性，此时可以考虑线段树分治解决。

看到这个，询问删除一个点的最短路，复杂度可以允许 $n^3 \times \log n$，考虑线段树每个区间 $l,r$ 维护不走 $l,r$ 内的点的最短路，对每个线段树节点进行 Floyd，在叶子节点对询问统计答案即可，时间复杂度 $O(n^3 \times \log n + q)$。

11.7 限时训练

20251107限时训练 - Virtual Judge

T1

P3243 [HNOI2015] 菜肴制作 - 洛谷

容易发现这是一个拓扑排序，但我们发现正着做取字典序最小不一定是最优的，于是反过来找字典序最大的，发现这个之后就很好做了。

T3

D - AB

找规律大分讨题，考虑最开始的情况，然后分讨往后扩展即可。

T6

E - Directed Tree

考虑这题要求实际上就是 $a_i$ 不能是 $i$ 的祖先，对逆排列计数，二项式反演容斥即可。

11.8 ABC

Tasks - TOYOTA SYSTEMS Programming Contest 2025（AtCoder Beginner Contest 431)

比较简单的一场，E 把每个点拆成四个方向四个点，然后建边最短路即可。

F 考虑从小到大填数，已经填了前 $i - 1$ 个，当前填第 $i$ 个，考虑可以填的数，设 $cnt_i$ 表示对于 $i$ 合法的 $i - 1$ 数量，那么对于 $i$ 的贡献就是 $cnt_i - i + 1$，最后去重一下，总方案数是 $\frac{\prod\limits_{i = 1}^{n} cnt_i - i + 1}{\prod\limits_x count_x}$，其中 $count_i$ 表示数字 $i$ 出现的次数。

11.9 模拟赛

进场先看了题，T4 直接处理 A 数组求最大子段和可以有 $25$，暴力分不少，T3 应该是困难题，部分分这么多，找一找好打的打一下，T1 看着像换根，T2 感觉像 trie 树，类似的题被创飞好几次了，再研究一下。

看了 T1，大约 40min 的时候想到可以换根，维护每个点子树内到它路径全为 $0$ 的数量，拆位换根就能知道每个点作为根的贡献，枚举统计贡献即可。

T2 想了很久，想到一个 $n^2$ 的做法，写出来发现假了，又想了想 $2^x$ 的东西，感觉实现太困难了没有写。

T3 写了一个比较好写的暴力，然后去看了 T4，写了 $25$ 的线段树维护最大子段和。

T1出现失误，实现的太拉导致自己最后剩下的时间很少，T2 没有想出来，最后没有专心开一个题，主要问题不少，但是今天场上用 NOILinux 虚拟机测了 CE RE 等问题，发现 freopen 是有返回值的 /lh，还以为是 CE 了。

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-16 22:41:19

11.10 ~ 11.17 集训记录

11.10 限时训练

T1

P10206 [JOI 2024 Final] 建设工程 2 / Construction Project 2 - 洛谷

考虑新的最短路一定是 $s -> u + d + v -> t$, 于是考虑正反两遍最短路，枚举每个点之后拼起来即可，要注意最开始就合法要单独计算。

T2

P11663 [JOI 2025 Final] 勇者比太郎 2 / Bitaro the Brave 2 - 洛谷

考虑实际上是对于一段 $b$ 的前缀和要 $\geq a_i$，于是线段树维护前缀和，每次变化后缀修改即可。

T3

P11727 [JOIG 2025] 神経衰弱 2 / Pair Matching 2 - 洛谷

发现对于配对的 $i,j$,他们之间最多拿上一张牌，否则 $i$ 就会被扔掉，因此设 $f_i$ 表示以 $i$ 结尾，强制 $i$ 配对的最大贡献，那么转移分为中间有没有牌，线段树维护一下即可。

实现上还有个小细节，对于区间取 $\max$，询问区间最大值，可以少维护一个 tag，递归修改为循环查询即可。

T4

P11726 [JOIG 2025] 最悪の記者 5 / Worst Reporter 5 - 洛谷

考虑倒着做，每次就是钦定两个位置相邻，直接维护 $id_i$ 表示 $i$ 位于时刻 $m$ 的哪个点的位置，每次交换并连边，如果出现点度数 $>2$ 即不合法，环也不合法，否则直接字典序最小输出链即可。

lca NOIP

T1

CF1844C Particles - 洛谷

考虑可以删掉一段长度为奇数的区间，于是分奇数偶数分别维护最优决策即可。

T2

P7967 [COCI 2021/2022 #2] Magneti - 洛谷

连续段 dp 好题，首先发现最后中间是一段区间，然后把空白位置插进去即可，于是考虑对长度为 $k$ 的方案计数，如何做呢？

从小到大插入，设 $f_{i,j,k}$ 表示插入了 $i$ 个，分成 $j$ 段，花费了 $k$ 的空间，共有三种转移：

• 新开一段 $f_{i,j,k} = f_{i - 1,j - 1,k - 1}$
• 合并两段 $f_{i,j,k} = f_{i - 1,j + 1,k - 2 \times a_i + 1} \times C_{j + 1} ^ 2$
• 接在一段后 $f_{i,j,k} = f_{i - 1,j,k - a_i} \times j \times 2$

最终答案就是 $\sum\limits_{i = 1}^n {l - i + n \choose n} \times f_{n,1,i}$。

T3

比较简单，难点在于复杂度分析，树形 dp 维护子树内同色节点数量，注意树形 dp 转移上下界优化到平方即可。

11.11 模拟赛

T1

最开始以为是 ABC 的 F 题，容易想到一个贪心，维护一个 set，每次找到最大合法的删掉，但是会发现大样例 #1 就寄了，问题在于可能会取到一些过大的值，这些值可以作为后续新的段的起点。

如何解决呢？我们考虑二分答案，接下来问题在于如何 check，我们考虑先把每一组第 $i$ 个元素全部填完，再填第 $i + 1$ 个元素，这样类似一行一行填，当一个数在当前不能被匹配，则在所有当前可以接上的位置都无法匹配，由于我们是顺着填下来的，所以其他位置一定 $<$ 当前位置，于是排完序直接枚举 $1\sim n$，不合法直接扔掉就行了，时间复杂度 $O(n\log n)$。

T2

考虑到了前面很多的性质，唯独没有发现最后的性质，考虑每次操作相当于向右压缩整个连续段，但是最终无法删掉连续段，最短也会留下 $1$ 的长度，而我们可以在左边任意添加新的元素，因此只要对于任意位置均满足 X 的后缀连续段数量 $\le$ Y 的后缀连续段数量即可，使用线段树维护，每次只会修改 $O(1)$ 个位置。

维护最小的差值，可以转化为一个加一个减，维护区间最小值。

T3

考虑最优策略一定是打 $\lceil \frac{suma}{x} \rceil$ 轮，最后会额外有一些，贪心的按照 $b_i - a_i$ 从大到小依次填进去即可。

考虑如果 $x$ 很大，我们可以不枚举 $x$，观察这个式子是类似整除分块的形式，我们可以按照整除分块，对每个块内同一计算答案，具体的维护出每个块合法 $x$ 区间 $[l,r]$，找到和区间有交的 $pre$ 统计答案即可。

T4

考虑图实际上是一个竞赛图，有一个比较好的性质是，从一个点出发能到达的所有点，均可以在同一条链上，于是问题转化为了从三元组 $0$ 出发能到达的三元组数量，考虑 BFS 如何更新。

发现条件看似是一个三维偏序，实际上只需要满足其中两维，我们考虑分讨三种合法情况，以 $A,B,C$ 为下标，另一个为值建立线段树，每次暴力找合法的点即可，每个点只会被删除 $O(1)$ 次，因此总时间复杂度 $O(n \log n)$。

11.12 限时训练

P11453 [USACO24DEC] Deforestation S - 洛谷

考虑贪心如何做？按右端点排序，每次尽量在最右边种树，这样可以对后面区间贡献尽可能大，现在问题变成了维护区间内已经覆盖的点的数量，以及找到范围内最右端的点，分别使用树状数组和 set 维护，由于每棵树只会被种 $O(1)$ 次，总复杂度 $O(n \log n)$，记得离散化一下，处理一下细节。

P10193 [USACO24FEB] Bessla Motors G - 洛谷

考虑从哪个 $c$ 过来其实不重要，对于每个点我们只关心 $k$ 个有用的点，因此可以直接在状态多加一维表示从哪个 $c$ 转移过来，如果一个点已经被转移了 $k$ 次那么这个点就没有用了，因为走前 $k$ 个一定更优，用 map 维护即可。

P10282 [USACO24OPEN] Smaller Averages G - 洛谷

考虑 dp，$O(n^4)$ 是好想的，方程如下 $$f_{i,j} = \sum\limits_{k = 1}^{i - 1} \sum\limits_{l=1}^{j-1} f_{k,l} \times [\frac{pre_i - pre_k}{i-k} \le \frac{pre_j-pre_l}{j-l}]$$

考虑如何优化，发现限制条件其实是 $i,k$ 对和 $j,l$ 对的限制，考虑枚举 $i,l$，另外两维可以双指针维护。

P10138 [USACO24JAN] Cowmpetency G - 洛谷

对每个位置维护状态 $1,-1,0$ 表示是否可以作为前缀严格最大值，考虑一个限制 $a,b$ 实际上是 $[a + 1,b - 1]$ 这段区间一定不能作为前缀最大值，$b$ 一定是前缀最大值。

然后设计 dp，设 $f_{i,j}$ 表示前 $i$ 个位置，前缀 $\max$ 为 $j$，转移分 $1,-1,0$ 分别转移，可以用前缀和优化。

发现一个连续段内是互相不影响的，于是考虑对每个连续段去做，于是就变成了 $O(QC \log C)$，其中 $\log$ 是快速幂，具体 dp 方程比较好推，是在推不出来可以看题解，式子很详细。

P12029 [USACO25OPEN] Election Queries G - 洛谷

首先考虑 $x,y$ 作为两个合法首领的充要条件是 $c_x + c_y \geq mx$，其中 $c_i$ 表示选 $i$ 的人数，$mx$ 表示 $\max c_i$，要不然肯定要选 $mx$ 这个。

于是可以想到对每种 $x$ 去双指针找到 $y$，用 set 维护 $c_i = k$ 的所有编号，取最大最小即可。

想一下，发现 $c$ 最多只会有 $\sqrt n$ 种，想要卡满就是每个人分别有 $1,2,3,\dots$ 票，其实就是等差数列求和，所以是 $\sqrt n$ 的，于是我们维护一下序列里当前有哪些 $c_i$，直接按上面的做，总时间复杂度 $O(n\sqrt n)$，可能要带个 set 的 $\log$ ？应该不需要。

11.13 模拟赛

T1

Problems

首先考虑无解的情况，由于每种颜色刷子只有一个，因此考虑对于一种颜色，设他最前面出现的位置为 $st_{c_i}$，则若出现 $st_{c_j} < st_{}c_i < j < i$，则无解，也就是两个区间交但不包含，剩下的则直接维护出每种颜色区间 $[l,r]$,直接从前往后染色即可。

T2

Problems

P4785 [BalticOI 2016] 交换 (Day2) - 洛谷

考虑设每次取出的三个位置为 $A,B,C$，考虑每次操作，一定让最小值放到 $A$ 上，于是如果 $\min = A$，则不变，若 $\min = B$ 则交换前两个，否则我们发现 $A,B$ 我们不能确定如何分配，此时我们记忆化搜索下去，由于交换形成了类似完全二叉树的结构，因此复杂度有保证。

T3

Problems

考虑当确定 $a,b$，$c$ 和 $s$ 之间是成二次函数关系的，因此最优一定取到 $\max$ 或 $\min$，枚举 $b$，可以得出 $c$，随后找到最优符合条件的 a 即可。

T4

Problems

P8996 [CEOI 2022] Abracadabra - 洛谷

考虑每次归并，实际上是形成了若干个有序连续段，这里有序指的是最开始的一个元素有序，连续段则为，从最开始的数，以它作为开头且最大值的极长区间，随后每次操作变成了拆开一个区间，由于最多 $O(n)$ 个区间，每个区间只会被拆一次，因此可以直接维护，使用权值线段树维护每个段的长度，查询时线段树二分即可。

11.14 限时训练

T1

P9186 [USACO23OPEN] Milk Sum S - 洛谷

比较简单的一道题，首先考虑无修改，贪心去做肯定让效率高的多产几天，于是我们排序，每次修改找到原来的位置和新的位置，计算一下增量即可。

T2

P9527 [JOIST 2022] 洒水器 / Sprinkler - 洛谷

给定一棵树，对树上不超过 $d$ 的点 $\times k$，单点询问。

首先考虑一个比较暴力的，每次跳父亲，对其子树能覆盖的范围区间乘，但是发现会重复，观察重复部分，发现每个父亲会覆盖向下 $d$ 和 $d-1$ 两层，每次跳父亲时 $d$ 都要 $-1$，于是可以直接维护 $tag$，每次询问暴力跳父亲即可。

T3

P9981 [USACO23DEC] Minimum Longest Trip G - 洛谷

第一问拓扑是好做的，考虑第二问，实际上我们可以考虑整个过程，在每一步转移都是取字典序最小转移，因此我们每次只考虑 $f_u = k$ 和 $f_v = k - 1$ 的这些点即可，每次处理出排名，按照先边权，后排名的顺序取即可。

T4

P9525 [JOIST 2022] 团队竞技 / Team Contest - 洛谷

之前题单里的一道题，考虑从大到小取，如果一个人同时作为多个集合的最大值，则只能把他删掉，要不然不合法，贪心用堆维护即可。

P14507 缺零分治 mexdnc - 洛谷

Luogu NOIP 模拟 T1，起来比较晚，发现其实合法的一定是在最大能凑出来之内，首先特判掉一些边界情况，剩下的肯定贪心从大到小取比较优，这里还需要注意到 $a_i$ 是假的，最多只有 $n$ 的级别，然后二分答案就做完了。

【MX-S11】梦熊 NOIP 2025 模拟赛 3 & WAOI R7 & FeOI R6.5（同步赛） - 洛谷 | 计算机科学教育新生态

P14520 【MX-S11-T1】战争游戏 - 洛谷

性质题，首先如果最开始 $suml > sumr$ 直接搞到最左边然后一直向右平推即可，否则看看能不能吃掉右边第一个，如果此时右边能吃回来则 $l$ 必败，否则则是要比较两边的和，注意到只会攻占一个位置就做完了，前缀和维护一下。

P14521 【MX-S11-T2】加减乘除 - 洛谷

比较简单的题，看到性质 $C$，考虑实际上每个点的区间，维护一下从根到这个点的前缀和，对路径上限制取更紧的，然后就可以求出每个点合法限制区间，相当于是给定若干个区间，每次询问这个点在多少个区间内，差分一下就行，这里还写了树状数组的差分。

P14522 【MX-S11-T3】空之碎物 - 洛谷

哇，非常难的一道题！

其实是性质题，考虑当区间出现了超过 $27$ 个数字，则一定可以取到 $\max$，于是先计算这些区间，具体的使用一个单调栈，然后考虑小区间如何计算，发现式子可以拆成 $x \ominus (y \ominus (\dots))$，此时只有 $x$ 某一位只有一个 $1$ 才能产生贡献，我们直接枚举区间一维，枚举 $x,y$，然后计算贡献即可。

具体计算，我们需要满足 $x$ 和 $y$ 按位与的结果这些位置是不合法的，同时对于区间内不存在的这些位置，只保留这些位置，然后计算贡献即可。

要注意当我们需要使用单调栈统计每个数作为最大值的区间，统计贡献时，需要注意钦定相等的贡献算在左边或右边，否则会算多或算少，这里可以在从前往后单调栈时使用 $>$，从后往前使用 $\geq$ 即可。

11.15 ABC

掉大分了，E 是一个比较简单的线段树，考虑算一下贡献就做完了，G 貌似是多项式科技，据说要用 NTT，不会。

F 写了一个 IDA*，最后 TLE 了没卡过去，D 题怎么还是大模拟，这场输麻了。