【NOIp 2018】Day 1 & 2 / 考后总结

【NOIp 2018】Day 1 & 2 / 考后总结

首先,这篇文章的写作时间开始于 1:59 PM,11/10/2018,NOIP 2018 提高组比赛结束的两小时之后。

Day 1


考试前感冒了,考试的时候整个考场的人一直在听我打喷嚏,抱歉。如果和我同考场的同学考炸了,我的错。

题目好像是 8:29 就下发了,我迅速用 Chrome 打开题面 PDF,三道题完整地扫了一遍,都有一种彷佛从前遇见过的,莫名的熟悉感,但当时想不到究竟有没有看过原题。

于是就从第一道题开始吧。

首先想到的方法是每个高度分别处理出有多少联通块,最后的答案就是每个高度联通块个数之和。我用了一个 $pos$ 数组记录每个高度上一次出现的位置,然后每加入一个高度都要 $\Theta (d_i)$ 地更新一遍 $pos$ 数组,总的时间复杂度 $\Theta(\sum{d_i})$。写完以后测了大样例,跑了 $\text{483 ms}$,极限数据则是 $\text{703 ms}$。比赛时用的电脑是三代 i5,当时感觉凭 CCF 的老爷机跑这个复杂度似乎有点不太稳的样子,但是一下子也没想到其他更好的办法。多跑了几遍大数据,没写暴力,没拍就直接去看 T2 了。

T2 的设定让我很快联想到了去年的 小凯的疑惑,但内容本质上是不太相同的。我看题之后得出的第一个结论是,如果当前货币系统内有一种货币的面额能通过现有的其他几种面额组合得到,这种货币可以舍去。于是先给所有货币按面额从小到大排个序,筛一下即可,但是我并没有这样写。前两个星期在做正睿比赛的时候碰见了一道用砝码凑重量的题,当时我用 $bitset$ 维护每个值能否到达,(本质就是个背包),通过了那道题。对这道题,我发现可以用一样的方法。于是枚举 $a_i$ 被选择的次数,暴力更新 $bitset$ 就可以相当快地通过大样例,因为值域仅为 $25000$。后面自己造了极限数据,也顺利地通过了(但是我不会写本题暴力也没有对拍)。

码完前两题,看了下时间,发现才过去四十几分钟,这速度不太靠谱的样子。着凉的我又逢上新一波的腹部痉挛,于是打了个报告要出去一趟卫生间冷静一波,监考老师就陪着我出了考场,并且站在卫生间门口等着我出来,这是我参加 NOIP 这么多年最不愉快的如厕体验之一。

所以肚子疼的问题并没有解决,不太靠谱的感觉也没有消除,我就回到考场开始研究 T3。观察数据范围,发现所有的特判加起来有 80分,我就尝试逐一击破。最简单好写的就是 $m==1$ 的 20分,两遍 $DFS$ 求出最长链就是最后的答案。接下来是菊花图提供的另外 10分,问题在这里转变成:你有 $n-1$ 个数,每次选出一个或者一对数之和,求选出 $m$ 个值可能的最大最小值。

发现可以二分答案,贪心判断这个值可不可行。每次二分的 $mid$,更大的直接计入答案,更小的尝试大小配对,双指针扫一遍求出最终的答案。题目并没有提供相同性质的样例,我手造了几组小的,人工判断似乎没有问题。

菊花图搞定之后,$v == u-1$,即一条链的情况提供了额外的 25分。做法和菊花图大同小异,同样是二分答案,线性判断能否达成。这里同样没有官方样例,我也是手造几组人工判断。

最后的 25分,来自于这张图的一个性质,“每个点的度不大于 3”。显然,抛开根,这棵树就是一棵二叉树。但是我考试的时候并没有考虑二叉树,我思考的是如何在儿子数很少的情况进行树上 DP。发现对于每个以 $i$ 为根的子树,点 $i$ 到父亲这条边只会和至多一个儿子上的链相连。于是我们令 $f_i$ 代表一个端点为 $i$ 的最可行长链的长度,同样需要二分找出答案。对于每个 $i$ 的儿子 $v$,如果 $f_v\geq mid$,直接将这条链计入答案。否则,考虑将它和另一个儿子上的链相连成为一条新链,或者和 $i$ 相连,最后通向 $i$ 的父亲。这里我没找到什么简洁的写法,只能堆满 $if$ 语句,但是条理还是很清晰的。这个性质的官方样例我认为只有第一组,最大的第三组并不满足,因为我的程序在运行它的时候 RE,我检查发现 RE 的时候有一个点的儿子数量超过了 3,而我用来缓存儿子信息的数组只开了 3 位。

过了小样例,我就一本满足地开始检查了。

回到第一题,感觉这个运行速度还是有点慢,我考虑优化。发现每次更新 $pos$ 数组只会影响到下一个点,只要判断下一个点高度是否小于这个点即可,如果大于,超出地部分另外计算答案,时间复杂度就变成了线性。这个优化写完以后,我就没有改代码了,开始养老。

不过在最后即将交卷,我重新审查题面的时候,发现这次的评测机是 i7 – 8700k,原来今年报名费上涨,是 CCF 狠下心来升级了硬件啊。

看来 T1 不需要优化也行的样子。

带着最后的一点惊喜,我走出了考场。

Day 2


今天早上有国际马拉松比赛,从南昌大学医院到考场的路段全部被封锁了,只能步行去考场,好像是全考场最后一个进入的,刚刚登陆系统就下发题目了。

T1 名字是 Travel,一股来自 NOI 2018 的熟悉感觉。看完题目描述,感觉这道题非常地不可做,顿时有一点点小慌,继续往下拉看到数据范围。。。$n \leq 5000$,$m=n$ 或者 $m=n-1$,暴力可做啊。看完 T2 T3,决定先把 T1 解决掉。一开始用的是前向星存图,每次 $DFS$ 的时候都要记录所有儿子再排序,自己造了个菊花图的极限数据,瞬间爆炸了。冷静一下,决定用 $vector$ 存图,提前排好序,枚举断边重新 $DFS$ 的复杂度似乎就是稳定 $\Theta(nm)$ 了,但是菊花图的数据依然跑得很慢,$\text{700 ms}$,我也不知道有什么问题。反正 CCF 今年用 i7 – 8700k 评测,似乎不是很虚的样子,就去杠 T2。

T2 $n \leq 8$,似乎可以状压 DP。每次向后添加一列,转移只和上一列相关,简直是状压裸题,尽管 $\Theta(2^nm)$ 不是满分做法,但是 80分还是比较可观的。于是我愉快地写了预处理转移,滚动数组优化的 DP,一发过了 $n=2, \ m=2$ 的第一个样例,心满意足地开始测第二个样例,然后发现程序输出了 $144$,而不是样例里的 $112$。顿时五雷轰顶头晕目眩心情开始崩坏,但是当时的时间才 $9:26$,冷静下来我开始查错。我对自己的算法还是很自信的,因为字典序更小是有传递性的,对于次大的 $w$,路径的唯一区别就是一个 $2 \times 2$ 矩阵的左下角和右上角,没有其他的情况,只要判断这两个点的值就可以转移。我顺着这个思路打了个暴力,枚举每个位置的值,计算出来的答案依然是 $144$。

这个时候情绪还能稳定一波,于是我开始在草稿纸上画所有的可行情况。因为起点终点对答案没有影响,所以本质不同的方案只有 $36$ 种,还是可做的。我硬着头皮对着暴力分析了每种方案的可行性,然后感觉没有什么问题。。。这个时候心态就崩坏了,因为已经在这里浪费了极多的时间了,于是先把没调出来的程序放在一边,直接去看 T3 的部分分。

T3 还算良心,$\Theta(nm)$ 的算法给了 $11$ 个测试点。考场上我误以为这是 $55$ 分 ,愉快地写完以后就继续去看 T2(考完才知道一共有 $25$ 个点,只有 $44$ 分)。

T2 神奇的 $144$ 和 $112$ 依然极大地困扰着我,感觉这个思路有问题的我本来想枚举每条路径,后来发现似乎数据量太大不甚方便判断,就彻底放弃了 $80$ 分的算法。此时我觉得满足这个转移方程的应该只有 $n=2$ 的情况,尽管我不知道为什么,但是看数据范围 $n=2$ 给了 $50$ 分的好成绩,就觉得这个判断可能是靠谱的。我测试了 $n=2,m=3$ 的数据,输出是 $36$,又手动画了一下 $9$ 种本质不同的图(其实也没什么意义因为我一定没考虑周全),主观上认为没什么太大的问题。

这个时候已经 $11:30$ 了,距离考试结束还有半个小时。我一直认为 T2 是一道送分题,只是我忽略了什么条件导致看不懂样例,大家应该都 A 掉这题了,就十分慌张,开始构想退役以后是滚回去学生物竞赛,还是带着遗憾远离竞赛这一块是非之地,安安心心按照初中时的计划学习文化课,靠高考求得一所大学上。

在这样凉飕飕的慌乱中,我又打开了 T1 和 T3,反复测试样例,确保不会出锅。T1 极限数据的慢和 T3 大样例的水都让我十分心虚,但是已经没有时间进一步优化,或者手造样例多测几组了。在和昨天完全不一样的心境中,我结束了 NOIp 2018 提高组的全部测试。走出考场我才想起来,应该用 Guide 重新编译运行一下,防止出现半年前省选一样的惨案,但是为时已晚。

到楼下和大家会合,才发现昨天 T3 大样例二叉树的问题只是一场闹剧,而今天的 T2 和我一样得出 $144$ 错误结论的人也不在少数。悬着的心似乎放下来了一点,但是两天大众分加上不是很稳的代码,似乎也不能给我带来什么好心情。

就这样结束了啊。