大量参考 抄袭 洛谷闲话、游记、日记、某不知名站的记录。
老规矩（？），洛谷博客是删减版，内容严格少于个人 blog 上的。

省赛省选举重若轻
国决国集履险如夷

（from OI Diary-Madia Lemon）
多么想，像这句歌词一样啊。但可惜……我的确没有这个实力啊。

2022 CSP-S 游记

在洛谷上那个游记的确是乱写的，还是想好好写一写这些时候的事，所以就再写一篇。

初赛（2022-9-18）

因为初赛一直都能过，所以赛前也不紧张。
出于不知道什么原因，这学期停课开始非常早，9-11 就开始停课了。
其实还是不习惯于文化课，上学期就每周请一天假调整心态，停课前也请假调整心态来着。
所以停课于我而言是很有利于心态的。

然后也算是 9-11 开始谈了恋爱……？
和 npy 揉揉抱抱真的好舒服啊（逃

结果大概是没啥悬念的进了复赛，分好像还不低。

复赛

day1 指 2022-10-29，不存在 day0。

day -???

初赛之后，停着课，似乎和机房同学沟通多了很多。
不要教坏小朋友.jpg

然后被神仙 lqy 带着板刷 AGC 了，虽然他做了很多很多但我没做多少。

day -??

因为机房电脑连 codechef 太慢了，所以给它装了个代理。

之后见到了学校跨性别的学姐，真的好好看啊，羡慕死了。（然而她说她的一个朋友见到我就夸我可爱却没夸过她可爱以此来说明我可爱但其实我一点都不可爱）

似乎一直都很颓废，十一前看了《莉兹与青鸟》，十一假期看完了《Angel Beats》。十一假期也是出柜一周年（？）不过并没有什么活动。
然后也是十一前，和 npy 一起逛商场，我尝试 RLE 并自我感觉非常失败（）

把个人 blog 的链接公开给了一部分同学，有位高中同学说我的诗有种面朝大海的感觉。
（我内心：接下来我是不是快要去山海关卧轨了啊（x））

然后也跟很多人直接出了柜，从此我没有柜子（

做了第一次春梦（？）（x

day -?

模拟赛经常爆炸，一直在打暴力。

day -1

龟甲缚只用 15min 就能完成了，好欸。什么人会在 CSP 前绑自己啊（x

day 1

颓废一上午。

开考，看完题就（觉得）会 T1 和 T4。内心 os：难度乱排的吧，建议换组题人。
开写，20min 过了 T1，测速，飞快。
写完 T4 矩阵优化 dp，发现走的点可能不在路径上，一度以为假了。发现开始时把每个点的转移矩阵乘上周围的再乘回来就行，然后过了样例，测速，飞快，用时 55min。
看 T2，好像是随便分类讨论一下做完了。写完之后发现调半天都过不了样例，有点慌。好在之后发现直接 A 和 B 中各拿出 $4$ 个有代表性的元素暴力做就好了。于是写写写，总用时 45min。
看 T3，发现不会。瞪了 0.5h，发现是个基环树，但还是不会，反正还有时间，于是先写个暴力。然后又瞪了 0.5h，发现是出度均为 $1$ 就可行。突然，就像是神告诉了我可以哈希一样我就会了，然后写正解，过了样例，共用时 90min。

以为 AK 了，于是吃了点东西。
笔袋上挂了个 trans flag，大概没人认识。

在场上以为人均 AK，出来发现好像也差不多（

day 2~3

自测，发现 T1 T2 全挂了，T1 挂的原因是没判断不能过点 $0$，T2 挂的原因是一处 $m$ 写成了 $n$。然后就以为没 AK 了，错失 OI 生涯中唯一一次 AK 的机会，而且要直接挂成 200 了。

day ?

出分了，noi 那网站还是有提前查分的 bug，于是前一天晚上就知道 AK 了。其实对这个结果也不是特别惊讶，毕竟根据 CCF 一贯的造数据风格，大概率会把它放过去的。
还是挺开心的！

或许填上了欲望的框
才能让我
越过悲伤

（from 合目《越》）

2023NOI 春季测试游记

不存在 day0，day1 指 03-04。

其实包含一部分 CSP-S 后的内容。

day -???

CSP-S 考的还行，然后就一直想着一定要进省队线。很有压力，很紧张，很焦虑。
特别是感觉到自己 CSP-S 成绩完全是运气好而导致的。
那一段时间就，精神状态也不好。
NOIp 前，真的是啥也不会了。

NOIp 前看了《心理测量者》第一部。其实很有趣的，但是对于虚渊玄把圣护写死了很不爽。

不过，所幸我这个省的 NOIp 因疫情取消了。
唉，又是运气好啊。在状态最差的时候取消了比赛。

NOIp 之后，看了 124 三个题，发现只会 1。听说 t3 是容易的，但是当时精神状态不允许我理解题目……而且我也不会边双。
所以精神状态就更差了。

day -??

模拟赛被喷太简单了。
去杭州集训了，写了一大堆鲜花。
面积了 OI 网友和非 OI 网友，好像有点尬（x
可惜没见到 zak 就得了 COVID-19 然后在酒店里休息。
事实上这次去集训几乎啥也没学。
看到了认识的网友的线下 impart 的直播，大受震撼.jpg

day -?

颓 MC。
期末考。没及格！（悲）
今天回老家，“这么高了” * n，“像个小闺女” * n （指头发长度），然而仍旧是男性化称呼而非中性化的。
心态稳定。很稳定。稳定。精神状态没问题没问题没问题没问题。

入坑了 Phigros，打歌 $\times \infty$。

还是很紧张的。

day 1

看样例。
实数？？？
不会有计算几何吧。

开题。
感觉 T1 随便做一做就行了啊。
感觉 T2 随便做一做就行了啊。
被 T3 吓死了。
完了，不会 T3 和 T4。

于是先 30min 把前两个题写了，去想 T3。感觉没有对的贪心，然后猜了个状态发现很对，直接 dp 做完了，于是 30min 过了。
还有 3.5h 做 T4，优势在我。然而并不在

以下是考场思路。

要相信所有题都是可做的。

• $k=1$：直接算；
• $k=2$：较大值放下面，较小值放上面，直接算。

$30$ 是容易的。思考 $k=3$。
估计一波省队线 $360$。
值域只有 $3 \times 10 ^ 4$。必然有大用。

• 必须让所有最大值和最小值不在同一行。（不过好像没啥用。

考虑对值域做……？
来，暴力：枚举每一行上下界，如何判断可行？
——对每个转轮看，$k$ 种转法是否可行。
二分答案，获得了一个 $a^k nk \log$ 的做法，期望得分 $0$ 分（雾
不过至少 $n$ 不在指数上了！（雾
其实好像是 $\min (a, nk)$
然后多了 15pts。

钦定每一行的区间越来越小？
这样最后一行最小值不用枚举了！第一行最大值不用枚举了！
只用枚举 $k-2$ 个区间！
复杂度 $a^{k-2} nk \log$。
看起来能得到很多很多分。

可怕。队线不会是 $400$ 吧。

考虑如何优化一下这个问这玩意行不行的过程。
根据那个啥，考虑分治！
分个锤子.jpg

对于 $k=3$，考虑把中间所有可能性记录下来。
然后我们获得了……$n$ 个大小小于等于 $3$ 的集合，每个集合选个数，问这玩意极差能不能在 $mid$ 里。
考虑枚举最小值。转化为，每个集合是否有一个数在 $[x, x + mid - 1]$ 里。排个序，双指针，数颜色，开桶。
是不是，是不是 $nk \log a \log nk$。
获得了很多分阿！
看起来非常优秀。
其实感觉，我是不是要阿克了。从 csps 阿克到春季赛是个很爽的事。
希望可以阿！

考虑，$k=4$！
$k=4$ 有非常多分。

如果按照上面那个办法优化的话，它就是……
好难描述这个事。
但是，如果再暴力枚举一行的，复杂度就变成了 $a ^{k-3} nk \log nk \log a$。
$80$。很好。

其实每次看到“在你的百般劝说下,小 I 承诺以后锁车不用有大于等于一万个拨圈的密码锁。”都想笑。
前几天还非常非常焦虑来着……不过好像还行。

欸好像直接计数排序就省掉了一只老哥。
那你 $10000^2 \log(30000)$ 也冲不过去吧。
其实说不准。说不定就过了，然后 $85$。哦多测阿你废了。
木有用阿。
先把 $k \le 2$ 的写了吧。

10:43 写完了。

哦好像，中间两行的最大值……哦不确定阿寄。
欸不会是，直接枚举发现种类数很少然后直接冲吧。
还有 2h，优势在我。吃点东西。
对了 CCF 这次为啥大样例是 windwos 格式。不懂哦，唉。

考虑分治。
好像困难。

中间是 n 个二元组集合。
考虑放到平面上，矩形数颜色！
有病吧你。
？？？好像真行。

……平面上数颜色怎么做来着。
反正有低于线性做法吧。
不过只用求某个正方形内颜色数量是否等于 $n$。
$k=3$ 是一条线，可以双指针，但是平面上……
从下到上枚举，动态区间数颜色.jpg
这东西是不是只能根号。
可恶。好难写。
复杂度是…… $nk \log a\sqrt{nk}$。
还有 113min，优势在我。
开写！

发现还需要枚举最大值和最小值在环上差距。寄。复杂度多个 $k$。

好像 $k=4$ 不是平面数颜色。有点……
但可以写平方的。好像有 $80$。
算了。$80$ 就 $80$ 吧。其实也挺好的了。

内容包含敏感词，请写“确定提交”

我：？
CCF 是敏感词.jpg

为啥对拍这么卡阿……电脑不好。
而且居然一次就过拍了，开心。

还有 39min，可以继续想一想 $k=4$ 怎么做。先让它拍着。
其实要是说队线 $400$ 也没什么关系。$380$ 和它的差距还是比较小的。
乱优化了一个地方它就跑的飞快……不会要阿克了吧。

然后 $k = 4$ 完全没想出来，于是写了暴力跑路了。但是这个暴力好像跑的非常快所以分也不低。

day 2

自测，没挂分，其实挺开心的。

其实一直是想着要证明自己的实力的，然而直接就证明了自己没实力。

NOI2023 省选游记

依旧是，没有 day 0，day 1 指 2023-4-1。

我若前行
沿这条路
此后梦中
便再无人恸哭
我愿前行
永不会再踌躇
继续我的旅途
寻找我的幸福

（from JUSF 周存《蒲公英之路》）

day -1

很紧张。很紧张。想进 A。

day 1

看样例，好像还行，没什么离谱的，似乎有个数数。

开题，T1 几乎一眼，T2 和 T3 不太会。
把 T1 写了，想 T2 和 T3。看了半天，看出来它有个性质，选的那个点集必然包含任意一个生成树的重心。然后就尝试抽一个以重心为根的 dfs 生成树来 dp，好像只用记录一下能不能跑到上面。T3 好像会了个 $O(nm\log)$ 的做法，先扔在那。同时发现彩蛋（？）：NOI2022 省选（
之后发现要枚举连通块大小，算了一下好像只有不到 $700$ 个，每次 dp 又是 $O(n)$ 的，感觉很稳，于是就开写 $k = 0$。
怎么这么难写啊.jpg
写完了，过了样例，于是尝试直接冲正解，然后发现写不出来。退而求其次，写树的部分分。写了好久好久才写出来，但是没树的样例很慌，于是立刻写个 $O(2 ^ n m)$ 的暴力开始对拍。调了调，拍了一会没问题就只剩小于 1h 了，很慌，于是迅速写完 T3 暴力。
只有 0.5h 了，开摆了，感觉 T2 写不出来。
出场发现不少人都过了 T2，很害怕，这是能写的吗？还发现好像 T3 是原题，更怕了，别到时候省队都没了。
而且我 T2 暴力没测速，感觉很可能被卡常啊。

day 2

小图灵出 day 1 数据了，好像还在队线里，感激，不过 A 队是别想了。

看样例，怎么有博弈论啊，害怕。怎么还有数数啊，害怕。剩下一个题不知道是啥。

开题。T1 感觉会了，于是在没想 T2 和 T3 的情况下开写 T1 了，还不知道自己正确性。
写写写调调调写写写调调调，终于 2h 过了样例，感觉很难拍于是直接扔了。
很慌啊，不知道 T1 多少分，感觉 day 2 乱打真要没省队了。
于是想 T2，感觉会了然后又假了又会了又假了。你能不能写代码之前认真想想这玩意对不对啊.jpg
然后就只有 0.5h 了，想着我怎么也不能 T2 啥都不会吧，于是拼了个暴力和性质 AB，好像有 $40$ 就扔了看 T3。
本来以为 T3 $10$ 分是容易的，然后发现不会简单 dp 了。没想到可以爆搜啊！于是写了 2pts 的判断可不可行。

总结，day 2 打的很爆炸。出场之后发现 T2 好像暴力挂了，但我测大样例没问题的啊。害怕了。

不管了！反正明天怎么说都要回去学文化课了，先把 OI 扔一边吧！没进队就没进吧！

day 3

……？回归文化课。

day 10

想不到，没挂分，而且就这垃圾分都能 A 队（听教练说的），有点离谱。

其实说是回归文化课，但实际上也没上几天，大部分时候都是请假……母亲日常请假，精神状态不容乐观。我精神状态也不怎么好就是了。
总的而言，只去了 1.5 天。

其实 D2T3 挂成了 1pts，然后 D2T2 发现能过 $n = 200$ 的 C 性质，于是就多了一点点分。然而没啥用。

她又要走多远的路、多漫长？
还要多久、
才能走达尽头？

（from 合目《陪着我》）