NOIP2018 游记

发表于 2018-11-13

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$。