Sweetlemon 的异世界

GXOI 2020——走在告别路上

回首一望，我走在 OI 的道路上将有四年；而我的整个 OI 生涯，就将在这四年走满之时落幕。2016, 2017, 2018, 2019, 2020，这一个个数字，都承载着无数的记忆。有懵懂时输出 00 拿分的喜悦，有被“小凯的疑惑”困住的遗憾，有省选时由“不可能”到进入省队的惊喜，有在桂电的班车上感叹的青春美好，有在广州开往南宁的列车上见证的学长的告别。四年里，OI 一直陪伴着我的成长。

如今，我第二次参加省选，也是最后一次参加省选。看着将要在两个月内结束的 OI 生涯，我就更想把这次省选记录下来，留作一个宝贵的留念吧。

Day −7-7

结束了学校的月考，考了一个大体满意的成绩，也算是从奇怪的角度增强了一些信心吧。就这样来到机房，开启了停课时光。

在机房停课的时间总是很快乐，与队友讨论奇妙的问题，增长着各个方面的知识，也能看到各种各样的景色。这一周主要以复习为主，不再学习过多的新内容，于是我欢乐地刷起了 Yosupo’s Library Checker，并刷到了（目前的）3333 名。

停课期间还总结了一些代码背诵指南， 比如 后缀数组、多项式全家桶（的很少一部分），以后也许我会大力实践“编故事背代码”的方法吧（笑）。

离考试还有三四天的时候觉得自己可能有点感冒，仔细思考，认识到了问题的严重性——如果体温不达标，我的 OI 生涯就将在省选前终结！怀着些许恐惧，我采取了能够采取的一切措施：在机房多穿适量的衣物，在宿舍多加适量的被子，疯狂喝水（多 喝 热 水），最后总算是将感冒治愈了。

Day −2-2

搬运机子把考场布置好，我们当天就在考场进行模拟和压力测试。由于我调试键盘时一不小心按到了键盘上的 POWER 键，机子瞬间关机，从而发现了这种键盘的严重隐患，当天下午我们将全考场的键盘都更换了。换上的键盘回馈更足，打字更舒服。顺便吐槽我原来的键盘，那个键盘的 Z 键坏掉了，然而直到我写到 T3 打不出 size 的时候才发现这个键坏了，之前只是奇怪为什么不能撤销（bushi

Day −1-1

早上重新适应新键盘，又做了一道题。下午是试机时间，见到了来自其他学校的同学。发现了许多使用 vim 或 emacs 的大佬，而我就只会使用 gedit……嘛，也没有只会用 gedit，遇到大样例还是会用 vim 打开的；别说，hjkl, 233G, ggVG, w 这些基础我还是会的（逃

Day 11

早上本想睡到 7:15，可生物钟阻止我继续睡下去，7:00 就醒了，不知道有没有打扰宿舍的同学（

吃一碗充满酸笋的粉，戴好口罩前往科艺楼。准备好了开宴会的食品，看了一下 Tarjan，就进了考场。

坐等了约半个小时，在桌子上打了打 Euphoria 的节奏，等着比赛开场。看到 JasonL 和 hkr04 没有来，还有些担心，好在后来都掐点到了。

终于开始了。我看了一眼题目，T1 一看上去就比较简单，T2 情景太简单了一定是原题（搞不好是模板题），T3 看上去不知道怎么做。这么看来，这天的题目难度堪忧啊。

T1

这题一看就可以 O(n)\mathrm{O}(n) 解决，于是就往 dp 的方向想了想，最后优化成了贪心（bushi

稍微写了写，看着挺合理的，就没有对拍。大约 30 min。

T2

关于此题题目名，论洛谷和 LOJ 上的题目名称是如何在 5 分钟内双双得到更正的，论如何在洛谷上解决 LOJ 问题。

看到这是道多组数据的题目，我立即在代码里写了一段话提醒自己——

1
2
3
4
5
6
7
/*
!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!
*/

简而言之，“多测不清空，爆零两行泪”。

这么简单的题目情景，肯定有原题。想了想启发式合并、树链剖分等相对好写的算法，都没有结果。有想到用点分治，但一直觉得难写，而且总以为它要 log⁡2n\log^2n，就搁置了。最后打了暴力 + k≤20k\le 20 的部分，就先去写 T3。

后来写完 T3 回来看这题，大约还有 1h 这样吧。打开菠萝包（挺干的，和着牛奶吃下去了），边吃边认真考虑了点分治，发现可做而且复杂度只有 O(nlog⁡n)\mathrm{O}(n\log n)，就下定决心要写点分治。为了克服心中的恐惧，我反复心理暗示，区区点分治，还有 1h，有什么写不出来的？于是不管代码长度，只是写。写完只调了一下就过了样例，可本地测时结果不甚理想，最后掺着数据分治交上去了。

T3

仔细思考题目，发现了这题的好几个性质，就有了一些信心。

看到 2×1062\times 10^6 这恐怖的数据范围，一度犹豫正解的复杂度到底是多少。最后用树状数组的 find_kth 操作糊出来了一个 O(nlog⁡n)\mathrm{O}(n\log n) 且常数可能不那么大的做法，作差找零点那个处理也算是数学导数题给的启示吧。写数据生成器的时候十分烦躁，最后测时，极限数据运行时间达到了 7s7\mathrm{s}，也只能靠信仰了。顺便吐槽一下，这题输出比输入还大，都是二三十 MB 的大小……

写完这个就回去写 T2 了。

Day 22

Day 1 晚上回了学校，发现机房电脑竟没有网络，玩了玩扫雷便回去休息了。

早上起来仍是吃了一碗粉。第二天，大家进场的速度就比较慢了，所以等的时间就没有昨天这么长。

今天一下子发了三张草稿纸，难道是要强行消耗完带来的打印纸吗？那么我们小机房每年的打印纸来源就没了

拿到题仍然先扫一遍，把对题目的第一印象写到了 sol.txt\mathtt{sol.txt} 里面。T1 感觉离散化会很毒瘤，T2 数据范围疯狂暗示是状压 dp，T3 仍然不知道怎么做。

T1

考虑了一下如何离散化，首先是把不等型条件拆成两个区间，这样所有的条件就都是区间了。当时我认为，只要涵盖所有的区间端点，再加上 00 一点，就一定可以包含答案。接下来如何确定每个点的值呢？区间修改、单点查询，先修改再查询，当然是差分数组啦。

可惜“只需要涵盖区间端点”的结论是错误的，因为“异或”不一定对答案有好处，我们也许需要“避开”某个异或，因此还要提供“避开”某一个优惠条件的方法，简而言之就是往区间未覆盖的地方扩展点来离散化。这个问题是可以用对拍发现的，可当时我认为这个东西很优美，就没有怀疑它的正确性，因此今后只要有时间，就要优先对拍预期得分较高的题目。

T2

首先可以发现大概是状压 dp。先把边数压到点对上（即记录 i→ji\to j 一共有多少次传递），再考虑每个点对的贡献。接着考虑“加入一个点时对答案的贡献”，发现贡献可以拆到 i,ji,j 两个端点上分别计算。经过仔细的推导，又发现可以运用各种诡异的 dp 预处理和优化技巧，把预处理和 dp 的计算量都调整到 9×1089\times 10^8 左右（并且还艰辛地压了空间）。

好不容易写出来了，居然过不了样例；调试了半天，最后发现是 f[S]f[S] 转移到 f[S′]f[S'] 时，计算 f[S′]f[S'] 竟没有加上 f[S]f[S]（只加了转移那部分增加的贡献），真是有些诡异；所以应该如何调整心态以便静态调试查出问题呢……

改好之后又是日常的本地超时，这我也没办法了嘛。

T3

这道题看着真的没有什么思路，只好写一写状压 dp，预计是可以拿到 m≤15m\le 15 的分数的（可不知为何写炸了）。写完暴力后一味地想发现性质，结果什么都没有发现，又赖着不肯走，坚持要写一个 m>15m>15 可用的暴力，最后证明是浪费了时间，不如去对拍 T1 或者静态查状压 dp。因此考场上如果对某道题真的没有思路，就不要死磕，不如去做一些更有意义的事。

总结

总的来说，这次的考场上发挥还是不错的，也积累了关于对拍的经验。

考完调整了一下心态，重新回归文化课的学习；同时也捡了一下定下的 todo list，争取在剩下的不到两个月里学到更多的东西，走好这最后一公里。

最后以 Euphoria 的歌词结尾吧。

啊，少年的我们

如果热情的日子和约定也

消逝的话

变成过去的话

就设法留下痕迹吧

—— Jin Euphoria

友链

以发布时间为序。

希望今年、明年，以及今后的每一年，都能看到大家共创 GXOI 的未来！

本文永久链接是：https://sweetlemon39.github.io/GXOI-2020/

评论