NOIP2018杂记

DAY 0

考前默默打了下配置文件练手,记不到怎么调用系统复制粘贴啥的啥啥啥的,准备用自带的辣鸡寄存器复制粘贴就学习了一下命令

1
2
3
ggVG		//全选
"+y //复制到系统寄存器
"+p //粘贴到系统寄存器

然后有次模拟赛就复制输入的时候出锅调试半天结果GG。。。一整天就写了几道代码量短的题,本来想打道树套树板子怕调不出来影响信心并且NOIP不考就弃了。或者是所谓的“超量恢复”?不是很懂,反正当年体考前几天也没有再跑长跑了,或许有用?

问题就是下午到家的时候开始肚子痛,喝了点热水没啥用,当时心里还是有点慌的毕竟最后一天了不能这种时候掉链子,然后默默坐地铁,人又多又挤没座位,到站的时候各种不爽感觉凉凉,然后走到一个垃圾桶旁就吐了然后感觉好多了=.=。然后还是不能大意到酒店喝了点啥药然后好得差不多了,出去考前最后集合了一下然后回来看了下很久没看的前面内容都挺傻吊的一本通提高版 的tarjan求强连通分量然后洗洗睡了,居然没有失眠。

DAY 1

早上起来吃两个小包子不敢吃多了害怕肚子不舒服,然后一行人走去考场,一堆人开始毒奶(所以DAY1如此傻吊)一堆神仙玩意,到场没多久就进去了

进场发现过道有矿泉水和面包当时想的是会发结果并没有,然后就走到考场坐下,发现我们学校的一个高二神犇在前面问了老师哪个盘不会被清空,我都忘了这回事去问了下然后彼此点了下头就坐下了,并不让碰键盘然后就呆坐,想过上厕所但觉得不必要反而会会徒增紧张感就并没有去,然后发网络地址,开始码配置文件,发现自带mswin真好,码完配置文件编译不起发现是没加<ESC>还行,然后还是打了个快读板子,一遍打对没有出错涨了点自信,头文件不用bits就只用三个cstdio iostream algorithm

然后发密码飞雪连天可能是纪念金庸先生的,接下来打开第一题第一眼单调栈矩形覆盖第二眼发现傻逼原题,10分钟切了一遍过大样例稳稳,然后随便写了个$n$玄学的暴力过了大样例开始拍。

第二题第一眼同余最短路,第二眼神仙题不可做,瞎搞搞发现有点像个背包,发现从小到大第一个不能表示的就必定在最小的系统中,比最小的数小的一定不合法,比最大的数大的一定不优想到这都没发现必定在原来的几个数中也是菜死了然后搞到九点半一遍过样例$2000\times 2000$,最后半小时才发现所有部分分要开到5000 x 5000还打了一个$n=2$的特判直接输出$2$也是后来才发现一个是另一个的倍数的时候可能有锅,还要特判(都到这里了怎么还没想到正解啊喂)

慌慌张张搞到九点半没有更优做法果断选择80分瞎打了一个$2000\times 2000$的乱搞一遍过了大样例后想用$bitset$优化发现有锅还是要右移$2000/a[i]$次复杂度$2000\times 2000\times 2000/a[i]/32$还不如直接$2000\times 2000$不过反正是用来对拍的就写完开始拍,后来发现应该是$5000\times 5000$(考完还担心了一下然后再冷静分析一下复杂度不是值域平方而是是调和级数,主要当时不知道最大开到多少才能保证正确性怕WA,现在一想只用开到最大的$a[i]$可能还是可以过的。(update:刚刚洛谷跑了一下多过了一个点85其他的TLE…)不过这是后话了)还是随便跑。

然后看T3,之前T2做不动的时候看了几眼可能就像语文考试先看作文一样,没有想但后台有了个大致的思路,然后一眼二分答案,再把题意理清了感觉就是个傻逼贪心,码码码,小样例随便过大样例居然WA,简直震惊,仔细分析算法正确性可能没啥锅,应该是打挂了,于是把一开始正确的从小到大贪心改成从大到小贪心(想的是反正改起来不难怎么样过了大样例就是对的,没有手推正确性,以后要注意避免)然后当然还是WA,而且答案一样,当时就震惊了,没啥办法,想到没测会不会CE,开了个虚拟机测了下T1,T2没CE还行(不会虚拟机D2T1就凉凉了后面会说),然后可能还剩一个多小时,T2当时心里想要么是个非常高级的算法几乎不可能当场推出来(主要$n=100$的数据范围非常奇怪呀)或者是个非常傻吊的东西没想到,而且这种第一眼没想到后面就难以再想到了估计再去看也是浪费时间,于是全力调T3,刚刚刚,码码码……

一看时间我去只剩20分钟了这毒瘤题怎么还没调出来,现在代码已经是千疮百孔了各种debug,cout以及特判特别毒瘤,心里开始慌张,冷静一下(就用冻手使劲搓自己脸几下)开始用纸笔推(发现这样可能才是最好的方法)发现应该从小到大贪心啊啊啊啊啊,然后改改改。

小样例都不对,还剩$15$分钟,手心在冒汗,不自觉想这题爆零的话今天预估分数,然后锤自己一下强行停止。

想找之前能过小样例的错误做法来凑数,改.ans.out放到D:/noip完成,还剩$14$分钟。

发现mfind边界不对改之,能感受到手上由寒冷导致的僵硬,还剩$13$分钟。

愣了一会通过cout发现有的up[u]没被更新导致答案偏小(现在一直测的是小样例),还剩$12$分钟。

改改改,改好了测试,第一个点$15$,第二个点$31$,那么第三个大样例也不能放松之前的反向错误做法也能过前两个样例,那么答案是…鼠标滚轮快速的划过上方的调试信息,后突然醒悟用G快捷键,翻到底是$26762$吗(因为没有过过大样例不记得答案是啥了),手在发抖,还剩$11$分钟。

因为手太紧张,点几次都没有点到,当时想的是这就最后一次了,没过就没过去检查文件了也没时间耗了,可能是完完全全算法错了吧。点开,$26762$。恩,还剩$10$分钟,我过大样例了。

然后以可能是这天来手速的极限删掉了所有调试信息,一个个过了样例然后才像耗尽了全身力气一样的摊在了后一个人的桌前,(椅子没有靠背特别不爽,还有要吐槽的硬件就是backspace居然只占一格大小,回车占两行,斜杠(或者叫反斜杠反正就是\n的这个)跑到退格键的左边去,导致换行的时候每次都按错特别影响速度)

然后检查应该没有啥问题,也没时间开虚拟机了(毒瘤电脑虚拟机开半天第二天还几乎接近崩溃了见下文)(没检查memsetmemcpy第二天刺激CE导致考后有点慌,也是经常有类似的什么感觉文件名打错了了啊什么直接CE了啊这种心理确实不是很好以后要注意)

然后时间到,起立,关闭两个对拍,关闭vim走出去,看到高二神犇一句话“每个数可被删去当且仅当可被另外的数表示”,感觉自己菜爆了啊。出楼,一问感觉全世界就我不会T2,太菜了哎。然后去吃饭,一行人开始讨论今天的原题,结果神仙jmr发现O好像之前出过T2加强版(顺带一提O,佬,司都提前阿克立场了太强啦orz)就在校内OJ上果然我还是太菜了,然后UOJ群又有人在说T3原题,看了下还是有区别一个要求全覆盖一个不用,除了二分以外做法还是很不同的。然后下午到酒店闲得无聊看西酱退役记(文笔太好了)感慨一下自己这条路还是很险的,然后迷迷糊糊中某阿克DAY1的神犇找我打乒乓然而当时想睡觉把拍给他就咕咕了。
然后去吃晚饭,路上一直在想T2复杂度是多少感觉会遭卡成$50$啊,整个人都不好了,更加确信了DAY1三道傻逼题以及就我不会T2这件事,菜没啥肉差评。
在酒店大厅的时候遇到蔺老还是说了一些稳住心态啊可以看一下高二的心态跟我们不一样什么的,然后就上去了,洛谷民间数据已出,5min手打T2居然$80$分并且都只用过不到$100$ms,推了一下复杂度$nlogn$的不禁感叹为啥不开大点不过当时也不知道这回事,怕T就没开那么大,还是做了一个非常明智的选择。过了一会蔺老到来“查房”(幸好没颓咕咕)说了一下今天的情况,以及下午看起来比较丧不是肚子痛而是担心T2的缘故,估分$280$,说了一下明天题可能会难一点不要死磕一道啥啥啥的。然后睡前又看了一会tarjan,喝了药就睡觉了,不过今天睡的不是很好一直担心T3有没有关memset啥的会不会CE,以及只测了大样例会不会WA,非常纠结(以后还是要尽量避免这种)在迷迷糊糊中睡着了。

DAY 2

跑到酒店的餐厅吃早餐然后只有一两个小房间并不是想象的那种,吃了半个烤面包有点不舒服就没吃了,然后走到考场路上一群人怎么开始讨论普及组题啊是都阿克提高了没事干吗

然后进考场,这次拿了零食感觉很好。开始看T1感觉树的形态非常可做,基环树的形态手推贪心结果都被第二个小样例卡了,没法,一看数据范围$n=5000$,这数据范围加上i7的新机感觉是要$n^2$的节奏,枚举一下环上每个边断开然后就行了,问题是直接调用的树上的函数导致每次都会sort一遍非常不好(听说$sort$有序数列是$O(n)$?可能可过?(update: 民间数据都没过=.=))当时偷懒了没重新打一个,哎。一遍过了大样例再写了个每个边断一次开始拍就做T2去了,这题可能做了将近一个小时。

T2最开始看题的时候哎$N$那么大$M$那么小不是太明显的状压DP吗都连续出了好几年了哎……

然后开始推式子,恩就是右下小于等于左上嘛式子一些,手算一下应该$2\times 2$是对的,$3\times 3$咋是$144$???不管,先打了再说,然后确实$2\times 2$是对的并且$3\times 3$是错的更不用说$5\times 5$了,冷静分析,可能思路错了,改为一个斜线一个斜线的考虑,只能是连续的$1$然后全是$0$嗯嗯……手算一下样例还是过不了$3\times 3$,没办法,时间可能已经花太多,想到昨天说的不要刚太久,估计这题不简单,选择再打了个$2^{n\times m}$暴力,测了下发现所有$2\times n$时状压都是对的,然后就分了两个subtask骗50(咋不打表找找$n=3$的情况呢其实也是时间花太多也担心找不到规律太浪费时间了)

然后数据生成$2\times n$的验证状压正确性开始拍,拍到一半卡起动不了点击关闭也关不了,任务管理器也不行,叫老师来捣鼓一会任务管理器后也无果,说不影响收题,愿意的话可以重启(这辈子不可能的)于是就缩小到最小放在边边上免得难看zz)

打开T3一看不带修改是个非常套路的树形DP,简单的码完$44$分就只剩40多分钟了,剩下的分一看不可做也不硬钢了,也没啥事用虚拟机(打开虚拟机的时候卡机了一分钟,吓得赶紧像老师示意,结果老师看了几秒就自己好了搞得非常尴尬,不过好了是万幸)测了一下发现T1居然CE!!!论memcpy不加cstring的后果(以后不用bits的时候记得写四个头文件了)还是比较惊心动魄的,不过时间比较充裕,改完后继续对拍。

可能检查了几分钟的文件后猛的发现datamaker没有srand!!!这可真刺激,不过还是拍起了,问题不大=.=。

还有十多分钟的时候反应过来深度<=100的点可以从下往上更新两条链的答案复杂度很对,不过写起来太麻烦而且怕调不出来就弃了。稳稳当当检查了十多遍文件名(昨天就几分钟检查,还在担心文件名有没有打挂)(第二天不担心文件名了,却担心没有看cena用户名会不会有锅,果然是操不完的心==)(DAY2确实没有DAY1那么惊心动魄主要后面的都不会了O.O,有大把时间检查)

然后出来一问T1果然懒的写sort复杂度多了个log有锅,其他的分都差不多,基本高一都是$100+50+44$(就我不会T1系列)然后在门口照相,吐槽了一下两天题目难度差异如此巨大,T2据说分类讨论繁杂到佬都没写完?T3据说叫做动态DP???不管了反正没啥大的失误就还好,之后一行人去吃了个自助餐,感觉大家都稳省一了呀还是非常强的,然后就回家了。

后记

今天来看的话确实没有挂题非常优秀,然后就是小的细节上比最高预估的分少了一点,考场上的考试策略还是很对的,就是考后的心态要注意调整(考前还有点担心肚子会不会疼,果然身体是革命的本钱,平时注意锻炼这种事情才不会发生)总之这次NOIP算是超额完成省一的目标了(目标就这么低吗某神仙400+还嫌少呢=.=)至于冬令营啥的也是能去就去不能去算了,去了多半也是被吊打,总之对这个结果还是很满意了。

不管怎样高一的联赛已经落下帷幕,在接下来的日子里还需继续努力!!!😝😝😝