由于学校的一些神秘原因，wyoj 服务器从国庆开始断电并搬运了位置，在 ryp 大哥的神级操作下，wyoj 顺利搬迁完成并成功恢复使用！
wyoj 蒸蒸日上！ryp nb！
xuyunao 的博客
博客
热烈祝贺 WyOJ 成立一周年！
为庆祝 WyOJ 成立一周年，现在推出特别活动，仅需在本贴下评论 WyOJ 蒸蒸日上 即可获得精美奖品（包括但不限于体验 重生之 WyOJ 皇帝和我生存在同一个星球）。
感谢 WyOJ 皇帝（ryp）的杰出贡献，我们一起来膜拜他。
算了
xya 与 OI 的故事
前言
感觉自从 NOIP 打完之后整个人都很摆，不知道自己在干什么，很多时候想写题但是找不到思考的感觉了，也没有做到适合的题，慢慢的整个人就变成：听别人讲思路看题解，写代码甚至可以说是默写代码，调不出来了，对着题解查错，最后写完一个题。整个过程，甚至都没有办法称得上是代码复制机器。其实个人感觉，或许真的需要好好休息一下，但是离寒假还很远，而且寒假也未必会好好休息，所以，可能我自己也不知道该怎么样去调整。
写这个类似回忆录的东西，才发现好像这一年对我而言并记不住任何值得回忆的事情，而只有每天都在重复的日常，日复一日，好像并没有任何偶然事件，也没有任何能够令人印象深刻的事情。
感觉写的很乱啊，写的也一点也不好看，后面的发生的事情更像是说给自己听的一些东西，不管了。
回到正题
这篇文章究竟要写什么呢？感觉或许记录一下这一年里的种种琐事，记录一下自己学 OI 这一年半的时间里所经历的事情，也记录下自己的心得吧。
哎，怎么已经，两年了，哎，我服了，好区啊，甚至于不会做，2100 的 dp，真是拿你没办法。
比较重要的同学 / 朋友
这一点多里，固然交到了很多的朋友，认识很多新的同学，在这里面自然有形形色色的不同的人，而每个人也会带给我们不同的感受。
炜哥应该可以排的到前面，学 OI 的这些时间里，不管是学习方法上的、心态上的甚至于是写专栏等种种习惯，很大部分都是深受炜哥影响的。一方面来说，我个人认为我们两个的经历是很相似的，这让我们之间有非常多共同话题，也容易引起共鸣。可是也许我没有炜哥勤奋、没有炜哥有毅力，亦或者说就是命中注定，总而言之，炜哥可以真正称得上是一个榜样，或者更确切来讲，应该是一个引路人。
炜哥很扎实，这是大家公认的，这可能也是他能很好的在 sale 上发挥出来，而我最终没有调出来的原因之一，但是人与人之间总是有很多不同的。可能在同一个时间，面对的是不同的处境，心态也不尽相同，但归根到底，炜哥带来的影响是巨大的，虽然或许我们相处的时间并不是最长的，希望炜哥能顺利进队吧。
upd on 2026.7.12：
马上就要 NOI 了，gwf 今天生病回家了，感觉最近好摆，唉不知道该咋讲。
他确实顺利进队了，哎确实很强，虽然这几个月可能大部分时间他都在骂我和骂我的路上，但是怎么说，可能我比较唐。总而言之，gwf 对我的影响还是比较大的，学到很多东西，而且大家经常一起聊天，也在心态上教了我很多东西。
感觉，马上就要分开了，其实是非常不舍得的，而且好像，有一种怅然若失的感觉，发现自己马上也要变成高二的人了，发现好像大家以后很难再有这样长的时间呆在一起了，还是挺伤心的。
怎么说，祝好吧。
唉，gwf NOI 打爆了，遗憾 Cu 了，不知道该作何感想啊，可能 OI 就是这样吧，就是，发挥稍微不好，就没有 Ag 了，总之就是，希望他在接下来 whk 顺利吧。
杰哥和炜哥很相似，在他们的身上都有踏实、质朴、善良所在的，但是和杰哥熟悉或许比炜哥更晚，细说起来大概是从初三暑假开始的。和炜哥比起来，杰哥应该更安静、更平淡、更细腻。杰哥非常好相处，爱听音乐喜欢各种游戏还是动漫人物的图片，这也算是他的一种精神寄托。杰哥教会了我很多，更多的是操作系统以及一些小技巧方面的东西，也带来了很多乐趣。
希望杰哥炜哥都能顺利进队吧。
除此之外还有很多学长，比如 zhu_wen，chb，ryp，cybrex，zibenlun 等等很多人，这里没有一一列举，但是他们之间的情谊，远比 OI 本身更加珍贵。
upd on 2026.7.12：
可惜杰哥没进队，但是心态还是很不错，大家经常在食堂见到，哎，还是挺开心的。而且杰哥虽然退役了还是经常中午做 oi 题，不得不说过了这么久杰哥实力依旧远高于我，只能说我太菜了。
说完几个学长，再来说几个同级同学吧。
Dtw_，我心中的 rk1。如何讲起呢，可能我们之间回忆中并没有多少起伏，没有多少被铭刻的瞬间，而绝大部分都是 OI 生活的点滴小事。他应该是除了 zhu_wen 以外我最先认识的人。和 Dtw 相处的时间应该占了我目前为止 OI 生活的大多数，以至于不知道从何讲起。
比起和炜哥之间的经历相似，和 Dtw 之间更多的是一个不断磨合的过程，每天从早读、上课到下午训练、晚上晚自习的全部时间都在一起，慢慢的我们都习惯了彼此，性格也慢慢变得相似。在国庆之前，我一直都把 Dtw 视作我努力的对象，在我看来，如果有人能够达到 Dtw 的水平，那么就可以称得上是了解 OI 的程度了，感觉这个表述并不恰当，总之，我认为 Dtw 可以看作是不冲省选选手的极高水平了。
在整个 OI 的过程中他教给我了很多东西，除去简单知识层面的影响，他对待生活、对待学习、对待放假休息的种种态度与看法，也或许让我真的触摸到了真正的生活应该具有的层面。我一直都认为他将会是陪我走过 OI 生涯最久的一个人，这种令人沉浸的幻想一直持续到国庆，他选择省一回归 whk，而我选择了继续打 OI，这些选择并不能说清楚为什么，而是漫长岁月中积累出的结果。在 wfbczx 的两个月，我们彼此之间更加了解，也更加珍惜难得的相处时间，珍惜在一起玩、讨论的时间。
希望 Dtw 明年能取得自己想要的成绩，在 whk 学习也能蒸蒸日上啊！
对于 hdz，我可以给他以下几个标签：智多星，"运气"也是实力的一部分。为什么这样说呢？hdz 对于数学和 OI 问题的理解能力，以及思考能力是很牛的，虽然平时总给人一种划水的感觉，但到了关键时候总是能打出不错的成绩，可能我们会说这里面确实有运气成分在，但不可否认，hdz 在认真学习的过程效率是极高的，以至于总是给人一种不切实际的感觉。
和 hdz 相处更多是生活、娱乐的一些方面，打球是我们几个之间的主旋律，娱乐之余也有不少相互之间的陪伴，不管是 mxbj 还是在学校的很多时候，hdz 都给我带来了很多启发与影响。
syc，数竞老哥
这是为数不多我非常熟悉的除了信竞以外其它的同学，最开始认识 syc 是初三每天体育课打球认识的，慢慢的就熟了。可能每天在一起的时间总是被不同科目给分割的刚刚好，我们之间的关系非常融洽，在一块干的事情也很纯粹，就只有打球和聊各自竞赛的一些事情。
现在是九勾爷了，磕了。非常可爱的小宝宝，很强，非常认真专注（不像我一直在摆），但是比较爱睡觉。可能是现在还和 Pigsyy 在一块，对他还暂时没有什么回忆的感觉，或许需要之后再来补上。
确实是，lsxh，yyds，强完了，人很好，比较随和，和他熟悉的时间主要还是从 lca 开始的，想到马上也要分别了，心里不知道什么感觉。
之前说的希望他们都能进省队，现在也要祝 KSCD_，lsxhyyds 在 NOI 中取得满意成绩，以及，祝 Iceturky 等回归 whk 的同学一切顺利。
以及一系列同学，由于下午讲题突然没那么无聊，没那么消沉了，所以就不继续写下去了。
upd on 2026.7.12：
唉，当时为啥说马上就要分别了，可能是，觉得自己进不了队就要滚蛋了，但是其实还是一直在混日子。可能这几个月在一起呆了这么久，感情变得更深了。
怎么说，小寒人其实非常好的，只是可能不太爱说话，外人看上去比较冷淡。虽然满打满算可能我们也只认识了不到一年，但是心里确实，也很不舒服。
这几个月小寒还是经常教我一些东西的，而且确实一起在学校也很开心（虽然小寒打球经常演），马上 NOI 了，真心祝愿小寒能顺利进集训队（虽然感觉他最近状态不佳）。
以及，可能我认识的很多人也都是从小寒这里认识的吧，如果没有他可能我也不会有任何的社交，所以其实小寒带给我的影响是非常大的。
祝他进集！
哎，小寒，也比较可惜吧，被神秘布丁创了，Day 2 虽然已经翻回来很多了但是怎么说，无力回天了吗，哎，感觉真的很可惜。
感觉小寒真的挺强的，但是平时都不怎么给我们讲题hhh，哎，太可惜了，感觉其实是蛮有信心的，总之，祝他好运。
后面都是省选之后认识的，所以 upd 了一下。
以及在这里提一下 ET，最开始是寒假在 ht 省选集训认识的，说实话当时他可能都不认识我，后来大家一起去了二轮省集，好像就只见过了那一次面，但是加上一起玩游戏，大家慢慢就熟起来了。
祝他也能顺利进入集训队。
ET 大哥，Day 1 也爆了，哎但是，ET 大哥在我心里是比较牛的存在，属于是比较敬佩吧，总之祝他在接下来的 whk 生活顺利。
她好强。
哎，其实第一次听说她，或者记住她是当时 NOIP 打完例行开合的时候，后来好像在 lca 还是啥时候又开合，发现她老家和我是一个地方。
后来去 ht 省选见到了本人，但是我比较区，没有任何与别人社交的能力，于是自始至终没有和她说话 \lengh。
沙东省选刚好和 pyyz 住在同一个地方，然后忘记具体咋样了，反正好像是非常尴尬的搭上话了就，然后，其实我是早就认识她的，反正就是莫名其妙遇到好几次，然后就认识了。
后来好像是因为她水到我专栏了？反正就认识了。总之，她好强，哎，不像我比较区，可能她也算为数不多愿意主动和我说话的人？反正就是，人很好，也很强，不像我很区。
然后祝她在 NOI 取得好成绩。
额，为什么，前面的人都爆了啊，哎好像大家都被神秘原因创了，看来 NOI 可能确实，怎么说，就是会因为各种各样的事情爆掉吧，感觉都，挺可惜的。
hya。
由于这位同学貌似非常喜欢隐藏自己的洛谷账号，所以我们不贴她的帐号了。
其实也是因为 chb 认识的，哎，她也好强，感觉也算为数不多有时候愿意和我讲话的人，怎么说，人很好，而且是忠实号家军（我没去过 hb 那咋办）。
祝愿她在 NOI 取得自己想要的成绩，祝愿上面所有人 NOI 不要倒闭。
哎，恭喜她在 NOI 获得了高一 Ag 的好成绩，预祝她在接下来的生活里面天天开心。
发生的一些事情？
说完了同学，说说这一年多里发生的很多事情。要说很多事情，实际上我认为的 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 打的并不好，但是总归，其实也还不错。
不久就 NOIP 了，也慢慢意识到好像很快就要和身边朋友说再见了。当时前一晚并没睡很好，但是并无所谓，毕竟人体的调节能力是非常强的，进场之后很快切了 T1，本身目标是奔着三倍队线去的，场上预计的三倍（也就是去年 $272$）大概是 $248$，因为 T3 $8pts$，T4 $40pts$ 都是很快就已经写完了，T1 是个签，T2 当时场上很快就推出正解来了，但是没有想到 T2 这么难调，当时场上留了 3.5h 来写 T2，放在一般题很快就想出思路了，3.5h 是完全够了的，但是场上调出几处错误之后大样例始终大 $1$，不知道该怎么办了。看着时间一点一点过去，很无奈但是也没有办法，在半个月之后再看才发现是自己没有处理好相等的情况，可能场上加上一句 if(a[i] != a[j]) 就能进两倍了呢？但是所有的东西都回不去，也没有后悔的余地。
NOIP 之后整个人好像都变了，看不到未来，看不到翻盘的希望，每次都在思考当时 T2 为什么没有处理好，其实细想想这一年多并没有好好休息一下，自从中考过后好像也没有放过 $2$ 天的假期了。整个人其实是非常希望能有一个长假来调整一下的，但是过年还有很久，年后也没有很多时间了，每天都在模拟赛浑浑噩噩并不能有什么改善，每天的状态就像刚开头写的一样，很疲惫，很摆，好像每天干了很多事情，但是又没干什么事情，只是一个代码搬运机器。
可能休息，更多的是需要放下手头的事情，放下心中的执念，去到一个新的地方，去做一些随心所欲地事情，不受限制的到处乱转，亦或者是在家玩上几天，总之，或许我们需要的休息并不是睡多久的觉，而是真正能不被约束、放下手头要做的事情、暂时的放下那些所谓的目标和理想，放空心灵、随心所欲而不需要考虑任何的目的，可这却也是最珍贵的、最难以得到的境遇。
总而言之，对待生活、对待学业，我们唯一能做的，就是在迷茫、朦胧中，去记录、去做这些有用所谓意义的事情，去试图找到调整的方法，去感受这过程中好的、坏的、种种一切。
写一篇这样流水账，记录一些有趣的算法，不去在意那些成绩与评议，只是在平淡的生活里去追求有意义的事情，或许我们才能够感受一切的意义。
星图铺就的，未必是归途。
但有人循着它，便不算迷路。
upd on 2026.3.23:
感觉可以更新一下了，省选之后总算是，放松了，虽然是很 fail 的放松了，但是总归是有了一段时间调整。感觉这一年的比赛，不好说什么，就是太菜了吧。
至于心态上的变化，可能去 省选游记 看会更好。
过去已经凝固，我带着回忆向前
只是时常疏于保管，回忆也在改变着各自的形态。
这给我的追忆旅程带来些许挑战。
我该在哪里停留？我问我自己。
upd on 2026.7.9
linux 字体咋这么大。
怎么说，这一年，认识了很多新的人，可能实力没怎么变化，该区还是很区，但是可能大家没有嫌我菜，还是有一些人喜欢和我聊天，感觉还不错。
到 noi 之前了可能不管自己能不能去，都总会有一些想法，一些不太平静的东西，可能一方面非常希望大家都能取得好成绩，另一方面可能，人与人总归是要分别的，或许我们也不清楚最终到底哪些人会依旧把彼此记在心上，又有哪些人会慢慢淡出视线，但是或许相遇了、经历了就已经是最好的缘分吧。
预祝大家 noi 取得理想的成绩，以及可能，我还是很菜，可能越来越感受到 oi 开始限制我的时间和为数不多改变的机会，但是总归是已经走到现在了，可能非常普通的退役，然后混完高中，也是很正常的选择。
感觉好久以来一直状态不佳，也有可能其实就是，一直都比较菜导致的，总之得过且过，每一天过完了也就不想那么多了，感觉也很幸运遇到了一些比较好的朋友，可能要问为啥这么菜，第一位的是太摆了，摆的太多了，以及可能心态比较影响做题的效率和进程；再往后可能是学习的时间比较短？但是其实好像也已经两年过去了；最后可能才是天赋太平庸了太区了，以及可能身边的人都不太了解我吧。
总而言之，天天开心。
upd on 2026.7.12：
原来这部分是要说一些事情，那就说说省选以来的事情吧。
说是要等生物的同学一起补课，所以我们获得了在机房先自己补课的权力。当然这段时间可能心态上的原因，其实我最开始并没有好好在学习，整天在摆，做的题基本上也是比较板的简单题，而且有一些题也不是自己想的。
后来二轮省集之后，确实不想摆了，开始学习了，但是告诉我们要和生物的同学一起补课，说实话我觉得既然都学 OI 了，而且可能就行 hya 同学说的，OI 对我来说可能就是，和我的情绪是完全绑定的，OI 训的好就会很开心，不然就会一坨，
所以我觉得其实我本人是不太想回去学 whk 的，而且其实刚找到的状态，但是没办法可能，家长也有他们的考虑，而且可能大家也很难做到一致。所以最后到最近其实才开始重新停下来学 OI，虽然感觉自己早就区完了，哎但是怎么说，可能对我来说已经扔不掉了。
哎其实这期间还发生了非常多的事情，这些事情可能或多或少都对我的心情产生了很多影响吧，总之就是，过去的事情也不想再说啥。
怎么描述我现在的状态，可能我一直没有找到一个能让自己休息的方式，也或许只是我没有足够的条件能休息吧，反正我感觉其实现在这样，躺着什么也不需要做，听听歌，能找到个人说说话，就是非常舒服的。
但是可能，我既不会能够找到这样的时间，能让自己完全休息下来随心所欲，更找不到一个人能说说话，也不可能停下来不去在乎 OI 或者任何其它的事情，总之可能就是，很累，然后也，没有办法。
天天开心。
NOIP 2025 游记
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-29 21:44:06
省流
输麻了被 T2 创飞了，打的不好，可能会继续冲。
某一天，我不再把离开当作失去。
Day.-4 （11.24）
考前一周模拟赛每天只有 $100$ 出头，mx 模拟赛太难了，回去 wfyz 了，感觉开摆了。
其实没有想到 NOIP 会这么难，但这些都是后话了。
夕阳无限好，只是近黄昏。
Day.-2 （11.26）
晚上依旧举办了神秘仪式，这一次隆重了很多啊，还上去唱了歌，感觉很好玩，机房老资历全都回来了，玩的很开心，不知不觉已经开摆两天了。
听了 KSCD_ Iceturky Pigsyy 和 lzx 合唱的 蜂鸟，超级好听，发现宝藏歌曲，KSCD_ 延迟有点难崩。
人生天地间，忽如远行客。
Day.0 （11.28）
早上没睡太晚，吃了个饭就去学校了，去找了 typ 玩，然后就在机房玩了一会 2k，中午吃饭记错时间了，急急忙忙吃完了，有点难崩。
下午坐车去酒店，发现酒店居然给我们开成了家庭房，后面才告诉我们原来是开错了。拍完合照就去吃饭了，吃了必胜客不是说吃完必胜客就必胜吗，呆了一会就去试机了。
进考场发现考场好大啊，面基了 xz，居然还有一套模拟赛，场上的 NOI Linux 这么丝滑，后悔没有多玩一会。出考场看到了 qqqaaazzz，在大门口合照，喊出了我们的口号：编程不复杂，难题找阿史。
收到了来自各个地方的祝福。
晚上回去十点就睡了，悲剧就此发生——
何处合成愁？离人心上秋。
半夜很久都没睡着，可能也是想了很多事情，也想起了很多以前的东西， 总而言之，心里有很多事情，而且感觉试机看到题没有任何感觉，可能内心很慌。
半夜 $1:19$ 醒了一次，感觉有点冷，心里想了很多东西，感觉睡不大着。
月落乌啼霜满天，江枫渔火对愁眠。
半夜 $3:29$ 又醒了，尝试重新睡觉无果，起来走了走，实在感觉睡不着了，可能是感受到了发自内心的某种感觉，又过了很久，一会冷一会热，就是睡不着。
终于在 $4:16$ 左右突然发现脑子里想的东西不那么多了，然后开始睡觉，一直睡到起床。
Day.1 （11.29）
“蜂鸟是唯一能向后飞的鸟”
早上起来状态还不错，给自己打气，早餐没吃太多，然后就去考场了。
进场很顺利，只是最开始怎么还不让上厕所，xz 说我已经高一了，让我加油打！
进场开题，先看了看 T1，很快发现只会选一个取多块糖果，于是很快做完了，但是明显能感觉到自己做题做的很急，非常害怕后面没时间，好在是几乎没调试就过了大样例，此时 $8:50$，以为这把要赢麻了。
然后看了 T2，这题怎么这么难，T3 一看也是困难题，而且感觉最近 T3 都是难于 T4 的，看了看 T4，觉得有很多可写的暴力，于是决定先想 T4 暴力。
很快想到了对于 $len$ 分类维护，但是最开始只想到了用 ST 表，发现貌似过不去，不知道该咋搞。
想到了单调栈，很快想到了单调队列，然后就会了一个复杂度 $O(n \times len + nq\times len)$ 的做法，发现可以有 $40$ 决定开写，此时大约 $9:15$。
发现直接写会爆空间，精心计算分讨了一下，最终把空间压到了 $470M$，终于能过了，于是开始写，写完输出调试了一会，改了几个错误，很快调出来了，然后大约已经 $10:00$ 了。
Day.1.3 （11.29）
心里太多事我不会表达，但我把错归结于自己，我怪不了任何人。
然后开始开 T2，很快发现可以对于 $x,y,z$ 计数，这里表示最后选的 $1$ 和最前面不选的 $0$，然后推了推复杂的式子，写了 $3$ 张草稿纸，决定开写，初步给自己定的时间是到 $11:35$ 就去打暴力。
时间到了，但是还是没调出来，此时觉得想到队线必须要切 T2，实在是有些急了，心里不知道该怎么办，思索片刻决定继续冲正解，毕竟本身感觉不能到队线，省一没啥用。
最后写了 T3 $8pts$ 暴力，然后 T2 没调出来遗憾离场。结束之前都觉得自己要完蛋了，直到结束那一刻 xz 告诉我他 T2 也没调出来，并且和我大样例输出一样，终于感觉可能这题确实很难调。
总而言之，这一次又炸了，不知道该咋办，出门很难过，也很不知所措，不知道将来到达应该如何是好，内心充斥了空虚和犹豫。
上车一问，莫非我的 T1 也假了，这下彻底玩完了，预估分数 $[0,100] + 20 + 8 + [0,40]$，总共 $[28,168]$，看了看云斗榜单在 FJ 能排 60 左右，在 SD 感觉可能和 S 差不多，在 90 上下吧。
如果向花礼拜，能和你在春天相遇吗？
中午出去吃了烧烤，很好吃，但是没太有心情吃，感觉很无奈啊，不知道该说什么。
回家立刻就开始研究 T1，从脑子里写下自己代码，交上去一看怎么真 WA 了一个点，仔细研究发现自己忘记判断 $pre > m$ 了，好在是场上写了，拍了 $13010$ 组没挂，于是把拍子关了。
晚上 ABC 娱乐打法，写了 $5$ 个就跑路了，想不到今晚 FG 都这么难，居然排到了 rk300，也算是有点安慰，看云斗还没出 SD 榜，希望明天起床能看到吧。
结束了吗？
此情可待成追忆，只是当时已惘然。
或许比起沉浸在过去，我们更应该着眼未来，过去固然值得留恋，可时间的齿轮不会停止转动。NOIP 打输了，希望省选能翻盘吗，亦或者，等待明年再次相遇。
后记
只恐双溪舴艋舟，载不动许多愁。
未来就在眼前，过去已成历史，lcw 说过，打 OI 是长远的事情，或许当我们把目光放长远，就能看到不一样的世界。当然在最后的最后，还是要：
过去已经凝固
我带着回忆向前
只是时常疏于保管
回忆也在改变着各自的形态
这给我的追忆旅程带来些许挑战。
我该在哪里停留？
我问我自己。
希望能让我排名不要太靠后~
11.17~11.23
本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-11-22 22:12:34
11.17 ~ 11.23
11.17 限时训练
T1
P12016 [NOISG 2025 Finals] 震踏 - 洛谷
用到了曼哈顿距离和切比雪夫距离的转化，对于这种需要旋转坐标系的问题非常有帮助，然后就是发现相对位置是不变的，所以直接前缀加单点查，树状数组维护即可。
T2
P12194 [NOISG 2025 Prelim] Snacks - 洛谷
直接写了个大力线段树维护，每次操作区间赋值单点加，区间求和。
T3
P12017 [NOISG 2025 Finals] 可达性 - 洛谷
一个不错的树形 dp，考虑设 $f_{i,j}$ 表示 $i$ 子树内可达 $j$ 个点是否合法，转移根据 $l_u = l_v$ 分类讨论，然后按照每条边是否连通分类讨论即可。
T4
P12018 [NOISG 2025 Finals] 机器人 - 洛谷
发现对于最右边的每个点，能到达他的点是一段连续的区间，于是问题变成了给定 个区间 ， 次询问区间 ，询问覆盖区间 需要最少区间数量，可以直接倍增维护。具体的维护倍增从每个点出发，向后最远能到哪，然后跳倍增数组即可。
11.18 模拟赛
T1
发现一个性质是，最大值要么是 $0$，要么是 $1$，于是问题变成我们需要找到有多少个区间满足 $mex = len + 1$，也就是整个区间排序后是 $0,1,2,3,4,\dots,len - 1$。
发现必须经过 $0$，于是考虑按每个 $0$ 分段处理，由于知道了区间最大值就可以知道区间长度，因此我们亲定最大值位于左边，右边的情况我们反转序列再做一遍即可。
之后我们考虑枚举左端点的位置，维护前后缀 $\max$，这样我们可以求出区间长度，也就求出了右端点位置，然后判断右端点的最大值是否合法，这样我们就只需要知道，这段区间是不是数字各不相同即可。
如何维护这个东西呢？其实可以直接对每个位置 $i$ 维护 $i$ 向后最远到哪能满足这段区间内每个数只出现一次，然后就做完了。
T2
考虑把变化维护到折线上，每次分治暴力枚举区间，时间复杂度 $n \log n$，还需要主席树维护一下前后缀信息，具体的可以去看官解，感觉口胡太麻烦了。
T3
反射容斥，还不会 \kk ~~。
11.19 限时训练
T1
P9350 [JOI 2023 Final] 宣传 2 / Advertisement 2 - 洛谷
考虑贪心的从大到小做，然后变成了一个二维数点？实则发现合法转移式子两个是肯定同时满足的，于是维护两个值，一个排序，另一个维护单调栈即可。
T2
P14294 [JOI2024 预选赛 R2] 白色灯 2 / White Light 2 - 洛谷
很简单的一个 dp，考虑设 $f_{i,0/1/2}$ 表示前 $i$ 个灯合法，最后一个是 $0/1/2$ 颜色的最小花费，转移是好写的，注意把 $f_{i,2}$ 初始化成前缀全都熄灭的花费即可。
T3
P7405 [JOI 2021 Final] 雪球 / Snowball - 洛谷
很有难度的一个题。
首先你需要发现一个性质：每个雪球的贡献点是一段区间。
然后发现当两个雪球之间的区间端点确定了，就不会再变了，于是我们可以考虑暴力维护这个东西，复杂度 $O(nq)$。
考虑怎么优化呢？这一步非常困难，你发现这东西是具有可二分性的，二分最终确定端点的时间，就可以处理出每个端点，时间复杂度 $O(n \log q)$。
T4
P7804 [JOI Open 2021] 决算报告 / Financial Report - 洛谷
发现题目其实就是要让我们找一个上升子序列，我们发现对于 $i$ 能转移过来的 $j$ 是一段区间，我们可以用并查集维护这个东西，然后我们按照值从小到大去做，每次转移找到转移区间，线段树维护即可。
T5
P12196 [NOISG 2025 Prelim] Lasers 2 - 洛谷
哇好牛的一个题，考虑最大的这个块一定要被挡住，然后考虑 dp。
设 $f_{i,j,0/1}$ 表示前 $i$ 列，有 $j$ 个位置是能照到的，有没有出现 $mx$ 长度的照不到区间，不需要移动的贡献和最大值，发现转移实际上时对于右端点位于 $i$ 的区间，覆盖到的范围加上一个它的权值，于是线段树维护即可。
P12196 [NOISG 2025 Prelim] Lasers 2 题解 - 洛谷专栏
T6
哇这题太难了，我们发现当我们使用 $3$ 个数字一组，用 $4$ 组凑一个人，那么我们需要满足任意 $4$ 组组成的一个序列一定有一个人，否则我们可以先走这个东西，然后再走到某个位置，这样就确定不了一个必定赢的人了。
然后拿背包把这些合并起来即可，感觉代码太难写了，直接盒了。
11.20 模拟赛
T1
简单题，考虑排序后双指针指一下即可。
T2
发现排序后后面的是前面的倍数，类似一个进制形式的东西，同时发现这样的 $v$ 只会有 $\log$ 种，于是我们考虑对于 $v = a_i$ 如果他没被选中，可以把 $k$ 个合并成一个 $v = a_{i + 1}$ 的物品，同一类按照性价比选即可。
T3
不会啊，反射容斥（刚刚那个 T3 好像不是反射容斥）。
T4
发现这东西一定是从小到大推平，我们推出式子，发现从两边先搞一定是更优的，然后就是要维护前后缀最小值，区间修改，线段树维护即可。
11.21 限时训练
P14333 [JOI2021 预选赛 R2] 安全检查 / Safety Inspection - 洛谷
考虑这东西可以二分，然后 check 考虑从后往前做，这样走到后面的人过来就不需要花费路程，只需要花费工时。
P14331 [JOI2021 预选赛 R2] 煎饼 / Pancake - 洛谷
数据范围很小，状态数可以搞得下，直接搜索就行了。
一些杂题
简单题，发现答案是 $\max(x - y,z)$，这里 $x = \max(a_i),y = \min(a_i)$，$z$ 为严格次小。
P13520 [KOI 2025 #2] 存放箱子 - 洛谷
考虑相当于是给了一些区间，要求最少集合，使得同一集合内区间不相交，线段树维护即可。
考虑数位 dp，然后统计答案即可。
将这棵树建出来之后，其实就是求树的直径。
感觉这题没啥营养啊，就是直接 $f_i$ 表示以 $i$ 结尾的最大权值，然后动态开店权值线段树维护 $dp$ 值即可。
P3116 [USACO15JAN] Meeting Time S - 洛谷
图上 dp 板子题，按照 topu 序 dp。
P10613 [PA 2008] Cliquers - 洛谷
整数拆分的模板，这个要好好看一下。
dsu on tree 好题，考虑两棵子树该如何合并，按照这种方式合并起来即可。
P2061 [USACO07OPEN] City Horizon S - 洛谷
考虑从前往后维护一下当前最大值，貌似还可以 ODT？直接维护一下最大值和贡献区间即可。
几个简单的 tarjan。
ABC
感觉没什么好题，其中 E 是个大模拟，F 是组合数推式子，用组合恒等式优化一下就行了。
11.10 ~ 11.16
本文章由 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
考虑可以删掉一段长度为奇数的区间，于是分奇数偶数分别维护最优决策即可。
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
首先考虑无解的情况，由于每种颜色刷子只有一个，因此考虑对于一种颜色，设他最前面出现的位置为 $st_{c_i}$，则若出现 $st_{c_j} < st_{}c_i < j < i$，则无解，也就是两个区间交但不包含，剩下的则直接维护出每种颜色区间 $[l,r]$,直接从前往后染色即可。
T2
P4785 [BalticOI 2016] 交换 (Day2) - 洛谷
考虑设每次取出的三个位置为 $A,B,C$，考虑每次操作，一定让最小值放到 $A$ 上，于是如果 $\min = A$，则不变，若 $\min = B$ 则交换前两个，否则我们发现 $A,B$ 我们不能确定如何分配，此时我们记忆化搜索下去，由于交换形成了类似完全二叉树的结构，因此复杂度有保证。
T3
考虑当确定 $a,b$，$c$ 和 $s$ 之间是成二次函数关系的，因此最优一定取到 $\max$ 或 $\min$，枚举 $b$，可以得出 $c$，随后找到最优符合条件的 a 即可。
T4
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 - 洛谷
之前题单里的一道题，考虑从大到小取，如果一个人同时作为多个集合的最大值，则只能把他删掉，要不然不合法，贪心用堆维护即可。
Luogu NOIP 模拟 T1，起来比较晚，发现其实合法的一定是在最大能凑出来之内，首先特判掉一些边界情况，剩下的肯定贪心从大到小取比较优，这里还需要注意到 $a_i$ 是假的，最多只有 $n$ 的级别，然后二分答案就做完了。
【MX-S11】梦熊 NOIP 2025 模拟赛 3 & WAOI R7 & FeOI R6.5（同步赛） - 洛谷 | 计算机科学教育新生态
性质题，首先如果最开始 $suml > sumr$ 直接搞到最左边然后一直向右平推即可，否则看看能不能吃掉右边第一个，如果此时右边能吃回来则 $l$ 必败，否则则是要比较两边的和，注意到只会攻占一个位置就做完了，前缀和维护一下。
比较简单的题，看到性质 $C$，考虑实际上每个点的区间，维护一下从根到这个点的前缀和，对路径上限制取更紧的，然后就可以求出每个点合法限制区间，相当于是给定若干个区间，每次询问这个点在多少个区间内，差分一下就行，这里还写了树状数组的差分。
哇，非常难的一道题！
其实是性质题，考虑当区间出现了超过 $27$ 个数字，则一定可以取到 $\max$，于是先计算这些区间，具体的使用一个单调栈，然后考虑小区间如何计算，发现式子可以拆成 $x \ominus (y \ominus (\dots))$，此时只有 $x$ 某一位只有一个 $1$ 才能产生贡献，我们直接枚举区间一维，枚举 $x,y$，然后计算贡献即可。
具体计算，我们需要满足 $x$ 和 $y$ 按位与的结果这些位置是不合法的，同时对于区间内不存在的这些位置，只保留这些位置，然后计算贡献即可。
要注意当我们需要使用单调栈统计每个数作为最大值的区间，统计贡献时，需要注意钦定相等的贡献算在左边或右边，否则会算多或算少，这里可以在从前往后单调栈时使用 $>$，从后往前使用 $\geq$ 即可。
11.15 ABC
掉大分了，E 是一个比较简单的线段树，考虑算一下贡献就做完了，G 貌似是多项式科技，据说要用 NTT，不会。
F 写了一个 IDA*，最后 TLE 了没卡过去，D 题怎么还是大模拟，这场输麻了。
11.3 ~ 11.8 总结
本文章由 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$，相当于是二维数点问题，然后就做完了。
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 晚 限时训练
比较简单的几个题：
A
直接维护每个数字出现次数，维护贡献即可。
B
考虑枚举 $a^b$ 的 $b$，然后 check 一下就好了。
C
考虑分别维护出每种情况出现的方案数与贡献，乘起来即可。
D
考虑枚举行的区间，发现对于每个数作为最小值贡献区间多选一定不劣，于是维护单调栈和前缀和即可，相似的题还有奥林匹克楼梯。
E
上面写了，主席树上二分即可。
11.3 上午 限时训练
T1
看到数据范围，直接折半搜索在中点处合并即可。
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
首先一个比较显然的性质是 $\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
首先有一个 trick，缺一分治，也就是需要统计去掉一个东西的贡献，例如删掉一条边维护连通性，此时可以考虑线段树分治解决。
看到这个，询问删除一个点的最短路，复杂度可以允许 $n^3 \times \log n$，考虑线段树每个区间 $l,r$ 维护不走 $l,r$ 内的点的最短路，对每个线段树节点进行 Floyd，在叶子节点对询问统计答案即可，时间复杂度 $O(n^3 \times \log n + q)$。
11.7 限时训练
T1
容易发现这是一个拓扑排序，但我们发现正着做取字典序最小不一定是最优的，于是反过来找字典序最大的，发现这个之后就很好做了。
T3
找规律大分讨题，考虑最开始的情况，然后分讨往后扩展即可。
T6
考虑这题要求实际上就是 $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-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 两道简单题
:::info[Hint] 发现点亮的灯会把整个序列划分为若干连续段。 ::: :::success[Solution] 做过的第一道多重集排列！
发现连续段之间互不影响，因此考虑对于每个连续段计算方案数，发现连续段只能从两个端点向内扩展。
因此每个连续段 $i$ 内方案数为 $2^{len - 1}$，然后考虑总排列数，由于同一连续段内方案数已经固定了，要从总排列数中去掉，最终答案大概就是
$$\frac{n!}{\prod\limits_i len_i!} \times \prod\limits_i 2^{len_i}$$ 需要注意处理两端的边界情况，边界只有一种点亮方案。 :::
:::warning[一个并不正确的做法？] 场上很快就想到了一个多重集排列做法，设 $s = \sum\limits_{i = 1}^n c_i$，则最终方案数为 $$\frac{s!}{\prod\limits_i c_i}$$ 这也就是这个题多重集排列的理解方式，但我们发现模数是给定的，不保证质数也不保证互质，因此不好处理逆元，于是考虑换种做法。 :::
:::success[Solution] 考虑每次从剩下的位置中选择 $c_i$ 个位置放上，然后剩余的位置就会减少 $c_i$ 个，直接从 $1$ 到 $n$ 依次做即可。 :::
CSP-S 2025 游记
本文章由 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-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。 - 调试记得先把同步流打开，否则看不到输出。
- 可以把大样例文件夹粘过来，但是要看一下是不是相同的名字（一般相同吧）。
- 记得先看好题目时间限制和空间限制，写之前先计算好。
- 能用的时间很少，一定要把握住每一分钟！！！不要空想！！！不要想着休息一下！！！不要想着时间还有很多！！！