2018acm-icpc江苏邀请赛后记

这场比赛可真难。

不得不说矿大的环境大大出乎了我的意料,无论是校园面积还是基础设施都很好,唯一美中不足的大概是吃了一顿晚饭每个菜都有辣,幸好饭票发的很多,一个人四张饭票,一张饭票可以换3根香蕉,于是我出食堂的时候抱着一大串相交,回头率提升了好多好多。

热身赛只做了A题签到题,C题的dp迟迟没有认真想,由于B题过的人太多了一度认为B题也是签到题,然而并不是,嘴上说着热身赛崩了正式赛能金,但是看其他队伍热身赛的实力就知道这场不简单,拓展kmp或者后缀自动机的题被过成签到题就让我觉得这场大概是hard难度。

然而并不是hard,正式赛才发现这场邀请赛比hard不知道难到哪里去了。

A题签到,学长一眼暴力,我觉得bfs更快,学长觉得没问题,于是连TLE了4发,一个小时之后暴力过了??喵喵喵,整场比赛没有想明白为什么O(nmt)被卡,O(nmkt)能过,比赛之后仔细一想觉得是因为bfs的常数很大,k范围较小的缘故,也有卡queue的传言...出题人最后讲题解说是bfs,然而被卡bfs的似乎并不只有我们一队...

D题签到,学长说组合数学加逆元,写了写就出来了,作为一个零基础数论的选手,话都没有说一句。

F题递推+java大数,三号签到题,(为什么每个队都会大数啊!),现在会java原来是acm选手的标配吗...连摸3道题的鱼

这三题签到题签完感觉难度和西安的三题差不多,然而此时我们还在铁铜的边缘试探

B题开始以为是规律题,后来学长队友开了5000 * 5000的预处理成功跑过了样例,然而MLE

于是我们把long long 改成int, MLE * 2

我提出滚动数组,把空间缩小成一个5000 * 5000,MLE * 3

我说暴力行不行,TLE * 1

这时候有一点凉凉的意思了,我突然觉得可以把预处理改成离线处理,双滚动数组一定MLE不了,时间也同样,

乌龙RE * 2,AC

就这样,艰难的AC了四号签到题。        

写I题的时候只能写出一个必TLE的简单dp,交了一发果然TLE,心满意足的开始想对策,赛后题解是邻接矩阵相乘,快速矩阵幂优化的dp,(喵喵喵???)没学过离散数学的我惊了,图论的邻接矩阵竟然可以相乘。

然而B和I还是被当作签到题一样的疯狂被过...整场给我们信心的大概就是边上的快乐爆零队。。

之前可能拿金银拿的太顺了,或许这才是acm的真正难度,之后的暑假要拿更多的时间来训练了,下半年有区域赛,按照我们队现在的水平,还是打铁的概率较大。

原文地址:https://www.cnblogs.com/Hugh-Locke/p/9499670.html