NOIP2018 游记

Day -5~Day -3

考试题太不NOIp了,所以写一写前几年的联赛题,找找noip是什么难度。

Day -2

前几年NOIp题写差不多了,看看模板题?

很多简单的模板懒得再写了,然后看到了ddp模板题。

看了很久ddp教程,没看太懂。

想着联赛不会考这么毒瘤的东西的,就弃了(然而……)

Day -1~Day 0

不知道该干什么,于是颓废了两天。

Day 1

进考场,先调vimrc。

拿到密码后手残把压缩包搞坏了(直接unzip 发现里面和外面都叫day1.zip,然后就想着mv day1.zip test.zip 然后里面就没东西了)赶紧找了监考老师帮我拷了旁边人的题。但是问题不大,才8:30。

一看T1,这™不是“积木大赛”么,积木大赛是前几年联赛题吧,我 抄 我 自 己??

再看T2,exgcd??? 一看样例和数据范围,这不就是个排序直接背包么…..

再看T3,没有什么思路,赶紧把T1,T2写完。期间一度怀疑T1要ll,后来冷静分析发现不用。

此时8:50。这个题目难度让我一度以为T3大概要肝3小时。然后开始肝T3。

大概9:30不到,我大概有T3一个看似正确的思路了,事实上确实是对的。

虽然没完全想清,但是赶紧开始写开始写,边写边补充细节。

10:15写完了。

大样例过了。

赶紧开一波emacs压压惊

随便开了半盘俄罗斯方块就关掉了。

这题不好写对拍,并且子任务中,菊花图没法写,链的情况这个算法肯定是真的,所以我就写了个$m=1$的算法对拍。此时11:00左右

然后发现拍得特别慢,以为是python太慢,但是我还是time ./track试了一下。

沃日,怎么要跑2s+

意识到链式前向星+vector+排序太慢了,赶紧把链式前向星+vector的部分推平了,换了个办法使得每个点出边的编号连续,只要0.125s了。

11:15

继续拍,果然飞快。

突然看到评测鸡是i7-8700k,吓傻了。

11:30可以交卷了,然而我在犯傻(emacs没找到什么有意思的隔膜),然后把每道题检查了几遍,最后5min的时候我把所有应用关了继续犯傻。

然后他们说后两题是POI的题???

下午神仙红包特别早就有代码了,她把代码给我然而我不敢交,于是她帮我交了luogu,300没挂分。

后面看了下普及组题,沃日怎么比上午还难,这个$T4$我根本不会啊

然后依然颓废了一下午+一晚上

Day 2

进考场前psk表示”昨天是2,3,4,今天估计是1,5,6“,我很慌,,,,

看到题后,,,,,

这个T1怎么都没思路了啊,这个T2是什么啊,这个T3怎么是ddp啊,我他妈为什么把ddp模板题扔掉了啊

咦,$m\le n$,$m=n-1$是个树可以直接贪心,$m=n$是个基环树了,,,,,

$n,m\le 5000$????那不是直接枚举删边就好了么

然后我个傻逼就写了删边+并查集+vector重加边,然后跑得巨慢

不对并查集不是$\log n$的么,这™怎么过啊

然而直接DFS就可以判断了吧

然而重加边这么慢,打标记就可以了吧。。。。。

然后就开始跑得很快,考虑评测环境是i7-8700k,一点都不虚。

还有两道题,T2直观想到了一个假算法,然后显然过不了。然后写了个暴力。

T3先写个暴力,看看ddp能不能根据对题解的记忆推出来?

然而事实证明这是不可能的。

继续开T2,通过暴力输出分析了下那个假算法错误的地方,发现少了一个限制:若 $(i+1,j)$ 和 $(i, j+1) $位置上的数字相同,则以 $(i+1,j+1)$ 为左上角的子矩形内斜线部分填的数相同。

$n=2$和这个性质似乎无关,那就直接写吧。

$n=3$推了很久还推不出来….

此时是$100+50+44$分,然而我联赛的目标是500+而且还有时间,继续看T3,似乎$A$的数据是那个所谓的矩阵乘法可以直接做的,然后就写上去了,此时是$100+50+68=218$,然而已经11:30了,不敢继续去想别的题了,赶紧检查检查再检查。

出了考场发现44分的暴力随便优化下就可以做B,白丢了8pts,自闭了感觉全世界都比我高

晚上发现n=3答案是$112\cdot 3^{m-3}$,沃日?applese爷告诉我所有$1\lt n\le m$都满足$ans(n,m)=ans(n,n)\cdot 3^{m-n}$其中$n\le m$,事实上只要打表出$ans(n,n),ans(n,n+1)$就能猜到并A掉这题了,我的内心MMP

乱搞水平技不如人,肝败吓疯。

你家$NOIp$6题按难度顺序排列啊

你家$NOIp$出打表题啊

你家$NOIp$出ddp啊

后来又是红包大爷帮我测的,218没丢,但是如果我认真打了n=3的表就能多15分了,以及T3少了8分…..

$100+100+100+100+50+68=518$。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×