2023 联合省选游记

考完被抓回去学常规,现在稍微闲点,来补游记。

省流:$100 + 55 + 48 + 95 + 40 + 0 = 338$,看似问题不大。

Day -1

感觉只有 2 天了才发现省选居然如此临近了,以前虽然知道省选时间,但好像毫无感觉。不过教练也交代日常考试一样就行,于是就也没怎么紧张(

早上信心赛,发现 2 原题,写完就开摆。下午晚上随机看题 / 开摆,似乎复习也是没啥用?

Day 0

早上又是原题,不过好像考完都没评测就出发去电子科大了。路上一路睡觉,但是坐在旁边的教练一直吐,看的我都有点犯恶心(

先说是考试从东门进,我们酒店在西门,于是我们绕半个校区过去,结果那边又说随便从哪个门都可以,于是我们又绕半个校区回去,实在下饭。去了一家拉面,晚上没吃饱点 KFC 被教练看到了(

晚上手机电脑都被收了过后只能看点电视,结果连 CCTV 直播都得会员 /qd,最近的各项赛事都没法看。为放松心情,去看了很久前的欧冠 1/8 淘汰赛皇马客场挑战利物浦,其实只为看两边守门员互送大礼(

本想看完的,不过看完半场实在困倦,于是直接睡觉,大概是 12 点吧。

Day 1

早上 7 点起床,没感觉怎么困(可能是和日常学校睡眠时间差不多吧),吃完早饭去考场,发现站着的人群中有 cosplay 原神角色???(我不懂,同校告诉我的)关键看他也进了考场,应该还是考生???

大受震撼,不过很快平复心情。发现电子科大的电脑不是我初三时来的 win7 + Dev 了,已经是我从来没用过的 win11 了。不太会用,不过问题不大。

8:30 开题。T1 一眼签到,T2 估计 tarjan 缩点过后 DP 之类的做法,T3 大 ds,先不管。

先想 T2。想了老半天,发现一个点双要么把里面的边全部保留,要么全部删除,不可能出现保留一些边的情况。然后建圆方树大概可以转化为一个树的情况。

即使是 $k = 0$ 树的情况也不好做,于是先去写 T1。意识到 $k = 0$ 最多只有一种划分方法,可以把多余的点拿出来拼到当前节点上,看是不是给定连通块大小。但 $k = 1$ 好像变数比较多,没怎么想清楚,大概还是一个多余的点拼上去的过程。写完过后就一直循环在一个 叉掉假做法 - 写假做法 的循环之中,根本无法通过样例。判断的细节真 tm 多 /tuu(当然有可能是做法不太对

11:30 了还在此循环之中,于是果断看 T3,发现有一个简单的 $O(nq\log ^ 2 n)$ 的贪心做法 48 pts,光速写完。感觉剩下的每一个部分都不好做,即使可做也是百行代码得个位数分。想想写这个不如调 T2 做法,于是又倒回去看 T2。

又调了半个小时无果,发现已经 12:30 了,做法还是假的,成功烂尾(感觉也不是烂尾?),于是先把代码阉割一下得到 $k = 0$ 的 $O(n\sqrt n)$ 的做法,然后光速写一个 $O(2 ^ n m)$ 的暴力拼起来,差不多至少有 55pts,$k = 1$ 就随缘了。

慢悠悠的检查了文件操作和编译问题,下考。出考场的时候听到有人说“二分还是三分””三分“给我吓一跳。后面好像发现意思是写了几个题。

出考场大概知道我 T2 $O(n\sqrt n)$ 的思路是对的,不过确实调不出来。

下午吃完饭就看了一下 Matrix-Tree 相关线性代数,不过实在看不进去。猛的发现今天没 DP,岂不是明天是 DP 专场?毒奶 ing……

晚上教练点了 9 or 10 个菜到酒店,然后我们连上教练才 5 个人。显然是吃不完的,于是摆条了很久,慢慢悠悠的把大部分吃了,最后吃了 2 个小时 /hsh。

没怎么复习就收设备了,于是把昨天没看完的下半场打开看,结果看到皇马 3 球领先就没兴趣了(

Day 2

早上 7 点起来还得收拾东西,结果肚子一阵翻腾,感觉今天可能要被催。光速收拾好结果发现隔壁也没收拾好。一问才发现那头也是肚子问题,盲猜昨晚上的干煸肥肠或者干锅有问题,因为好像教练没什么问题,只有我们吃过的好像就这俩(

进考场感觉今日状态不是很好,主要是肚子翻江倒海,很不舒服。8:45 就去上了厕所,要好得多了,后面也没出问题。

迅速浏览题目,T1 暴力?哦还有平局啊,想起一个 ARC 的题好像就是在图上轮流走,不能走者败的类似模型。依稀记得是一个点能走到败点就是胜点,出边全是胜点就是败点,否则平局点,建反图按 DAG 做就好了。还在想状态数,结果发现只有两个红棋,一个黑棋,那不是只有 $O((nm) ^ 3)$ 状态,结果 $n, m\leq 10$,那我会了(

T2 一眼 2-SAT 判断合法性(什么?值域连边是什么?),想想 2-SAT 由于逆否命题的优美性质,感觉比较可做(我在想什么呢?小编也不知道)于是编了很久编出来一个 2-SAT 图上跑 flow 的做法,感觉不好写,于是先写 T1。

T1 怎么这么难写啊!难写程度确实出乎我的意料啊,主要是判断状态出边和压缩状态一步比较烦人,还有就是这个加强了 ARC 的题,现在是需要求出最优步数,编了一会按照什么方式排序已入列的点。想了半天才发现这个加点过程本身就挺合法的样子,于是直接把 std::priority_queue 改成 std::queue 就好了,还少 log。 结果一跑大样例 2s+,只有 6 组 $n = m = 10$ 的点而且还有一些 subtask 的数据在里面。还以为机子慢,结果看到机子是 i7-10700,就不好说啥了。又煎熬的卡了会常,卡到了 0.4s 左右,应该差不多了吧(

光写 T1 就用了 90min+,感觉比较危险,已经差不多 11 点了。于是先去看 T3,结果看到了永远不会的 LIS 相关。题都没读懂,盲猜 sub2 开始全部不可做,也懒得读题写 sub1 了,于是写 T2。

容易发现 2-SAT 做 T2 光判断合法性就需要前后缀优化建图(为啥想到这里的时候还觉得这个做法很合理呢?可能觉得 D2T2 本身就不是可做题吧),容易发现编的 flow 做法完全无法写出来。于是最后写了个 AB 和暴力就跑路了。

检查文件操作和编译问题,下考。出场的时候没觉得今天很下饭,路上听到有人说 T2 的 C 性质怎么做,感觉问题不大。

同校同学好像不太会 T1,搓了点暴力,感觉比较危险。因为 T1 不是什么很难想的题吧(

下午水群闲逛的时候才发现 D2T2 不是很难,想到值域连边后面是一个神秘贪心。可惜第一步想错了怎么回事呢?

后续

4.3 早上起来看到教练已经打了个电话还没接,又听说 xtl 可以查总分了,于是回教练电话之前先看了 xtl:D1T2 直接 95pts??排名来到了全省 rk4(话说 383 也不是很高的分数罢)回教练电话说应该没啥问题,但是 yundou 上只有 308,叫我去看看。一去 yundou 发现 D2T1 被卡常成 65pts 了,有点危险,不过 yundou 上也是 rk12,加上 NOIp rk13,怎么算标准分应该都问题不大。

4.5 回校过后才开始关注我们同学的成绩,似乎他们就略惨了:D2T1 没判红棋走到一起的情况从 65pts 挂成 0pts,各种奇怪的挂分。此间连利益不是很相关的我都一度十分紧张,最后好像他们都在省队线下面 5 名之内,去掉被 1/3 卡掉的人的话就是省队线下面 1、2 名。不过这事还没有完全结束,现在下定论还有点早(省队名单尘埃落定了再写)

总分最后 D2T1 挂了 5pts,D1T2 也没有多得一分,总分 $100 + 55 + 48 + 95 + 40 + 0 = 338$,加不加 NOIp 成绩都是 rk6,属于是比 A 不足,比 B 有余了。

总结

总的来说还是打的不算好,毕竟 D1T2 会但调不出来(虽然不是正解,但至少现在已经调出来通过了这个题了),D2T2 应该也是能力范围之类的罢,结果都没有做出来。还得提升自身水平罢。

NOI2023 再战!