Sweetlemon 的博客

Sweetlemon 的博客

GXOI 2020——走在告别路上

posted on 2020-06-26 21:20:30 | under 总结 |

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

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

Day $-7$

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

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

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

离考试还有三四天的时候觉得自己可能有点感冒,仔细思考,认识到了问题的严重性——如果体温不达标,我的 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 的节奏,等着比赛开场。看到 JasonLhkr04 没有来,还有些担心,好在后来都掐点到了。

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

T1

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

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

T2

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

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

/*
!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$,就搁置了。最后打了暴力 + $k\le 20$ 的部分,就先去写 T3。

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

T3

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

看到 $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

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

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

T2

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

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

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

T3

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

总结

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

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

最后以 Euphoria 的歌词结尾吧。

啊,少年的我们

如果热情的日子和约定也

消逝的话

变成过去的话

就设法留下痕迹吧

—— Jin Euphoria

友链

以发布时间为序。

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