前言

第二次省选了，这次的心态又与去年有所不同。

一来是因为，NOIP 成绩并不优秀，不抱希望，也就没有压力。二来是因为，很久没有碰 OI 了，自 THUPC 后还是会来机房，但是来机房基本只是找机会跟女朋友聊天和看着和她的聊天记录发呆，顺便补补文化课。

毕竟实力就在这个地方了。如果我 NOIP 后继续停课到现在，进队的概率或许还能看得见，但我最好最好也就是打个 Ag 潦草收场，然后去跟本来就能裸分的大佬抢清北羟基。什么啊。

去年参加省选时也没多大希望，高一嘛来试试水，本来想着还是高二冲队，谁知道 NOIP 后半场一败涂地直接退役。

但不管怎么说，这次比赛也宣告了我本赛季的结束，姑且是写了游记。下一次重新面对 OI，应该是年底了，届时是真的退役赛了。

另外，其实去年参加时也写了游记，但并未公开，本次一并附在附录中。

游记

day -4~-1

考前一周才想起来三月初要打省选。

谁爱打谁打。

什么，还要占我一个周末？去你的吧。

什么，可以提前一天回家？我马上来。

本来打算 day0 早上回家，但是 day-1 是我可爱的女朋友的生日，所以特意提前到 day-1 晚上就回去了，码了好久的字然后定时发到空间了嘿嘿。

当然这一周也不是什么事都没干。day-4 vp 了 YDOI R1，打了 220 跑路了。day-3 vp 了 HBOI day1，赛时 T1 死活不知道哪里错了，只得了 50 pts，而且对的还是后半部分的点，诧异，day-1 的时候发现是最后扫一遍统计答案的时候忘记判 inf 了，改了之后一发过掉。应该算签到成功了吧。

day 0

上午没学 OI，但是和她断断续续地聊了一些。

中午吃完饭没多久就出发去考点学校了，去年在广州，有些远；今年在东莞，近了许多。先去了酒店放了行李，楼层很高，拍了很多照片。然后去了考点学校报道，领了牌子和赠品。今年怎么有赠品？去年怎么没有？去的时候考点学校的学生还在上课，哈哈。

试机的时候打了个不带懒标记的线段树，测了小数据一次过了，非常好。

之后回酒店点了晚餐，之后开始打模版手速赛。十三道模版题，前十道一路打过去基本都是一次过，最后三道是三种联通分量，忘干净了，边双点双强联通的代码全记混了，打崩溃了，遂跑路。

最后成功比室友多打了一倍的模板，拿下手速赛第一名。赛后看了以前的边双代码，把边双改出来了。点双和强联通一点都不想打，跑路。

本来想着姑且尊重一下比赛要早点睡的，没忍住，和她聊到了一点多。

day 1

早上起来还算精神。

吃了早餐，提前大概半小时赶到了考点学校。打不到车，最后加了钱才打到的。

开考提前三分钟给了解压密码，先看了数据点只看得出来有一题图论。后面发现 pdf 没密码可以直接打开，火速看题。

T1 读题：我题目背景呢？怎么全是公式？好不容易读明白题，想了一会感觉好复杂，后面套回题目背景上之后好理解多了，有了一些头绪。

毫无疑问，先翻转坐标系把目标位置整到第一象限，然后接下来大力讨论，然后写着写着发现讨论不明白。

注意到风吹和移动的顺序不重要，以及具体行动路线也不重要，在某些情况下只关心吹完风之后的位置到目标位置的曼哈顿距离，但存在特殊情况。

自然而然想到，先计算一整轮风吹下来后的情况，枚举最后一次吹风，再讨论出前面轮数，然后总天数取最小值即是答案。

对于一整轮风的情况，贪心的尽可能往目标点走，所以将所有向负方向吹的风尽可能抵消，得到了一轮下来的位移以及可以自由安排的移动距离，接下来只需要枚举后讨论。

写的时候发现讨论不出来，但可以用来 check，遂退一步，枚举后二分出总轮数。

过掉小样例，然后在第二个样例发现寄了；修修改改过掉了第二个样例，然后在大样例发现假了。遂开摆。好想她。

T2 有一些思路，感觉这个博弈是假的，二进制拆位去贪心就好了。但发现这个定向加强很不好做，遂开摆，只打了最低一档暴力和做 $m=0$ 的特殊性质分，特殊性质写了半天 01 Trie 过不去，最后全都上了暴力。好想她。

T3 不可以，总司令。检查了所有代码。好想她。

结束了，四个半小时纯坐牢。出校门的时候风很大，衣服没帽子，耳朵冻没知觉了，打到了车但是要十分钟才到，冷死我了。

缓过来之后突然发现她不对劲，还以为在学校出事了，吓死我了。终于回到酒店，本来想出去吃的，被风冻怕了不敢出门，还好酒店里全天开着暖气，这才活过来。

下午摊着了，迷迷糊糊的和她聊天，等消息的时候好像睡着了一会。中间点了个肠粉当晚餐，之后和她聊了五个多小时，这个周末最美好的一段时间。

day 2

早上六点多起来了一次，发现室友通宵了。又躺回去，好像没睡着，一直到了七点才起床。

和她聊天的中途赶到了考场，提前十五分钟进了考场等开考。

我一点都不想比赛，为什么要比这么久，好想继续和她说话。

开题。

T1 这个博弈有点意思，很显然有一个最基本的贪心。最开始的思路是，从确保 $1$ 不被选开始，尽可能让 $2,3,\cdots$ 也选不上，通过这个找到要唤醒的结点，最后搜一遍出答案。

小样例过掉，第二个样例就寄了。

好想她，我为什么在这里做题。

突然注意到题目一个要求是必须走完所有子树才能回到根节点，所以发现前面思路单纯按数字大小来贪是不对的，应该按当前能走到的最小值来贪。

想到思路了，大改特改。有点分治的想法在里面，维护了结点子树中能够到达的最小结点，然后 solve 会在当前子树中进行贪心，然后会根据决策，进入到不同的子树中去 solve。

写完之后我很满意，debug 了流程很符合我的想法，简直神来之代码。结果还是一样，只过掉了第一个样例。

好想她，我不想做题了。她今天放假，我想找她说话。

手模了第三个样例中的一个数据就发现，问题出在选取要唤醒的结点的地方。试着换了别的贪心方法也过不去，估计这个地方不是贪心而是某种规划。。寄！

我在这里比赛不如拿这个时间和她聊天多好。

最后改成了自己认为正确率比较高的决策方法后就润去写剩下两题暴力了。

T2 发现是我最不擅长的概率与期望之类的题目，虽然我觉得这个概率好像是假的。不管怎么样，我发现当 $n+k\le 10$ 的时候还是可以用 next_permutation 水过去的，于是火速开写。

这暴力都不简单。check 是按照约束对整块碎片建 DAG，然后跑拓扑排序来 check。然后写了个 gcd 和 qpow 完成了有理数取模。中间还记错逆元的次数了，一直写成了 $mod-1$ 次方，我说怎么 qpow 跑出来一直是 $1$。

最后是过掉了范围内的样例，剩下的部分就不可以总司令了，我相信总是会出现一个的（

好想她，为什么不能打完暴力提前交卷。

T3 逆天题面，给我看傻了。后半部分题目不是很懂，索性 puts("1") 了。

还剩下十几分钟，好无聊，好想她。

最后一次完全检查了代码没有出现去年的错误，于是开始玩起了电脑。启动了虚拟机看看，发现 vs code 不会配置，于是在终端用 gcc 编译，结果编译出来的程序无法运行。退出来研究了一下别的 ide。

终于结束了，什么都结束了。耶，终于可以和她说话啦。

比完赛马上就回去吃午饭，吃完之后收拾了东西，酒店退了房，然后就离开东莞回家了。路上因为给她发消息看手机，晕车很严重，差点没撑住。到家之后继续聊天，真好。

后日谈

Day1 蓝黑黑，Day2 紫黑黑，真有你的省选联考。

没想到今年也签到失败了，太菜了，day0 打的模板一个没考到，不过无所谓。感觉最重要的是和她聊了好多，但我觉得还不够，要是假期就好了。

不过接下来还是专心 whk，恋爱脑也得收收。老婆和学校哪个重要我还是掂的清的，不能因为学习耽搁了恋爱（？）。

附录

省选联考 2023 游寄

注：以下是去年写的，格式不好，也没用 Latex。而且当时也不敢提到女朋友的事，就单纯写了游记。现在看着蛮难受的，但总之就是一起放出来了。

Day -1

虽然初三暑假才开始学的算法，但我对自己还是挺有信心的，基本上算法我是不会写错的（但是题目会不会做就是另一码事了），所以一上午在学校机房里就只是简单的看了下各种数据结构的代码后就继续学新东西。看了b站上关于计算几何的一些视频，向量、凸包、旋转卡壳、最近点对、随机增量之类的，除了随机增量以外基本都很简单很好理解。下午就坐了两个半钟的车到省会，先去酒店放好行李然后就去考点了。

结果走错门了，门口一大群家长，然而当时我还没发现，因为看到了好几个学生，估计他们也是打车打错了。好在当时周五下午，等了一会正好考点学校放学，学校大门开了，我就随着那些家长一起进去了。虽然因为走错门所以完全看不懂地图，不过看路标还是找到了报到的地方。因为弱校校队只有我有省选资格，所以教练也没跟着来，于是报到处的老师直接把整个文件袋都给我了，里面除了我的胸牌还有教练的胸牌和文件之类的，打算回学校后拿给他。听到对其他学生说有饭票，考完可以在考点学校的食堂吃，发现自己没有，或许是需要学校提前订吧，感到有些悲哀。

然后就回酒店了，复习主要是看了一下比较容易混淆的一群Tarjan算法还有突然想不起来和spfa有啥差别的dijkstra。然后就学了一下新的东西，比如爬山和模拟退火，还有一些乱搞（骗分但不完全骗分）。

Day 1

昨晚没睡好，悲。但还好比较精神，可能我本来在学校就天天凌晨睡，所以没太在意。早上吃完早餐就直接去考点了，结果走到昨天那个门这时候才发现走错了，不过时间很充裕，后面又坐车坐到了正确的门。在考场门口又看了下昨晚的模拟退火，总感觉能用上。进去后就看注意事项然后等开考，旁边的哥们在趴下休息，我由于第一次参加省选，格外的精神。想着D1能不能切一题暴俩题拿个200。输完神奇的压缩包密码和pdf密码后，一看目录感觉T3名字眼熟，多半是图论。

T1看完之后有点不是很明白，就看了看T2，一眼DCC，但是对于是边双还是点双有点不确定，但是能确定最后缩完应该是棵树。一看对大数取模就知道这题凉了，因为我对于这种树上dp+大方案+容斥很不会，虽然前不久才做过一道，于是就赶紧回T1了。第一眼觉得跟差分有关，但是试了试没推出来结论，所以最后选了线段树维护并查集。写+调一直到了十一点，不过由于已经放弃T2了，所以压力不是很大。最后大样例跑的飞快，写出来的那一刻还是挺高兴的。之后T2再看一眼发现还是不会于是赶紧跳T3，想着剩下差不多两个小时打个暴力四十分，D1就算圆满收官。一看题目，发现挺像之前做过的一道模拟费用流，但是又感觉很不一样。题目看到一半的时候想到刚学的模拟退火，感觉很能做，每次随机让某位员工往下走，结果往后一看发现居然是动态的，心里偷偷竖中指。于是只好敲暴力，结果发现数组开不了那么大，无奈只能放弃66666的点，最后小样例跑的飞快，大样例直接爆数组RE，D1到此结束。

中午吃过饭后就一直待在酒店里看电脑，翻了翻wiki感觉没啥想学的，会的懒得看，不会的看不懂，于是就一直在洛谷讨论区里翻来翻去看大家“关于省选”。然后发现了好多和自己做法一样的，发现T1正解居然只是道贪心，估计我最近数据结构写多了，后来发现确实有差分的做法但很容易挂。然后下午就出代码了，发现我竟然手误给几个没有返回值的方法写了返回类型，寄，T1爆零了估计。没有拿noilinux虚拟机编译一次，不然估计不会有这个问题，确实可惜，但我确实怎么也想不到居然我真的会写出这种低级错误，还是在考场上，幸好我本来就是来试试水，没打算冲队，压力没那么大。

晚上突然在b站刷到了用DQN训练只狼AI的视频，点进去就出不来了。估计因为我学AI的时间是我学OI的时间的好几倍吧，我感觉炼丹才更像是我的主业，OI只是感兴趣？不过前几年就在书的尾页中看到过DQN的介绍，对这一种直接输入屏幕图像的训练方式特别感兴趣，当时还跟朋友说打算用DQN训练某个我很喜欢玩的小众游戏的AI，结果后面找了发现DQN的资料实在太少，而且网上实现的DQN玩的基本都是叫A什么的某种很古早的只有几百个像素的电子游戏，所以最后放弃了，结果这时候突然发现有大佬用DQN实现玩现代游戏，还开源了出了教程，真的很震惊，于是就乐呼呼的看到了晚上都没碰OI。

D1理想分，100+0+48，实际估分0+0+40左右（T1其实洛谷能编译而且打了90，但CCF测评机应该是会CE的），目前民间0+0+30左右。虽然我会说没爆零就是胜利，但实际上我估计会等官方数据出来以后在洛谷交一次T1，再把T1分加回去当做我的非官方成绩，毕竟不是很在意官方排名，只是想看看自己能打成啥样。

Day 2

昨晚睡得还不错，而且这次没走错门。来到考场门口听见有同学说D2肯定有计算几何，我心里偷偷一笑然后赶紧复习计算几何，顺便看了眼模拟退火，然而结果没有考到。进了考场以后隔壁的哥们又在趴下休息，我还是格外的精神。开考念密码，跟昨天的反过来，哈哈。

一看目录，看到game就感觉要来博弈论了，但是我不急，先看T1，发现好像又是大模拟博弈论，寄。当时感觉有点像启发式搜索，但又想不出来怎么写启发函数，考虑他一个网格地图感觉会跟曼哈顿距离有点联系，一看样例又看不懂了，我手推都不知道样例答案怎么来的，想不明白为什么另一颗被困住的红棋也会移动（还没看题解，不过此时写这篇游记的时候我突然有点想法，感觉黑方的启发函数应该是棋子到第一行的距离+两颗红方棋子到黑方的曼哈顿距离， 红方可能是棋子到黑方的曼哈顿距离的相反数？这么一来确实能解决我那个疑惑。显然不是IDA*，那么肯定是A*，并且可以用记忆化搜索标记一下状态来判平局，欸卧槽好像感觉突然会了）。看到输入里面有数据编号就感觉有好事，火速看数据范围，嘶……显然，像我这种考场上没想出的正解的蒟蒻，肯定是针对每一种数据去写暴力啦，看到特殊性质A送分，我就直接跳到T2去了，打算最后一小时再回来写T1。

看到T2，果然是博弈论（至少当时我是真的以为是博弈论）。一上来先输入的时候判断一下能不能满足B互不相同，然后提前计算一部分已经确定的答案然后剔除出去。那么就剩下最后一部分了，都是B有俩选择的，这时候就感觉有点像动态规划，但是想了半天，不会表示状态。好吧，老实暴力。然后，直接敲了个2^n的dfs+回溯和剪枝出答案，测第一个样例过了，测第二个发现直接就寄了。然后死活想不明白为什么暴力都写错了，一直调一直改，差不多到十点的时候我就怀疑是我关于A的部分有问题，于是就转而投靠刚学几天的模拟退火，在A的有的选的部分中随机一个换，然后再对B暴力求答案，结果调半天还是错（现在看来，感觉是前面那一段剔除确定部分的地方出了问题。。），直到快十二点，赶紧看眼T3看看能不能骗分，发现样例好多1而且只对第一问也有分，就写了个输出1和一个随机数，然后回到T1写暴力。发现暴力不会写，只有性质A比较稳，后面的BCD好像都有乱写的成分在的，然后D2到此结束，我的第一次省选也结束了。

看洛谷有大佬评价说D2确实很难，而且T2好像不是博弈论，性质A是匈牙利、C是费用流，但我考场上确实没看出来，而且暴力也写挂了，只能说D2不爆零就是胜利。

D2理想分30+5+0，实际估分20+0+0，目前民间10+0+1（T3没想到骗到了一分hhh）

总的来说，感觉确实很难，但又好像比我想象中的简单（或许是因为我压根不去考虑正解吧），这次官方分数估计就是40左右，至少对我来说已经很不错了，毕竟我才学了不到一年。不过D1T1果然还是略有点遗憾，不过当时忘记随机化了，所以不能指望官方数据全随机，可能确实会T几个点吧；D1T2这类题感觉很难但我可以掌握，再学一年的话应该能做出来，毕竟感觉这一类题都思路很明显，缩成树后dp+容斥嘛；D1T3，明年的我写的暴力估计会更优吧；D2T1出考场才想到思路，D2T2和T3相信明年的我能写出暴力。但值得庆幸的是，虽然我这次犯了很多问题，但我都找到了可以改进和避免的方法，至少下次应该不会错在同一个地方了，而我没有下下次，所以，这次确实攒下了很好的经验，值了！

最终官方成绩没到40，太难看就不说了，不过挺可惜的是后面把D1T1考场代码里手误写的的几个没有return的函数的返回值改成void之后官方数据AC了，然而实际上虽然没有CE和RE但是也没有分。

最后的最后，鼓励一下自己，顺便立个志向：数据删除（注：搬过来的时候这一段我还是删了，实际考的远达不到这个，就不放出来丢人了）

参考文献

我去年写的别的游记。

版权信息

本文原载于 reincarnatey.net，遵循 CC BY-NC-SA 4.0 协议，复制请保留原文出处。