JSOI2019 Round2 游记

Day 0

和同学们坐火车一起去南京。一路上都在颓雀魂,有一次大三元听牌了但是并没有和到,感觉RP又增加了。

南航电子系的芯片墙看起来好高端啊。晚上去试了一下机,发现实验楼机房的CPU竟然是i7-6700,十分赛艇,比起NOIp2018一号楼的初代i3简直不知道高到哪里去了。NOIp的时候眼睁睁看着评测机的i7-8700k本机却只有祖传i3的感觉真自闭啊。

试机的时候我打了个多项式求逆,然而发现它一直过不了手造的一组数据。调试了半天输出了各种东西才发现原来是NTT的时候忘了按照二进制的逆序重排,感觉自己实在是太菜了。

今年JSOI的Round 2与往年不同,竟然只有一天,感觉十分容易翻车。

Day 1

现在回想起来当时许多细节都忘记了,只记得打开题看了一遍发现三道题都看起来很不可做的样子。我感觉自己退役稳了,只好重新看了一遍题,发现T1似乎是个2SAT,还要用bitset优化,感觉十分不可写。又看了看T2和T3,果然还是被劝退回来写辣鸡bitset了。

幸好JSOI开了C++11,只花了一个多小时就写完了T1。然而一个样例都没过,心态有点崩,又调了不到一个小时才过样例。由于我的bitset是使用指针new出来的,所以常数比较大,空间限制本来就紧,时间空间两被卡。拿了60分就先不管了,滚去写T2和T3的暴力。

打完暴力发现还有一个小时多一点,然而T2和T3完全不会,只好回来优化T1的bitset。把new改成内存池之后测了一个极限数据,发现RE了。检查了一下发现好像忘了开大栈空间了,虚惊一场,又测了一次发现时间已经卡过了,但是空间还是严重超出限制。建图基本上没有优化的空间,建出来的每一个点都是有用的。

还有40分钟就要结束的时候,我尝试给每个bitset节点加了引用计数,只在用到的时候才分配内存,并且在指向某个点的所有入边都被访问过之后就把这个点丢回内存池里。这个优化似乎效果显著,调整了内存池的大小之后跑过了85分的数据,再大的内存就RE了,应该是用完了内存池。听说NOI系列比赛中开的内存即使不用也会被统计,不敢开大内存池了。

出了考场和同学们去吃了隔壁路上的石锅拌饭,饭很好吃但是我很虚。T1的样例很弱,bitset要是写挂了什么地方很难查出来,又听说NFLS的神仙们都会T2,感觉自己要退役了。

滚回去听讲题的时候发现自己T1竟然过了,什么情况?

新人求助,生死预测那题,本机RE提交AC。

听完讲题回到机房发现当时自己测极限数据的时候没开无限栈,实际上是爆栈了而不是内存池用光了。

第二轮省选的时候运气竟然又这么好,靠着bitset乱搞苟进了省队。NOI的时候肯定就不能这样了,题目的区分度肯定很高,我这种只会乱搞的蒟蒻选手肯定就要被区分掉了。NOI也要继续加油呀。

发表评论

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