NOIp 2018 游记

Day0

啥都没做,记了一下 vimrc 和配置,然后搞了一下午的颓。

然后头有点晕乎乎的,早点洗澡去睡觉,在床上想了很多,但还是强制自己大脑放空,早点睡着了。

Day1

由于去年的教训,今年我决定先稳住 (Day1)

进去先打打配置过了 (10min) ,然后解压下包。(今天密码是飞雪连天,那明天就是笑书神侠?竟然奶中了0.0)

看了看三道题,诶。。竟然没有模拟题?

然后有点慌,先写个第一题暴力,跑了 (10s) 把大样例跑出来了,发现对了,还行。

想优化,不会优化啊。。。诶我会平衡树 ,不对,不可能是第一题。诶我会线段树,不好写。

想了 (40min) 然后先弃疗这题了,发现旁边长郡小哥早就开始看 (T2) 了。。。


随便看看 (T2) 发现我会乱搞,直接从小到大贪心然后背包,随便就写完了。

样例过不了,尴尬。。发现多组数组没清。。。我有点疑问,我选 (2,3) 为啥不对啊。

然后看了看题面,原来不能出现的之后也不能出现啊,然后直接测一发大样例,发现过了!!

此时我不知道为什么对了,反正很欣喜,马上一波回头看 (T1)


认真想了想 (T1) 我会二分 + 树状数组优化,好像也不难写,也有暴力和 (gen) 根本不怂。

(15min) 就码完了,测波大样例,诶没过。。。哦原来是少修改了,然后测过大样例,直接开拍。


此时已经 (A) 两题,一点都不慌。看了看第三题,第一眼 林克卡特树?? 凉了,我写不出凸优化了。

想了想,有点不对劲,怎么会有凸优化。

先写个二分算了,然后直接贪心合并其中一条链,剩下的传上去一条尽量大的。

发现只能过第一个,看了看第二个样例,原来是边不相交啊,这不就是贪心改一下就行了。

随便写了个 std :: multiset<int> 来维护就行了,然后一波直接过三个样例,爽歪歪。

虽然有点慌,但发现此时我应该 (ak) 的时候有点不敢置信。

然后为了防止挂分,测了测三题的空间,极限数据和数组爆没,发现没啥问题后,回头想了想为啥第二题是正确的。

其实是对的,因为其中一个最优方案可以看作一开始选的物品的一个子集,然后你想使得这个子集尽量小且凑出原来所有的物品,这个从小到大贪心背包就行了。

发现还剩一个多小时,随手点开 emacs 的五子棋,竟然一把都没赢!!!电脑好强啊。


考完了,出来一问。大家都 (ak) 了啊,后来发现我 (T3) 那个 std :: multiset<int> 可能会被卡常,早知道不去五子棋了,卡常去。。

后来洛谷数据测一波 (100 + 100 + 95) 果然被卡了一个点。。但廖哥那清北学堂的数据好像没卡常?

Day2

今天是真的刺激。

开局,看看题,发现三道题都不会,要凉的预兆。

果然 (T1) 就让我搞了好久,一开始一看,随手写了个贪心,能过树的。

环套树, (n, m le 5000) 。不会做啊。想了一个巨难写的贪心,写了一会,发现大样例过不了。

然后开始强刚的不归路,想了好几种情况,发现一点都不好写。其中有一种甚至要手写栈模拟 (Dfs)

时间一晃一个半小时过去,这时候慌得一逼,整个人紧张地冒汗,疯狂喝水让自己冷静。

我突然想起,为什么总是有那么多不应该的失败(比如 (RNG)),其实核心就是没有及时止损。前期的劣势不是致命的,只要不要一直沉沦下去,最重要的还是稳住。


马上放弃第一题,写了个第二题的暴力。

对于这种只有两个输入的题,我想起来去年的小凯的疑惑,打表神题。

然后突然发现有 (n = 2) 的点可以打表,随便观察了一下。

诶规律不就是 (4 imes 3 ^ {m - 2}) 么。。不知道为啥,反正很妙就对了。


剩下一个第三题,看了下,暴力不就是没有上司的舞会吗?好像很好写,写完调了调过了两个样例。

此时心情沉稳多了 (60 + 50 + 44 = 154) 加上昨天也有 (450) 左右,还行。

再想了想 (T3) ,这不是 (ddp) 模板题吗。。写不出写不出。


决定再回首再来 (T1) ,认真想清楚细节,开始码,不到 (30min) 就码出来了。

认真对着大样例调,调了好一会,终于过了大样例,此时欣喜若狂,看了下跑得很快。

发现我这个可以优化成 (O(n log n)) ,用桶排序+链表可以优化到 (O(n)),但没必要了 。


回头看波 (T2) ,发现我暴力还可以勉强跑 (n=3) ,打了几个发现,不就是 (112 * 3^{m - 3}) 吗?

为什么公比都是 (3) 。。但我暴力跑不了 (n = 4 sim 8) 的了,弃疗,再见。

第三题还想写个随机树形态的点,发现写不出来了,算了。


出来一问,大家都是 (200) 出头啊,心里安稳多了。

但长郡那边几个神仙是真神仙啊,啥现场写出 (ddp) ,啥秒了 (T2)

后来洛谷数据测一波 (100 + 70 + 44) 第二题顺便多送 (5pts) ?良心啊。

Day ∞

这次还考的挺不错的,达到了廖哥考前要求的 (500pts)

预估得分大概是:

[100 + 100 + 100 + 100 + 65 + 44 = 509 ]

(Update~on~11.20)
实际得分竟然一模一样。。。qwq

[100 + 100 + 100 + 100 + 65 + 44 = 509 ]

虽然和理想中有部分差距,但我觉得自己已经表现的很好了。

经过这次考验,发现 (mathcal{afo}) 与功成名就真的之差那一瞬间调整的心态,多写那么几分的暴力。

水平还是不够,细节题还是写的不够。曾经很怕细节题,这次考试还是刚出来了,不容易。

简单题看不出简单做法也只能证明我的前路漫漫,修行不够。

希望我能再接再厉,这毕竟还是个起点,虽然表面很辉煌,但是却还是有一丝运气庇佑着我,冒着翻跟头的危险拼命迈过了第一道坎,发现之后的路途会更加坎坷。

往日的共同前行的伙伴大多还在,希望所有人都能翻过那座山,让大家听听我们的故事。

原文地址:https://www.cnblogs.com/zjp-shadow/p/9943572.html