NOIP 2018 游记

AFO.

Posted by Monad on November 13, 2018

突然想起来好像 NOIP 2017 游记“明天再写”的 flag 还在……

Day 0

上午考完假的信心赛,中午机房第一次锁门,只能回去睡觉。14:45 出发,一小时多后抵达万达。
晚上去万达吃饭,不知是不是命运的安排,居然去了跟往年一模一样的店吃饭,而且坐的桌子还一样,座位也一样(除了当时的 yhf 换成了 lty)。
晚上回去忘记干了什么,企图换房失败,大概十点多就睡了。

Day 1

早上 6:50 起床,吃了个 sandwich 就去考场了,到达考场大约 8:10。发现右前方是 yhf,左后方是 yww(RP ++)。
Day 1 的密码是 [email protected]$Tian!,然而当时并不懂含义。

首先看 T1,表示没有做过原题,想了 20 分钟(在想比较优雅的实现),再加上 10 分钟的编写,就把大样例过了(蒟蒻表示并没有注意 “首尾相连”)。并且顺手写了个对拍。
然后看 T2,看完题目,完了,线性基,没有复习,GG。然后看了 T3 后回来企图推高斯消元和线性基,30 分钟后无果。后来灵机一动发现貌似可以背包,时间复杂度 $O(n \cdot a \cdot T)$(当时:我 *,那么水的吗),写出来后一次过大样例,就去搞 T3 了(此时已过去 1.5h)。

T3 的话呢,一开始也不觉得自己一定会做,就先把部分分的打了。先打了一下是链的情况,然后又打了一下 $m = 1$。
然后看到了 $a_i = 1$ 这么一个数据范围(菊花图),当时看成了边权为 1。然后就很纳闷,这是个什么鬼部分分。然后就写了一个树形 DP,并且证明了尽量在子树中匹配得尽量多不会变差,就认为 T3 可以水 55 了(三个部分分用了三个 namespace)。
继续想 T3 正解。突然灵机一动发现 $a_i = 1$ 貌似可以做 $a_i \not = 1$ 的情况,就很开心地复制了过来,测了一下大样例,发现居然不对(打脸)。想了一想发现还要保证在匹配得尽量多的同时要让尽可能大的数上传,于是就 xjb 实现了一发,调了几下居然把大样例过了。
emmmm?我 AK 了??????感觉有点虚,就把 T3 正解去跟我的部分分对拍一下。一拍就发现问题:$n = 1000$ 怎么跑那么慢(答案没错)?发现时间复杂度正常($O(n \log^{2}n)$),gprof 显示时间都在 dfs 上,于是肉眼调错。
于是发现 while (...) p++; 中的条件居然没有约束 p 的范围(没有 RE 也是神奇),就加上了。再拍一下,正常多了。
10 分钟后,把 $n$ 调大,发现 $n = 10000$ 也很慢(3s+),继续肉眼挑错。发现还是 while (...) p++; 这个地方,把 p <= qt 错写成 p <= n(差点写成 $n^2$),改过来之后 $n = 50000$ 可以跑过了。
这是还有半小时结束,玩了 10min 的小恐龙(因为没有扫雷)。

12:00 结束,去吃饭,吃饭时发现全世界都 AK 了。回酒店玩了一个下午和晚上,成功把 Chameleon Run 玩到全三星,顺便刷了一下记录(晚上 LGJ 没有来查房,估计是因为电梯停电了)。
当然还顺便看了一下 PJ 的题目,发现 T3 智商不足,还有普及的解压密码是改革开放……

Day 2

早上 6:50 闹钟响了,居然点了关闭,感觉有点困,于是躺了一会,再次醒来已经 7:20 了。下去吃了一个 main 包,跟昨天差不多时间到达考场。
Day 2 的密码是 %xiao#SHU!shen9XIA

首先看 T1,感觉访问的顺序不就是贪心走最小嘛,打完程序过了样例一,样例二 GG。画样例,发现贪心只对树有效,当 $n = m$ 时会有环,有且仅有一个。就按照这个想下去,20 min 后写了出来,也是一次过大样例。
然后去看 T2,看了 5 min(连样例都没画),觉得有点头大,就去看 T3。发现 T3 还好一点,于是先把 T3 的 44 分暴力打了一下,就回去看 T2 了。

T2 打了一下暴力,又画了一下样例,发现一个规律:对于每个 $2 \times 2$ 的矩形,左下角一定要大于等于右上角。以为这个就是正解,结果发现过不了 $3 \times 3$ 这个样例。
把中间结果输出了一下,发现的确有反例,但是又不会处理,只能把 $n,m \leq 3$ 和 $n \leq 2$ 的部分分做了(期望得分 50)。
然后把暴力优化了一下后拿出去打 $ 8 \times 8$ 的表(用了挺久的),希望表没有打错(可怜.jpg)。

这天没有玩小恐龙,emmmmm。

题解占坑。

CC 原创文章采用CC BY-NC-SA 4.0协议进行许可,转载请注明:“转载自:NOIP 2018 游记