2023 省选游记

· · 个人记录

Day -4

NOIP 被喵了个喵寄飞了，近乎压线上的一等。

剩下四五天时间不打算学算法了，打打模拟赛刷刷往年省选题找找手感。没有申请停课，不过现在的状态也和半停课差不多了（

数论内容好像还是很差/jk 希望别考或者少考数论题。

往年省选题只能切几道，后面切不动了（

Day -3

尝试部分分练习/jk 毕竟考场上做出更高部分分比想出正解对于我这种 cg 来过简单多了。

浅浅复习了图论和树上操作。计算几何，多项式和线代都只会基础，不过既然 FFT 都 10 级了应该也不会考多项式吧（（考了就暴力卷积，其他两个只能看天意了/kk

有点紧张，但不多（

Day -2

开摆 day，还打了场 CF 掉大分，希望涨点RP（？

Day -1

在家摆，调整心态，省选希望考出属于自己的水准，能否进队当作结束后的后话叭，目标就是得到尽量更多的分数吧

Day 0

来 fz 了，一整天都在看小说/玩游戏，没怎么复习，希望明天能以最好的状态应考

rp++

晚上去旁边学生街吃东西，买了一大车的东西根本吃不完，晚上溜去别的房间玩游戏，想了半天玩什么小游戏，最后下载 Fall Guys 到了 10 点，决定第二天再玩，就回去睡觉了。

Day 1

晚上被酒店的床和半夜陡升的温度给搞了一波心态，不过整体状态还算不错，早上 7:20 吃早餐进考场，前一天猜了个会不会有大表格。

8:20 进考场，意外的是昨天试机坐错位置了。于是整设备花了五分钟，坐下的时候已经 27 分了，看了眼数据包，然后 transfer 有十五个样例直接给我吓麻了，大概看了一眼，station 和 cities 有点像图论问题，transfer 好像要多测？（不确定

过了两分钟就发密码了：flood#head0413，没有想明白 0413 这个数字有啥特别的，打开 pdf 的时候在默念无数论题。

大致扫了一遍题，第一题题意很明晰看起来就是简单题，第二题是个让人头疼的无向图计数，第三题看到 N=10^5 时限 5s 的时候就觉得是个大数据结构。于是先去想 T1，细看直接在 s 周围合并线段再计端点就可以了。大概写了 20min。

大约九点的时候去仔细想了一下第二题，在想这种连通性的问题应该是边双还是点双，然后想了半小时无果决定先去开 T3，想了一下子树上的点限制会比子树根节点，每个节点的最大容量又是子树大小，于是在每个节点上开了一个堆来维护容量大小，最后回溯的时候向上合并前 cnt_x 大小的堆。时间复杂度不太会分析，好像有点假，但是两个 n=2333 的大样例分别跑了 2.1s/2.3s，感觉可过，这个时候已经是 10:50 了。

决定回第二题先做 k=0，可以发现的是 k=0 的情况下答案非常少，于是先找割点再处理所在连通块的大小，然后发现我的 tarjan 找割点寄了。。。调了 20min 无果，决定打暴力搜索。

考虑一个点集对应的就是一个边集，然后 n\leq 20 的数据范围显然可以枚举 t 个联通块内的 t 个关键节点，也就是向外界连边的节点，然后把这样的关键节点间的边断掉，构建一个新图并用 dfs 计算联通块大小，维护一下极值不超过 k。

这时的得分是 100+25+34=159，没有发现好入手的部分分了，于是去上了个厕所（（（（（（

回来发现 T3 一个 6pts 不带修改的链可以贪心，怕把 10^5 的树形结构拉到 34pts 的做法上会导致 MLE ，求稳起见就放了树上的 6 分。又写了一个函数来测试点分治/jk

最后 20min 测了一下样例。发呆了 5 分钟恍恍惚惚地走出了考场，觉得最多比大众分高一点，很难摸到队线，不过还是稳住了分数。

upd: 小图灵 100+25+36=161。

然后从两点多玩游戏玩到了十点多，草草收拾一下就去睡觉了。

Day 2

猝 死 局

开题面的时候看到 color 和 game 两个文件名就感觉要出事，过了一会发密码了，是个 pku 啥了，忘了。

第一题拿了几个样例手玩了二十分钟没有什么思绪，于是先打了 1,3 两个性质分，打完大概在九点五十。

第二题开起来就是想可否优化建图 2-SAT，在缩完点的 DAG 上贪心选点，想了半天感觉怎么贪心选都是假的，于是决定先写出来再讨论，然后花了大概 40min 写写写写写，写完又假了（

这时已经 11:10 了，心态有点爆炸，写了个第一档暴力走了。

然后性质 A 由于 2-SAT 还挂了甚至没拿到分，看了一眼 C 觉得相当不可做，想着我也没什么分打得到了就写了个 2 分的测试点 1,2 的第一问。

感觉有点难受，平复了一下心情决定剩下 50min 写个 T2 的性质 B。

结束前 15min 写完了，这是还注意到旁边的同学一会睡觉一会打游戏，感觉这样直接开摆倒也不算反常（可能 Day 1 炸了吧），又测了下样例，然后怀着非常遗憾的心情等着收卷了。

最后分数大概是 35+32+2=69。

upd:云斗学院 100+25+28+35+32+2=222，FJ rk29，寄飞咯。

还能说什么呢，还有什么可说的呢，只能说菜是原罪吧。

这次省选带来的感受不是 NOIP 那种遗憾和不甘，而是尝试多次无果的题目带来的无力感吧。

还有一年时间，但也只有一年了。

直到现在还有一些不真实感，从中考前夕才算真正接触 OI，而这一年来的热忱支撑着的 OI 生涯，有些功利心，又有在学习新知时感受到的乐趣。在省选赛场上几乎没有挂分对于我来说已经是一个相当不错的进步了，但我在正式赛场上的机会也没有几次了。

最后可能 NOIP + 省选 128+161+69。

大约是在三倍队线左右，这小半年也算有了一些成效，应该不会买 D，也有可能根本没有机会买 D 咯。

Day ?（4.11）

最后分数是 100+25+28+25+32+2=212，大概还是全省 rk30 左右吧，竟然成为了 D1T1 数据弱，D1T3 & D2T1 数据强的受害者了qwq

但是再其他人的挂分下最后小图灵上的参考排名是 rk26，全国 rk537，也就是在恰好二倍队线qwq，实际上如果赛时注意到 D2T1 的状态数只有 10^6 而想到了有向图博弈而去写 D2T1 的话，可能就翻盘进队了，不过现在的叹惋已经太晚了，只能将希望交给明年了。