NOIp2018 滚粗记

DAY 1

8:30

总算拿到题目啦!

打开题目一看,T1T2T3全部512MB,1s,没有什么特别奇怪的时间限制的题目,题目应该可做(吧)。

8:32

啥废事都没做,直接开T1。

等等。。。。。。等一下下

这熟悉的题意。。。。。。

这不是神TM的积木大赛原题吗?

直接5min消灭,过了大样例,稳如老狗。

8:37

快速过了一眼T2,T3。T2好像不怎么可做,想了5分钟只会一个a^n的10分暴力。T3好像更不可做,想了5分钟没啥头绪,连暴力都不怎么会写。那还是去开T2好了。

在草稿纸上YY了一下,觉得这题跟裴蜀定理有这什么不可描述的关系,回头读题,不对啊,不能找零啊。

又YY了半个小时,想了想怎么优化之前那个a^n次方的暴力,感觉不怎么可以优化.......怎么办啊,要退役辣。

打了个哈欠冷静一下,猛然发现好像我们只会选之前有过的纸币,并不会新造别的面额的纸币出来。一看样例解释....好像蜜汁有道理。

就酱,我的复杂度成功优化到了2^n,总算能得50分辣,(但是还是要退役)

赶紧花了10分钟敲完了暴力,过了一下样例,结论应该没有猜错。

下一秒,我就想出了怎么优化这个暴力:我们能组合出来的面额的钞票一定不会使用。

然后又花了10分钟去敲了一个优化后的暴力,即我们不枚举哪些不可能使用的钞票。

等等.......我怎么感觉不用枚举?

当然不用枚举啊喂 (*´ノ皿`) ,我们都把能组合的去掉了,再不用剩下的纸币一定会gg啊。

又花了10分钟敲了个数据生成器跑对拍,对拍没啥问题,稳如老狗。

9:15

辣么快就到T3了,今天应该很稳啊。(*/ω\*)

掏出草稿纸开始yy,最小值最大....emmmmmm,这显然二分鸭。

那怎么判断呢........gg

想了半个小时,还是没啥头绪,有点点虚,就去上了个厕所冷静一下。

回来路上发现我们好像可以用树形DP来搞二叉树和m=1的链的情况。

问题是暴力怎么写啊w

又想了10分钟,好像我们可以直接每次暴力枚举选哪条路,判断一下可不可行就好。

接下来当然是写写写写写啦。

10min敲完大暴力,直接过前两个样例,稳。

20min敲完链的树形DP,又花了10min写对拍,没有拍出任何错误,稳。

20min敲完二叉树的树形DP,又花了5min改数据生成器,结果并拍不上,不稳了

猛然发现我犯了一个很脑残的细节错误,改了改就能过对拍了,稳

11:30

总算弄好了,拍也拍上了,如果没啥意外的话应该就这样了吧。

剩下半个小时没能做啥事,也就对拍一下,检查一下拼写,检查数据范围,也就结束了。

12:10

woc,好像T3的根节点不一定只有两个叉,(怕不是要gg)(出题人应该不会卡吧)

woc,人均AK,我又要被暴打了

woc,dalao们居然玩了1个小时贪吃蛇,太强了

DAY 2

8:30

早有耳闻昨天晚上紧急换题,今天会难到起飞。

一眼T1:woc,这不是SB题吗?我们只需要每次贪心的选能到达的点中编号最小的就好啦。

然后5min敲完,一测,并不能过样例。

回头去读题目:woc,我看错题了,走过的点不能再回去。

那......好像不可做啊。

打个哈欠冷静一下,看一眼数据范围:m<=n

.......

那个60分的树显然直接在树上贪心暴做就可以.....问题是剩下40分的gay环外向树怎么做.......

好像可以用一个很骚的贪心配合找环强行搞一波。

在草稿纸上yy了半个小时,感觉可能很难写,决定战略放弃一下,先去看T2T3,有空再回来写T1(flag)

9:17

快速过了一眼T2和T3。T2:woc,这啥题啊,怎么看起来辣么不可做啊。T3:前44分显然是保安站岗原题啊,还有8分的随机树我们也是可以暴力维护一下的。

进过几轮思维上的挣扎,决定先去写T3。

花了30分钟快速打完了保安站岗那道题的代码,略作修改,直接取跑样例。

woc,怎么过不了“大”样例啊。

赶紧肉眼静态查错,没问题啊,没有任何地方写挂了。

woc,那怎么搞啊。

上了个厕所冷静一下,回来后直接在草稿纸上手玩样例。

不对啊,我手玩的结果和我的程序一模一样啊。

赶紧回头读题,猛然发现读错题了,这题要求每两个点之间都必须至少有一个人,和保安站岗并不同。

emmmmmm,好像更好维护了

又花了15分钟魔改之前写的DP,总算能“大”样例了。

此时已经10:00了,觉得还是先战略放缓一下那8分,先去看一眼T2好了(flag*2)

10:02

花了5分钟,总算彻底理解了题意,同时脑子里马上出现一个看起来可行的结论:每个格子的左下角那个格子一定比右上角那个格子更大才有可能满足题目要求。

花2分钟对着样例解释观察了一波,好像是对的。

那这个东西显然可以用状压暴力维护啊,然后再上个矩阵快速幂暴力优化一下就好了吧(数据范围也是这样说的)

为了求稳,先写了个暴力搜索验证一下想法。

拍了15分钟,拍好了,过了样例1,稳。

很不幸,这个东西并不能过样例2,事实上,样例2的答案为121,我的答案为144。

......

这就很尴尬了。

花了15分钟验证想法.....并没有问题鸭.....

那我写一个直接按题意模拟的暴力试试?

又过去了15分钟,我把更暴力的暴力打完了。

一测样例2,依旧是神TM的144。

黑人问号.jpg

难道我读错题了???

回头一个一个字读题,并没有啥问题啊。

.......

到这个时候,已经11点了,距离考试结束仅有1个小时了。难道真的要退役了?

不,还有希望,立马放弃T2,先把T3的8分先写了,再回去写不稳的T1。

11:02

根据往年的剧本,这个时候我应该要不就弃疗了,要不就在搞对拍。然而今年,我到现在连题都没写完。

凭借着17年单身的手速,以光速魔改了T3的暴力做法,把它成功地优化到了m*深度的复杂度。

然后当场爆写对拍,爆调代码,总算在11:30分的时候拍上了。

11:31

为了尽快写完T1,我赶紧对之前的做法简化了一波,并魔改了一下做法,变成了一个有可能写出来的东西。

当场爆写。

距离考试结束还有10分钟的时候,我写完了,但并过不了样例。

我快速写出来的代码一般都有成吨的问题,这次也逃不过一劫,我的代码有成吨的bug。

凉了,直到最后一刻我也没有调完T1。

最后还是没有检查后面的文件名和数组,祈祷自己不要写爆吧。

12:30

woc,T1我干嘛要写O(n)的SB贪心啊,我直接m*n暴力枚举那一条边被干掉不就好了吗?也许这就是题好人菜吧。

DAY 1 + DAY 2

期望得分:100+100+75+60+10(?)+52=397(?) = gg

洛咕数据:100+100+65+60+25+52=402 = gg

牛客数据:100+100+65+60+15+52=392=进一步gg

咕咕f数据:100+100+60+60+15+44=379=滚回去学文化

比起上年,我有了30分的“巨大进步”

也许这就是颓的后果罢。

总体来说,DAY1发挥得比较正常,DAY2在解题策略上有严重失误,T2浪费了过多时间,为了追求一个看起来的正解花了太多的时间,却抛弃了能得到的T1的40分。这种错误正是我批判的,没想到,自己也会在正式比赛上成为自己批判的对象。


update 2019/1/14

虽然我DAY2考得十分爆炸,但是还是凭着GX-10的成绩苟进了省选轮。

在这之后一定不能再颓了呢,这样下去怕不是要文化竞赛两爆零

原文地址:https://www.cnblogs.com/GoldenPotato/p/9939219.html