NOIP2022 游记

· · 个人记录

正文(11.28 day3 ver.)

day-7

才从学校回到家结果突然被告知要马上去绵阳，龙泉驿区要静默了？？

最后决定在同学家住一晚明天一早就去，手忙脚乱。

day-6

上午就到了绵阳，住的是两人一间的酒店，就在考点东辰旁边，环境还不错。

学校要考 noip 的同学都到了...

下午差点去面到多头了，可惜晚上要聚餐。

当晚健康码变黄了，很吓人，十点多被带去黄码专用检测点做核酸了，有惊无险。

day-5

绵阳要静默了，面多头机会没了（悲）。

但是面了 kds 。

同学们在酒店上 whk 的网课，我在模拟赛坐牢。

休息时间？o，启动，开始上班！！

day-4

稍微复习了点随机化相关的算法（去年 t3.jpg ）

今天没有模拟赛是做题，终于不坐牢了，小清新题。

做完了就上班。

晚上和同学看了会世界杯。

day-3

模拟赛坐牢，改完题上班。

晚上又和同学看了会世界杯。

day-2

模拟赛坐牢，但是自己切了个区分度还可以的题，以为打的不错。

一看榜，怎么大家都会啊？

改完题继续上班，以及复习。

没想到今天是我农历生日，吃到了蛋糕，好评！（虽然大家都吃过饭了）

调整作息，早睡。

day-1

最后一天了，开始复习一下（感觉 noip 没考什么啊），着重复习了 LCT 和 SAM 和 dinic 和 ddp。

晚上稍微上了一下班，终于攒到 50 抽了，绫华指日可待！

然后大概看了一下光速乘和快速模和莫队就准备睡觉了。

结果再晚点多头突然找我给我交流了点考前心态和考试策略，受益匪浅，感谢他！

day1

day1开幕

起早了点，感觉早上刚起的时候如果很早精神真是特别好啊！

（以后考试压着点起床是不是赢麻了？）

调整了一下吃的东西，不然考场当喷射战士寄了咋办。

最后要进考场的时候问了一下群友怎么扩栈。

八点进去发现 wfy 就在我斜对面考，不错，考完就能知道一个省队的预估分了！

他来了过后我们对视了一下，呃然后就没有了，接下来开始考试。

开场在没发 pdf 密码的时候在观察样例，发现没有字符串题目，心里放松了很多。

然后准时开考了，进去先看一眼时空范围和题目类型。不错，都是传统题，时空限制也很常规。

上次考试输在没浏览完所有题目再决定开写，这次我告诉自己一定要先读完题，大概花了十多分钟。

看完感觉 t2t3t4 都不像容易的样子，以为是 构造+计数+期望结合 ds ，不太是我擅长的。

t1

于是先开 t1，一眼秒了，大概 15min 过了大样例。

t2

然后开始看 t2 ，发现部分分很奇怪，于是考虑 k=2n-2 咋做，观察到这个太“偶数”了，所以就想配对，这样可以空出来一个位置，然后就是朴素的。

接下来直接开始想正解，因为 k=2n-2 的这个性质太好了，感觉多一个就是多了一些情况而已。于是还是考虑配对来做，然后到了最后一个空位要放进去的时候，发现有的时候是可以不放进空位的，因为底下的必须用空位来消掉！如果放成三个，如果最底下的被消了，不就转化成子问题了吗。

但是这样会不会导致中间的被卡住了一直消不掉呢？

继续想，什么情况下会导致卡住，一定是上面那个比下面那个更快被消去才会！

那么我们就不放到上面会被下面先消去的两个元素上面就可以了！

但是要注意这里的具体实现，我们需要存所有下面比上面先到的栈的编号拿来备选，让它可以变成存在三个元素的栈，需要使用无序集合 unorderedset 来做到线性。

那如果所有的都满足这个咋办，那我放空位不就好了。

于是接下来我们讨论的问题就是：所有栈都有至少一个元素，并且一定有至少两个栈只有一个元素的时候，如何决策。

直接考虑最极限的情况，只有两个栈有一个元素，其他的都被放满了，因为刚刚我们保证过的性质，一定不会出现其他栈的底部元素被先加入，所以一定是加入一个新的元素，这时我们只需要找到两栈当中，后被消去的那个元素对应的栈放进去即可。

这里我考场脑子有点晕，拿了个对顶堆维护只有一个元素的栈，实际上可以只比较任意两个数就行了，可以做到线性。

那么时间复杂度为线性，可以通过。

思考大概花了我三十分钟，期间还尝试去观察了大样例的构造办法，发现不如直接想，于是就想完了。

最后大概用了两个小时才写和调完，代码写了 7kb，分类讨论太多了。（后来发现只是我写得有点复杂）

t3

此时考试还剩一个半小时，我获得了 200pts ，但是我感觉这个 t2 区分度很够了，所以后面两题我只要稳扎稳打写完暴力应该就上队线了。

毫不犹豫赶快开 t3 ，看完题面大概就知道需要缩点，然后看看部分分是什么，发现 n^2 分就挺多的，于是秒了一个直接 dp 的做法。

大概就是直接 dp[x][0/1] 表示 x 子树内是否选取点的方案数量。

这时我突然发现，这个 dp 的过程不就是线性的吗？难道这个 t3 就这样做完了？？？

此时我非常激动，因为这时我以为，标准省队选手应该都已经先我一步过了 t2 并且开始写这道题了，正巧斜对角这时候传来非常激烈的敲击键盘的声音，我擅自揣测是 wfy 也发现这是简单题在狂写了，于是我直接立马对着自己的思路就开写，大概 30min 就写完了。

可是我这次并没有直接过大样例，于是先强迫自己冷静，不要去想着 t4 的暴力了，这个时候我也根本不知道 t3 还能怎么 n^2 的简单写法，我只会目前这个线性做法，不成功则成仁，写出来 t3 我就一定上队线了。

中间经历了很多调试，包括对着大样例一个几千的数据调试，然后一步一步输出查看错误，最后大胆决定直接静态调试，整理思路。

这期间我脑子很混乱，想了很多不对的调试思路，比如中间有一会一直以为边双会像 SCC 那样有重边要用并查集来判，后来发现如果有甚至会对答案有影响，用 map 记录重边又可能会超时，最后还手写了个 pair 的哈希表（看我代码里面好多冗余的东西）。

但是我这样一系列改了过后还是不对，甚至输出都没变过，我就意识到一定是不会有重边的问题的，是别的地方的错误！

终于，在最后十分钟，我发现我的 dp 状态是没有包括到不选 x 但是子树内被选的点的 lca 是 x 的情况。

这时我的心脏开始狂跳不止，难道我真的可以上队线了？甚至是 A 队线？

但是我现在必须立刻强制自己冷静下来，稍微思考了一下就大概知道怎么改了，就是记录当前子树选了多少个，然后把这些东西一起传上去即可。

监考员的提示声在我耳边不断响起，可我此时满脑子里都只有最后的一个想法：调出来。

最后两分钟，当我的手最后一次颤抖地摁下 F11 ，屏幕上，那个期望了无数次的数字终于出现在眼前，我激动得大脑都放空了。然后立刻保存代码，但是我检查 noip 文件夹发现我之前保存的代码的位置不对！只有一分钟了，电脑右下角显示的秒数每一跳都让我心急如焚。

另存为，保存，另存为，保存，另存为，保存！但是这时，dev卡住了，我的大脑一片空白，然后立刻举手示意监考员，并向他描述了情况，他尝试了帮我关掉 dev ，但是并没有起效，然后又叫来另一个监考员，这时已经一点钟了。他问我代码保存好没有，我告诉他：我就是不知道到底保存好没有才举手示意（因为是在结束前卡住了，这个时候至少有 30s），然后他们调出了任务管理器就帮我关掉了 dev 。我请求能否让我再确认一遍代码是否保存成功，他们就告诉我不可以了...我心底里感到莫大的失落，万一我真的没交上去该怎么办？我是不是就此退役了呢？

但是一切已经结束了，我并不敢冒着被扣上“作弊”的帽子的风险坚持自己查看，我只能收拾好东西，最后一个离开了考场。

day1尾声

出来我问了 wfy ，问他有没有 300 ，他说悬，我大概对难度判断有了点把握，自己感觉这次的队线应该是在 250-300 左右，因为 t3 真的简单得太出人意料了...

然后出来问问同学，好像都说不会 t2 ，t3 大家好像因为不太会边双也没做出来，但是好像 t4 的暴力分 52 是非常好拿的。

最后父母也来绵阳了，我大概说了一下情况和可能会寄的 t3 就没继续讨论这个，回酒店收东西准备吃个饭回家了。

然后下午在回家车上收到了代码（感谢多头！），一看 t3 真的没交上去，当时的想法就是：退役了。

回家后把 t3 改的那个地方凭记忆加了上去，果然在各处民间数据都过了...

后来发现可能队线并不高？以为自己还有点希望。

但是晚上 llzer 给我测的 t2 也有点问题？我有点麻了，但是太累了，不想再看 t2 我那冗长的代码，吃了晚饭上了会 o 就睡觉了。

day2

早上就起来看 t2 挂哪了，发现是该用无序集合存的编号我用了数组来存，真是太可笑了。。（具体错误见上文）

然后调整了一下心态，决定等正式成绩出了再决定退役的事情吧...

day3

如你所见，在休息和写会游记...

早上起来看 xtl 发现自己居然有 rk26 ？如果能拿到 300 都 sc\ rk2 了？？

结果发现是没测 t4 的榜，白高兴一场，下午更新了是 rk33 ，但是 300 还是 sc\ rk2，这下真输麻了。

未完待续。

（退役记嘛，等我退役了再说吧。）

小小的总结(11.27 day2 ver.建议不看)

（只是简单描述一下情况）

大概是寄了，300\to150 （可能？），明明都切 t2 了，不挂完全就是赢麻了，没想到是以这样戏剧性的方式结束了。

考场大概是秒了 t1 ，然后想了会 t2 ，会了之后写了很久（足足7k代码），最后本来打算打暴力了结果发现自己秒了 t3，调试到了最后两分钟成功过了大样例... （什么是大心脏啊/kx）

考场预估：100+100+100+0=300 。

民间数据：100+[50,55]+[15,20]+0=[165,175] 。

这次 t1和t3都是白给的，感觉目标省队的话至少得会，然后 t4 的 52 也是在白给，所以标准一点的暴力分应该是 100+15+100+52=267，预估队线在 250 左右。

所以只能指望官方数据水一点让我没改过的之前 t3 的代码多过点和 t2 自己傻逼的点少挂点...

这次其实在考场上已经做得非常好了，最后两分钟极限调出 t3 更是让我激动不已。

可惜，因为一些代码保存的问题，还有我不知道为什么场内的 dev 能在最后那么关键的时候卡住了，求助了监考员来把我 dev 关了过后就不让我检查交的是否正确了（结果是并没有交上我最后调出来的代码，民间数据获得了 100pts）...谢谢你们，让我失去了随手上队线的资格/wx。

结果自然是白丢了 t3 的整整 100 白给分，太搞笑了。

同样的，t2 的挂分项也特别简单，明明该用无序集合来存的数据我却不知道在想什么用了数组来存，所以其实还可以挂的更多。

现在剩下的只有等待奇迹，还有考虑以后的 whk 学习。

更具体的游记会补的，退役记也会补的...