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=1m=1的算法对拍。此时11:00左右

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

沃日,怎么要跑2s+

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

11:15

继续拍,果然飞快。

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

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

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

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

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

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

Day 2

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

看到题后,,,,,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

你家NOIpNOIp6题按难度顺序排列啊

你家NOIpNOIp出打表题啊

你家NOIpNOIp出ddp啊

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

100+100+100+100+50+68=518100+100+100+100+50+68=518

文章目录
  1. 1. Day -5~Day -3
  2. 2. Day -2
  3. 3. Day -1~Day 0
  4. 4. Day 1
  5. 5. Day 2
|

博客使用Disqus作为评论系统