2023 省选 流水账

· · 个人记录

*day 2：

三点多钟起床，没啥事干，于是坐公交提前了亿点到了首师附，沿 北洼西里-七贤村-阜城路-航天桥-（花园桥）-岭南路 溜达了一个多小时，卡点才进考场。感觉比省选本身有意思多了（）

好的不扯了。我不觉得一场比赛有什么可游来游去的，所以下面都是用写题解的态度写的。

day 1:

T1:

一眼秒掉按左右端点分别排序扫一次，维护能到达的左右端点的做法，大约十分钟写完调完（几乎不太相信省选有这么水的题），看起来样例不弱，于是不拍了。

*期望得分 100。

T2:

前后读了好多遍题意才把漏看的条件看全。。而此时已经过去一个多小时了，想了想还是不太会，于是开写 m\cdot2^n 的枚举 V' 大暴力，还好并不麻烦，就是可惜这计数题的样例答案分别为 2 和 3, 感觉强度不太可靠，但我找不到什么东西能和指数级的暴力对拍，所以摆了。

然后想性质分。容易发现 k=0 时可能的连通块大小只有 d(n) 种，又容易发现 m=n-1 是棵树（废话），可以树上背包，对于每种连通块大小 t 能够 O(n^2) 处理。那么我们…哦但是为什么 m=n-1 的部分分 k 都是等于 1 的？？？没想到整除分块，不会枚举连通块大小，寄了。

*期望得分 125。

T3:

第一眼看像动态 dp，再看像线段树分治套什么东西…反正肯定是我不会的神奇数据结构…？直接想 nm? 级别的暴力，发现每次计算只需要自叶向根依次贪心换最小值就行了，那么可以线段树或者启发式合并 multiset,。后者好像比较好写，虽然带俩 \log 但这个时限下无所谓，于是在十一点多写完调完了。样例一看就很强，所以继续自信不拍。

最后一点时间想性质。A,C 看起来比较可做，但可能因为我比较蠢，想到的 C 做法需要维护区间第一个 \leq 0 的数和区间第一个 \geq 1 的数，不太会写，也不太相信这东西套个树剖的时间复杂度，于是不管了。

*期望得分 173

upd：民间数据 100+25+48=173。好像成为了垃圾大众分？

day 2:

T1:

一眼不太会做，先开T2。

最后剩一个多小时写了 65 pts 部分分，可惜写得又丑又乱，大样例有点弱，希望不挂。

*期望得分 65

T2:

想了好半天，但是连基环树都没有想到！最后只写了极为一眼的暴力分和性质 ABC, 啊但是 C 我只会费用流。。而它并没有退化成 n^{3/2}, 于是写完发现只有 44 pts。

然后开摆，罚坐。

*期望得分 109

T3:

有趣的，题都没看懂。

*期望得分 109。

出考场感觉大众分有 130, 但好像是我的错觉（x）

upd：有点难受呜呜。xtl 挂成了 [25,65]+44+0=[69,109]（原因 T1 每个点（即使有性质分）都先暴力 dfs 一遍检查正确性，但 dfs 内部判断步数的东西没初始化哈哈哈哈，于是就看数据心情输出了，不理解为什么我对自己的性质分这么不自信。。）

不过鉴于这是我第一次打省选，也是第一年学OI，所以没挂得太惨就算赢麻了啊。~~~

xtl：100+25+48+25+44+0=242, rk\ 40+

官方数据更为逆天： 100+25+48+5+44+0=222，不知道 rk 多少了哈哈哈哈

悲………不过算帮助认清了自己很菜的现实，下学期见。

upd：[数据删除]