NOI 联合省选 2023 游记

寄麻了，退役。

坐标 SC，NOIP 125。

Day -4 $\sim$ 0

省选要来了，很慌。

开始打各种板子。

星期四上午“全真模拟”直接变成省选信心打击赛，我 T1 连简单的倍增都不会，成功垫底。

中午 ygg 直接放了，但是我家长没来，在学校呆到星期五下午我才去酒店。

到了酒店啥都不想干，直接开颓。

Day 1

慌。

虽然我声称了我考试时不吃东西，但爸妈非给我塞了个面包。

来的比较早，在 ygg 面前站了 5 分钟不知道干啥。

考场居然不能带吃的，要吃得出去吃，不好评价。

进考场一看键盘，又是阴间布局，Enter 占了反斜杠的位置，反斜杠在 backspace 左边，backspace 只有一半大。正在调各种设置，监考员又在怒斥怎么到处都是鼠标声，《别让我抓到你在敲板哈》。

开考直接看 T1，一眼，排个序贪心一下就完了，20 分钟切了。看 T2，没啥思路。随手画了个图，发现要保证选的点切断边后不连通，一个点双上的点只有不选、选一个和全选合法。建广义圆方树，设一个方点被选了当且仅当周围所有圆点选了，那么选出来的点在树上形成一个连通块。考虑钦定一个圆点被选择了，进行树形 dp，在之后的计算中钦定这个点不能被选。先枚举连通块大小，然后用背包算出有多少种方案，总共 $n^4$，$35$ 分。实在不会优化，先敲 T3 暴力去了。考虑每次暴力求，从下往上选，把当前元素填到子树内最小的位置即可，按 dfn 序拍到线段树上维护。$nq\log$ 有 $48$ 分，打完跑路。然后回去优化 T2，搞了一个小时，最后套个点分治变成 $n\log n$ 乘子树大小和，$35\sim 65$ 分。最后半个小时想继续搞 T3 没搞出来，NOI Linux 下检查编译，检查空间，检查 freopen，虽然考过这么多次了，但是马上收卷的时候依然很怕出傻逼错误。

考完遇到 zc 和 lyh，lyh T2 只有 $2^m$ 的十分。zc 差点切 T2，但他声称没调出来，T3 也没打暴力，但按照经验，他该切了 T2。听了思路，好像很有道理，但是又不完全懂。出来给 ygg 报的 $170$。

在 luogu 上看到 T2 解法，原来有个傻逼结论，子树大小小于 $l$ 的一定要选，大于等于 $r$ 的一定不选，正确性显然。这么傻逼的结论居然没想到，像被撅了一样。

T3 好像是线段树分治套树剖或全局平衡二叉树之类的，反正我不会。

出代码后拍了一下 T2，居然和 SC-001 和 SC-002 都不一样，慌麻了，但看了他们的代码应该是没有写 $n\le 200$。zc 和暴力拍出错了，看来真挂了，太可惜了，他实力很强的。

云斗学院 T1 T3 T2 数据先后出了，$100+65+48$，没有挂分，主要看 T2 有多少链的数据，如果挂的不多还有可能翻盘。zc $105$，lyh $158$。

看了一些游记，T3 暴力居然都搞的很复杂，有点怕，再次验证了一下 T3 暴力正确性。

Day 2

早上大图灵出数据了，$100+55+48$，省排 8，还行。zc $140$，lyh $183$，假的 dp 都水了这么多分。

开考看 T1，好像对抗搜索，但是应该过不了，T2 应该是奇怪的图论，T3 应该是奇怪的计数 dp。先搞 T1，结果忘了对抗搜索怎么写了，记忆化没有加时间，还判了重，样例都要 WA，调了半天，才发现完全是假的。当时已经过去了 1.5h，很慌，怎么也想不起真的对抗搜索怎么写了，最后改成平局不记忆化的爆搜才没有 WA，但是几十步的样例都跑不过，搞完已经 3h 多了。T2 暴力 $20$，还有几十分特殊性质 ABCD，我只会 $n\le 200$ 的 ABC，总共 $12$ 分，没写。T3 写了个 $10$ 分暴力。然后又来检查一系列东西，但是我预计今天连 $100$ 都没有，直接开摆。

出考场翻以前代码才记起对抗搜索怎么写，而且 ygg 还专门讲过对抗搜索，寄麻。lyh T2 还写了 $32$ 分的特殊性质 ABC，写的是网络流，我才想起可以用网络流写。

下午坐车回绵阳。路上一直很慌，害怕对抗搜索能过 T1，白丢四十多分。云斗学院 T1 出了数据一测，我 T1 $50$，正常的对抗搜索 $65$，问题不大。zc T1 好像挂了，只有 $35$。测了一下其他人的，好多都过了 T1，但也有不少五六十的，心里算是有了底。T2 马上也出了，我和 zc 都是 $20$，lyh T2 的 $n\le 200000$ 的特殊性质全 T 了，只有 $32$ 分。寄老师 T1T2 都切了，拜谢。

晚上出了 T3，我还是没挂分，但是 lyh 挂了。T1 数据更新又给我搞回 $65$ 了，离大谱。

Day2 寄麻了，应该人均会 T1，还有不少人会 T2，我 $100$ 分都上不了，应该是寄了。

估分 $100+[35,65]+48+[55,65]+20+10=[268,308]$。

Day 3 $\sim$ 5

ygg 给我们放假，颓。

云斗学院 $100+65+48+65+20+10=308$，数据强度应该不行，CCF 的数据可能会很强。

大图灵 D1T2 之前还是 $55$ 后面变成 $65$ 了，数据强度越改越弱是吧。总分 $100+65+48+55+20+10=298$。

希望能进吧。

Day10

出分了

D2T1 挂成 $30$ 了，被极限强数据卡没了。

$100+65+48+30+20+10=273$

Day2 4 个小时爆切 $60$ 分。

好，退役。

把 D2T1 改了一哈，才发现红棋相遇是不能走，我以为是相遇了然后输，这样算出来步数就要多一步，寄。

ygg 给了校榜，刚好卡到 12 名，哈人，险进。但是看起来连 SC 榜都上不了，寄。