OI Diary 06：2023 福建省选游记
今年省选没有停课，训练强度和自身实力都决定了基本没机会进队。所以主要是去春游，顺便积攒经验。
Day -1
仍然在永泰某基地军训。晚上班主任给开了假条提前坐车回家，要不然第二天没时间看考场。
军训期间只看了两眼简单的算法，没有设备，也没什么机会复习。
Day 0
上午在机房打了一点简单的板子，很小丑地忘记了怎么线性筛积性函数。最近模拟赛打得有点少。省选计划后期模拟赛欠了好多没补……之后可以利用起来。
下午学校组织坐地铁去师大附中看考场，期间向 hy 学到了怎么用宏定义来编译。机房一的键盘是好用的诶，开心。
因为中午和附中的一个朋友约好，看完考场等她一起吃个晚饭再走。于是偷渡进了他们音乐教室，然后一边看蓝书复习，一边听合唱团训练。他们训练真的感觉好专业，氛围很轻松有趣……那个老师也很开明，直接让我坐在旁边看。不过我还穿着三中校服，反而自己有点尴尬。
见到了很久没见的好朋友还是很愉快的。而且成功蹭到了附中食堂的饭，比我们学校好吃太多！！又是羡慕别人家食堂的一天。
回家再读了一会儿蓝书，这时候训练更多也没用了。
Day 1
要早起的周末好难受……怎么这周都没机会睡大觉阿！伤心！！
在考点楼下发现附中参加省选的同学好多，估计要占满三分之一名额吧……
$8:30$ 开考后，先阅读了 T1，发现非常可做，于是后面两题只扫了一眼，准备先把 T1 解决。
为了稳妥，决定写个最坏 $\mathcal{O}(m^2)$ 的暴力，即从包含 $x$ 的区间为开始，暴力扫所有区间，把与现有区间有交集的区间不断并起来，顺便记录答案。
然后马上想到一种优化，就是区间排序后，从 $x$ 开始双指针 $\mathcal{O}(m)$ 向左和向右扫。当时觉得包含 $x$ 的区间不太好处理，就搁置了这个想法。现在想来可以把穿过 $x$ 的直接拆成左右两个区间。
又重新想了一下暴力的过程，发现与其从 $x$ 开始向左右并，不如直接做全部的区间并，再用并查集来找到和 $x$ 处于同一个连通块的所有区间，这些区间只要满足 $l < x$ 则答案包含 $l$，满足 $r > x$ 则答案包含 $r$。于是就写完了，复杂度是 $\mathcal{O}(m\log m)$。
然后和暴力拍了几百组小数据感觉很对，极限数据也跑得飞快，就丢掉了。此时是 $10:00$。
休息了一会儿，准备开 T2 和 T3。
先认真看了 T3。第一感觉的暴力是树剖然后暴力贪心，似乎可用线段树之类的维护最值，有 $40-50$ 分。但是写到一半发现调不出来。
决定写一个更暴力的做法，直接用优先队列维护最小的位置，然后在 dfs 的过程中合并选点，大概是个 $\mathcal{O}(m(n+k)\log n)$。不过因为没有学过可并堆，导致写出来常数爆炸。测了一下大样例，感觉只有 $20pts$。
回去看 T2，吃着面包读题终于了解了题意，写了 $\mathcal{O}(m 2^m)$ 的暴力就润。后来发现暴力莫名写挂了。不过没什么大事，$10pts$ 加上去也进不了队。
快结束的时候电脑死机，还好文件有存。
出来发现又是低于大众分的一天，好像人均 $150+$。讨论了下 T1，有各种各样的真做法，反正就是签到题。
Day1 就这样过去了。btw 附中旁边摆摊的无骨鸡柳很好吃，以后还来吃。
Day 2
昨晚睡得有点晚，早上起来困困困。
正好 T1 的部分分看起来很像大分讨，所以 Day2 的前半场就思维缓慢地写 T1 的部分分，其中 $9$ 步以内的搜索莫名写挂了。后来写到了将近 $11:00$，是 4.5k 的烂代码。
正解似乎不是大分讨，只是 bfs 题而已。不过场上没想到……部分分大概有 $35pts$ 吧，如果分讨没挂的话。
后面越写越精神，但是后两题都有点困难了。
T2 写了个大力 dfs，似乎有 $20pts$。
T3 暴力写挂。感觉只剩下 $2pts$。
Day2 就这样挂没了。但是好像大家分差没有很大。
下午考卓越杯，莫名进了复赛。连写带蒙地写完填空题，大题啥都不会。于是睡了半个小时，好困好困。
D2T1 测民间数据挂掉了 $10pts$，有点难过。估分如下：
Day1：$100+0+[26,34]=[126,134]$。
Day2：$[20,25]+20+2=[42,47]$。
标准分离队线应该也挺有差距的。接下来要回归文化课了，但是还没决定退役。加油。
后
出分了，挂得有点惨
$100+0+22+5+20+1=148$。
♥