GXOI 2020——走在告别路上

回首一望，我走在 OI 的道路上将有四年；而我的整个 OI 生涯，就将在这四年走满之时落幕。2016, 2017, 2018, 2019, 2020，这一个个数字，都承载着无数的记忆。有懵懂时输出 $0$ 拿分的喜悦，有被“小凯的疑惑”困住的遗憾，有省选时由“不可能”到进入省队的惊喜，有在桂电的班车上感叹的青春美好，有在广州开往南宁的列车上见证的学长的告别。四年里，OI 一直陪伴着我的成长。 如今，我第二次参加省选，也是最后一次参加省选。看着将要在两个月内结束的 OI 生涯，我就更想把这次省选记录下来，留作一个宝贵的留念吧。 ### Day $-7$ 结束了学校的月考，考了一个大体满意的成绩，也算是从奇怪的角度增强了一些信心吧。就这样来到机房，开启了停课时光。 在机房停课的时间总是很快乐，与队友讨论奇妙的问题，增长着各个方面的知识，也能看到各种各样的景色。这一周主要以复习为主，不再学习过多的新内容，于是我欢乐地刷起了 [Yosupo’s Library Checker](https://judge.yosupo.jp/)，并刷到了（目前的）$33$ 名。 停课期间还总结了一些代码背诵指南， 比如 [后缀数组](https://www.luogu.com.cn/blog/Sweetlemon/bucket-radix-suffix-sort)、[多项式全家桶（的很少一部分）](https://www.luogu.com.cn/blog/Sweetlemon/how-to-recite-polynomial-algorithm)，以后也许我会大力实践“编故事背代码”的方法吧（笑）。 离考试还有三四天的时候觉得自己可能有点感冒，仔细思考，认识到了问题的严重性——如果体温不达标，我的 OI 生涯就将在省选前终结！怀着些许恐惧，我采取了能够采取的一切措施：在机房多穿适量的衣物，在宿舍多加适量的被子，疯狂喝水（多 喝 热 水），最后总算是将感冒治愈了。 ### Day $-2$ 搬运机子把考场布置好，我们当天就在考场进行模拟~~和压力测试~~。由于我调试键盘时一不小心按到了键盘上的 POWER 键，机子瞬间关机，从而发现了这种键盘的严重隐患，当天下午我们将全考场的键盘都更换了。换上的键盘回馈更足，打字更舒服。顺便吐槽我原来的键盘，那个键盘的 Z 键坏掉了，然而直到我写到 T3 打不出 `size` 的时候才发现这个键坏了，之前只是奇怪为什么不能撤销（bushi ### Day $-1$ 早上重新适应新键盘，又做了一道题。下午是试机时间，见到了来自其他学校的同学。发现了许多使用 vim 或 emacs 的大佬，而我就只会使用 gedit……嘛，也没有只会用 gedit，遇到大样例还是会用 vim 打开的；别说，`hjkl`, `233G`, `ggVG`, `w` 这些基础我还是会的（逃 ### Day $1$ 早上本想睡到 7:15，可生物钟阻止我继续睡下去，7:00 就醒了，不知道有没有打扰宿舍的同学（ 吃一碗充满酸笋的粉，戴好口罩前往科艺楼。准备好了~~开宴会的~~食品，看了一下 Tarjan，就进了考场。 坐等了约半个小时，在桌子上打了打 [Euphoria](https://zh.moegirl.org/Euphoria(%E6%AD%8C%E6%9B%B2)) 的节奏，等着比赛开场。看到 [JasonL](https://www.luogu.com.cn/user/137422) 和 [hkr04](https://www.luogu.com.cn/user/111528) 没有来，还有些担心，好在后来都~~掐点~~到了。 终于开始了。我看了一眼题目，T1 一看上去就比较简单，T2 情景太简单了一定是原题（搞不好是模板题），T3 看上去不知道怎么做。这么看来，这天的题目难度堪忧啊。 #### [T1](https://www.luogu.com.cn/problem/P6625) 这题一看就可以 $\mathrm{O}(n)$ 解决，于是就往 dp 的方向想了想，最后优化成了贪心（bushi 稍微写了写，看着挺合理的，就没有对拍。大约 30 min。 #### [T2](https://www.luogu.com.cn/problem/P6626) [关于此题题目名](https://www.luogu.com.cn/discuss/show/233857)，论洛谷和 LOJ 上的题目名称是如何在 5 分钟内双双得到更正的，论如何在洛谷上解决 LOJ 问题。 看到这是道多组数据的题目，我立即在代码里写了一段话提醒自己—— ```cpp /* !IMPORTANT If there are multiple groups of test data and you forget to do some cleaning, you will get a zero as well as two rows of tears! */ ``` 简而言之，[“多测不清空，爆零两行泪”](https://www.luogu.com.cn/problem/P5289)。 这么简单的题目情景，肯定有原题。想了想启发式合并、树链剖分等相对好写的算法，都没有结果。有想到用点分治，但一直觉得难写，而且总以为它要 $\log^2n$，就搁置了。最后打了暴力 + $k\le 20$ 的部分，就先去写 T3。 后来写完 T3 回来看这题，大约还有 1h 这样吧。打开菠萝包（挺干的，和着牛奶吃下去了），边吃边认真考虑了点分治，发现可做而且复杂度只有 $\mathrm{O}(n\log n)$，就下定决心要写点分治。为了克服心中的恐惧，我反复心理暗示，区区点分治，还有 1h，有什么写不出来的？于是不管代码长度，只是写。写完只调了一下就过了样例，可本地测时结果不甚理想，最后掺着数据分治交上去了。 #### [T3](https://www.luogu.com.cn/problem/P6619) 仔细思考题目，发现了这题的好几个性质，就有了一些信心。 看到 $2\times 10^6$ 这恐怖的数据范围，一度犹豫正解的复杂度到底是多少。最后用树状数组的 `find_kth` 操作糊出来了一个 $\mathrm{O}(n\log n)$ 且常数可能不那么大的做法，作差找零点那个处理也算是数学导数题给的启示吧。写数据生成器的时候十分烦躁，最后测时，极限数据运行时间达到了 $7\mathrm{s}$，也只能靠信仰了。顺便吐槽一下，这题输出比输入还大，都是二三十 MB 的大小…… 写完这个就回去写 T2 了。 ### Day $2$ Day 1 晚上回了学校，发现机房电脑竟没有网络，玩了玩扫雷便回去休息了。 早上起来仍是吃了一碗粉。第二天，大家进场的速度就比较慢了，所以等的时间就没有昨天这么长。 今天一下子发了三张草稿纸，难道是要强行消耗完带来的打印纸吗？~~那么我们小机房每年的打印纸来源就没了~~ 拿到题仍然先扫一遍，把对题目的第一印象写到了 $\mathtt{sol.txt}$ 里面。T1 感觉离散化会很毒瘤，T2 数据范围疯狂暗示是状压 dp，T3 仍然不知道怎么做。 #### [T1](https://www.luogu.com.cn/problem/P6627) 考虑了一下如何离散化，首先是把不等型条件拆成两个区间，这样所有的条件就都是区间了。当时我认为，只要涵盖所有的区间端点，再加上 $0$ 一点，就一定可以包含答案。接下来如何确定每个点的值呢？区间修改、单点查询，先修改再查询，当然是差分数组啦。 可惜“只需要涵盖区间端点”的结论是错误的，因为“异或”不一定对答案有好处，我们也许需要“避开”某个异或，因此还要提供“避开”某一个优惠条件的方法，简而言之就是往区间未覆盖的地方扩展点来离散化。这个问题是可以用对拍发现的，可当时我认为这个东西很优美，就没有怀疑它的正确性，因此今后只要有时间，就要优先对拍预期得分较高的题目。 #### [T2](https://www.luogu.com.cn/problem/P6622) 首先可以发现大概是状压 dp。先把边数压到点对上（即记录 $i\to j$ 一共有多少次传递），再考虑每个点对的贡献。接着考虑“加入一个点时对答案的贡献”，发现贡献可以拆到 $i,j$ 两个端点上分别计算。经过仔细的推导，又发现可以运用各种诡异的 dp 预处理和优化技巧，把预处理和 dp 的计算量都调整到 $9\times 10^8$ 左右（并且还艰辛地压了空间）。 好不容易写出来了，居然过不了样例；调试了半天，最后发现是 $f[S]$ 转移到 $f[S']$ 时，计算 $f[S']$ 竟没有加上 $f[S]$（只加了转移那部分增加的贡献），真是有些诡异；所以应该如何调整心态以便静态调试查出问题呢…… 改好之后又是日常的本地超时，这我也没办法了嘛。 #### [T3](https://www.luogu.com.cn/problem/P6628) 这道题看着真的没有什么思路，只好写一写状压 dp，预计是可以拿到 $m\le 15$ 的分数的（可不知为何写炸了）。写完暴力后一味地想发现性质，结果什么都没有发现，又赖着不肯走，坚持要写一个 $m>15$ 可用的暴力，最后证明是浪费了时间，不如去对拍 T1 或者静态查状压 dp。因此考场上如果对某道题真的没有思路，就不要死磕，不如去做一些更有意义的事。 ### 总结 总的来说，这次的考场上发挥还是不错的，也积累了关于对拍的经验。 考完调整了一下心态，重新回归文化课的学习；同时也捡了一下定下的 todo list，争取在剩下的不到两个月里学到更多的东西，走好这最后一公里。 最后以 Euphoria 的歌词结尾吧。 > 啊，少年的我们 > > 如果热情的日子和约定也 > > 消逝的话 > > 变成过去的话 > > 就设法留下痕迹吧 > > —— Jin Euphoria ### 友链 以发布时间为序。 - 明年五象的希望 wzy dalao：[GXOI2020垫底记](https://www.luogu.com.cn/blog/GamerDiaosi/gxoi2020-dian-di-ji) - 特别能在代码里玩梗的友校女 OIer：[GXOI 2020 游记](https://yuwenzhou-sakana-chn.blog.luogu.org/gxoi-2020-you-ji) - 超强的高一 dalao JasonL：[GXOI 2020 省选游记](https://www.luogu.com.cn/blog/JasonL/gxoi-2020) - 超强的高二 dalao Alear：[GXOI 2020 游记](https://www.luogu.com.cn/blog/Alear/gxoi-2020-you-ji) 希望今年、明年，以及今后的每一年，都能看到大家共创 GXOI 的未来！