前言

实际上已经半 AFO 三个月了，再来参加这场比赛也没什么好说的，尽力而为吧，也无需过于在意。

这段时间洛谷上做题寥寥无几，只有偶尔会出一些题，比方说给学校高一集训出题和组题，或是给区里的竞赛（貌似是给初中生考的？）供题。

更多的还是回到 whk 上了。

初赛

初赛还是比较简单的，就不细讲了，补全代码都很好懂，不过阅读题有一篇只看出来树上背包，不知道合并的什么玩意儿，另外单选貌似也有选错的。

最后出分虽然是机房第一，但还是比我预想的八九十分要低一点点。另外这次高一学弟也晋级了三个，也有几个差了一点点，相比往年我们学校的情况感觉好多，但相比这届竞赛班人数又感觉有点少。

喜提一个市1=，虽然感觉作用不大。

复赛

总的来说，抛开题目不看，这次复赛是所有比赛中最舒服的一次。不管是比赛场地、设备、比赛系统、IDE、赛时安排之类的，都是体验最好的一次。

day -3

整理了一下官网给出的考试范围和对应的模版题。居然有网络流？而且复杂树和复杂图论里面也不知道有什么…数据结构也没说清楚。

这一天光整理题单去了，好像没做题。

day -2

敲了一些图论板子，只剩下欧拉回路和联通性相关的那些没敲了。

day -1

花了好多时间把三种联通分量和对应缩点、割点割边都重新复习和理解了一遍。也许我第一次学的时候没有理解清楚，一直有点模糊，这次终于区分清楚了。然后欧拉回路也重新理解了一遍。

发现这次重写模板题，又多了好几个优化代码减少码长的地方，学 OI 两年了技术也就这样，倒是压行和偷懒越来越会了。

网络流应该不考？不看了。数据结构还挺熟练的，不看了。字符串大纲说只考基础，不看了。

day 0

赛前

因为这天本来学校需要补高考假，所以是从学校出发。考点在广州的广技师，从深圳过去需要大概两个小时。

六点起床，大概 6:20 左右一边吃着面包一边赶到了门口。高一有两个学弟没在线请假，校门口刷脸没有开门权限，走人工通道要打电话跟教练确认，搞了有一会。高二另一位同学（之前一起打 THUPC 和省选的）不知道是起晚了还是怎么，来的有点晚，打电话催了一会。六点半多一点出发了。

洛谷运势大凶。在车上看一些骗分和防挂分的博客。

到了考场之后以为不用着急进去，上个厕所回来发现人都进去了，有人提醒我们这场比赛需要签到和登录？于是赶紧进考场了。

进来发现比赛场地环境好舒服，签完到之后找到自己座位坐下，发现比赛设备居然是笔记本电脑，而且提供的 IDE 除了常见的 devC 和 VSCode 以外居然还有小熊猫！震惊。听说要登录，不知所措，遂举手询问工作人员，原来要打开桌面某个程序登录。发现居然是 java 写的，会定时发卷和自动同步文件，我去这也太牛了。

发现周围的同学可以动电脑，遂启动小熊猫开始配置，调了一下编译选项和缺省模版之类的。在桌面上发现了样例文件夹，打开来看了一眼，发现输入都好少，而且看起来没有图论和数据结构题，啊？

看大屏幕系统终端发现有同学已经同步了四题的 cpp，于是我也先把样例复制到考试文件夹，然后把四题的源代码文件和文操先弄好了。

赛时

开考前一分钟发现已经发卷了，遂打开看题面。

啊？七选五…我开的是英语卷子？

看了一会发现这不就是错排列 plus，应该可以一样的去推，遂推柿子。桌面空间有点小，草稿纸写起来不舒服，以及只给了一个小样例，离谱。

按错排列的思路推了半天发现行不通，因为递推到 $n+1$ 的时候不知道对应正确答案是否被前面选过，好像加一个状态也不行，加限制也不太行。

没什么思路，跑去看一眼其他题…发现都好难的样子，然后火速回来。推了一个 $O(n^2)$ 的式子，感觉没问题，把里面的组合数展开然后消了一下阶乘，发现如果换一个主元的话就可以把分母提出来，这样只需要算一次逆元，遂推推推。

1h 过去，推到后面想出了一个基于错排列的 $O(n)$ 式子，刚写一部分就发现不对，然后再回去看原来的式子发现也不对。遂难绷，1.5h 打完暴力，测了几个错排列的样例没问题就过了。

开 B，一开始感觉要拆位后面发现不太对。想了一会之后认定操作二是没用的，因为或运算只会把 $0$ 变成 $1$，而与运算需要的是 $0$，异或运算需要的是相同。首先显然可以异或自己，也可以把数字的任意 $0$ 取出变成 $1$ 其他变成 $0$，这样一做与运算也可以一次性变成零。然后想错了，误以为先异或任意数字再与上同一个数字一定会清零，所以发现只需要找到每个函数的最小值或零点去尝试即可。所以答案只可能是 $\min{x,f_i(x),k,f_i(k),2min,2f_i(min)}$，读入每个函数的时候检验一下就好了。

后来发现不对，先异或再与也不一定会变成零。但是发现答案不超过 $2$，因为要么直接与 $1$ 可以变成 $0$，要么先异或再与也可以变成 $0$，因此答案最大为 $2$，所以只需要考虑一下什么情况可能会取到更小的答案就好了。

如果函数 $\Delta\ge0$，那么最小值才有可能可以取到 $0$，否则由于 $a,b,c$ 都是整数，所以该函数的每个整数坐标点都是经过格点的，那么就最低会取到 $1$。

所以这里继续猜测，答案只会从取最小值和取 $1$ 中选？于是火速开写，过掉了所有样例，但是没有任何证明，也没有对拍。但是只有十多分钟了，后面的暴力有些紧张。

火速看完 C 然后开码暴力，谢谢你 next permutation。

最后五分钟开 D，读题好像是 KMP，坏了，暴力都写不出来。虽然可以暴力真的拼好之后用 find 计数，不过来不及了，遂输出样例跑路。

最后一分钟检查了一下四份代码，遗憾退场。

赛后

发现大家都考的挺炸裂，不过高一成绩都比我想的要好吗，感觉他们其实剩下打满暴力的话分应该比我高。

赛后在校门口找了一家沙县小吃吃了午饭，然后想了一下发现 D 是不是跑两次 KMP 就可以了。然而给的考试范围里面没提会有字符串高级算法，所以没复习 KMP，虽然原理很理解，但细节不太熟悉，感觉就算时间充裕也没办法裸写出来，就是有点可惜暴力分，无所谓了。

ABC 出场后也没有思路，C 的话具体应该要看给的那个函数来贪心或者 dp？

洛谷的大凶说的确实没错，可恶。

后日谈

• 2024/06/16：哈哈。
• 2024/07/07：120 分，喜提 2=。

附录

参考文献

版权信息

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