NOIp2018 游记

记起一段你总哼的调调

那年这大街上阳光普照

Day 0

上午在机房划水,突然被水淹没,不知所措发现自己没带身份证。马上就要出发了,于是身份证被父上送到了南京。RP++

时光荏苒,这已经是我第四次参加NOIp了。一改从前每次欢乐的气氛,我突然感到有些压抑:今年我急于参加NOI,特别害怕考挂,并且经此一役,不知又有多少在机房朝夕相伴的人要退役了。在去南京的路上又看到了熟悉的景物,脑海中忽然浮现出种种往事。三年前稚嫩的我第一次参加普及组时的场景,两年前在宾馆终于打通了东方辉针城Easy的场景,一年前在南航宿舍聚众三国杀的场景,考完后站在走廊里如释重负的场景,点开成绩单时心跳加速的场景都还历历在目。在车上百感交集,并没有睡好。

到了宾馆和室友颓了一会原曲认知测验,几乎一题都没做出来,感觉自己是个假的东方众。

东方符斗祭真好玩。

我因为意外休学了一年可真惨。晚上想起了一些错过的人和事,很晚才睡着。

Day 1

江苏从8:00就开始试机。打开电脑开始码vim的配置文件、快读板子和对拍板子,全部搞定后发现已经8:20了。监考老师检查准考证的时候发现我坐错了位置RP++,我竟然认识监考老师感觉十分赛艇。在正确的位置上把板子打完之后马上就发题了。

时间限制和内存限制没啥槽点,可是今年的评测机竟然是i7-8700K!不卡常好评。

T1这个画风不对啊!我正在做的真的不是NOIp2013么(真怀念那个NOIp就能保送的时代)qwq。花三分钟码完了一个简单的循环,过了大样例。

T2口胡了一波之后发现选的物品一定是给定的物品的一个子集,于是从小到大贪心就行了。写了十分钟过了小样例,一测大样例发现WA了。检查了一下多组数据清空,发现果然是它的问题,改正以后就过了大样例。一看时间发现才8:10,什么情况,今年Day1这么水的么,和初赛形成了鲜明的对比。

T3这种要求最小值最大的题一看就只能二分。可是check怎么写,再套个DP似乎不怎么靠谱。于是考虑贪心,发现对于一个子树一定是优先子树内选出尽量多的链,在此基础上给父亲节点提供一个尽量长的链,然后就可以贪心了。子树内最多选出的链数比较好求,可以用双指针做。提供给父亲的链似乎也二分一下就好了,两个log跑5 * 10 ^ 4感觉十分靠谱。于是码了一发,代码量并不大,大概9:00的时候就过了大样例。感觉特别的方,觉得自己写了假算法,然而拍了一下似乎并没有什么错的样子。

造了极限数据测了一发,发现需要跑一秒多,赶紧切出去看本机配置,发现是i3-550就放心了。i3-550是什么鬼呀,为啥编号只有三位,难道是一代i3?出了考场发现还真是,淘宝上只要卖50块钱……南航今年这么穷的么

为啥今年Day1这么水,正解好想好写,暴力分也给的多,我考的真的不是普及组么qwq

考完听说是2.5道原题,什么鬼呀qwq不过大样例强度较大好评。

下午继续颓东方符斗祭。晚上去吃烤肉竟然遇到了连云港的学长Orz

Day 2

今天并没有坐错位置,很早就打完了读入优化和对拍板子。研究了一下NOI Linux的终端配色,发现虽然默认的挺丑的,但是别的更丑啊233。

T1好毒瘤啊……一改昨天送分的风格。而且n=mn=m-1的情况岂不是需要分开考虑,强行二合一差评。树的情况直接贪心就行了,基环树的情况可以枚举环上一条边删掉变成树来做。虽然肯定有更优的做法,既然数据范围这么小就直接写了。代码量似乎并不小,我写完的时候已经是8:30了。

打开T2发现画风不对,怎么一股状压DP的感觉?想了想2^nm的做法,发现并不会,于是扔了T2去看T3,发现更不会,除了44分暴力一点思路都没有,于是又滚回去淦T2……发现每一条斜率为1的对角线上的1一定是一个前缀,然而好像并没有什么用的样子。

过了一个小时还是一点思路都没有。这个东西关于m应该是个线性递推数列,$n$的范围那么小,难道是高斯消元求递推式,然后打表转移?然而这样也太毒瘤了吧,而且表我也不会打Orz……我决定上个厕所冷静一下。

在路上,我突然发现如果出现了形如

x a ? ? ?
a y o o o
? o o o o
? o o o o

这样两个斜向的相同的a,那么所有的被标记为o的格子斜率为1的方向上相邻两个一定相同。再冷静一下,就发现这个条件和之前那个1一定是前缀的条件不仅是必要的,而且是充分的。我通过通过这两个条件写了个dfs,在几分钟内打出了n \leq 8, m \leq 10的表。观察了一下发现当m \geq n + 1的时候好像线性递推都不用,每次乘3就行了。于是我就打了个表。

我竟然在NOIp的赛场上打了个表Orz……

T3只剩45分钟了,打完暴力之后发现链的情况似乎可以用线段树做,然而并没有写完Orz……总这样打不满暴力可不行啊。链的做法写到一半发现好像可以倍增,但是非常难写的样子。

走出考场听说T3是动态DP的板子题……为啥今年NOIp这么鬼畜,原题+普及题+二合一题+打表题+板子题???

Day 3

紧张然而并不刺激的文化课生活。

Orz 为啥这一届新高考需要背那么多古文……

JS的程序第二天就下发了,一放学就跑到机房开始测民间数据。

D1T3好像被卡了一点常数?不怕2333,评测机是8700K。

D2T1莫名WA了几个点?第二天的大样例好不良心啊……

发现D2T2没考虑n=1的情况,洛谷上被卡了一个点Orz,不知道CCF会不会卡

洛谷数据:100+100+90+80+95+44=509

感觉海星,写了的分大部分都拿到了。OI实在是一件高风险的事情,这次本校的小伙伴们有提交错文件的人,有忘了删调试输出的人,有把defense打成defence的人,还有数组开小的人(真是多灾多难的一年啊),当然还有很多被奇怪的题风送退役的人,祝他们在高考之路上一帆风顺吧。突然想起了一首歌,看到小伙伴退役真实伤心的一件事啊。这次侥幸没有退役,我深知自己的实力远远配不上这样的分数,下次也要继续努力啊。

Day 4

测了一下民间数据发现D2T3被A穿了。动态DP都不会写的我真是太弱了Orz……

3 thoughts on “NOIp2018 游记

发表评论

电子邮件地址不会被公开。 必填项已用*标注