这是一场注定无果的比赛,最优惠政策实在是太过遥远了。
Day0
凭借常州主场优势,可以待在家里。下午报到试机,我靠这机器跑的真快,使用std::set
,无论是\(O(\log{n})\)插入还是\(O(1)\)插入都比我的笔记本快得多。然而FFT慢一倍。别人都在码SA,我嫌麻烦不想码。晚上心血来潮,在ubuntu里装ubuntu虚拟机。折腾了一晚上终于装好了。下面是guest OS和host OS的对比:
好像没有什么区别啊。于是我不打算升级到19.04了
Day1
早上到的超早。等了好久。考场在三楼,被ob亲切地称为二等公民。于是抱着吊打全场的幻想。发题,首先浏览了一下题面,这T3是什么毒瘤啊,一股消失的题面即视感。WC考这个,集训队作业考这个都算正常,省选考这种题是smg。
看T1,第一眼就两个log,发现没分。然后想了想,先二分再在可持久化01-trie上查询太傻逼了,当然是在01-trie上二分。本来想边二分边求答案的,发现好像做不了。只好写两个qry,分别查询全局第k大异或值和某个版本的第k大异或值。写了一个小时,调试+对拍一会,大概在9:30时完成了。
然后是T2,题目好长,理解了好久。然后发现前40很傻,线段树优化一下建图就可以了。不对啊,这明明可以做80。还有20,怎么想都不会,于是开始码码码。这个数据范围有些大啊,写之前我还专门测过,光是\(O(Tn\log^2{n})\)建SA就要1.3s了,还好时限有5s。然后写着写着发现这玩意好长,再加上线段树就要突破100行了,那哪里还有时间玩T3啊。于是干脆直接在ST表上建图。二分+ST表查询太长了,干脆换成只有一行的在ST表上倍增。Tarjan判环太长了,干脆直接求拓扑序的同时判环吧。于是成功78行完工。
一遍过编译,一遍过样例(除了第三组数据),一遍过大样例。爽。想对拍,发现gen出来的数据全是-1。至少还可以测一下跑了多久啊。完了。满数据7s。gprof分析一下耗时部分,我靠,100%花在Init_SA()
上,其中54%花在std::sort()
上。怎么和之前的结果完全不同。于是开始一个log后缀数组,这还不简单,开\(2\times10^5\)个vector,桶排即可。这个一个log的算法真的优秀,比两个log慢3s。完了,还是前向星吧。好不容易花了半小时码前向星(我是真的不会),码完了才发现这个东西是push_front
,不稳定,不能用于基数排序。大样例也WA了。
调调调,怎么调都不对,一直调到12点,心态崩了。早知道我昨天就码一个SA了。没办法了,按住Ctrl+Z撤销到一小时之前。反正只有7s,这边机器又挺慢的,应该评测时能过。然后开T3。
这时候完全没心情看题了,而且输入输出就和外星文一样。题面里说自然溢出,我就真的写了个自然溢出再模998244353,然后第一个点就WA了。删掉重写。(后来我才知道我删掉了自己的分数)开long long,第一个点就过了。我考试时鬼迷心窍,只看输出不看输入(我以为输入只有一个字符串!)然后看第二个点,这个输出似乎毫无规律。没空写BM了,于是肉眼观察规律,无果。继续看后面的外星文输出,没有一个有规律的。考虑压缩,输出0/1的大概可以除以8,输出int的大概可以除以3,出题人都刚刚好卡掉了。心态真的崩了。
这时候听说比赛马上就要结束了,弃疗,平复心情。开始吃东西,一边吃东西,一边看出一个输出”p”的点貌似可以RLE压缩,没时间写了。这时我忽然发现输入不是只有一个字符串,后面还有东西。于是我马上看出第二个点是快速幂。不敢写。果然,过了几秒钟就收题了。
期望得分\(100+80+4=184\)。出来,发现snz、ys的分数都和我差不多,就是T3都比我拿分更多,所以都吊打我。早知道我不卡T2常数了。lzq神仙T2写了乱搞,不知道他得分如何。
下午一边吃饭,一边害怕T2FST。因为我想起来,只有一个字符串长度很小的点,我怕不是一被卡常就只有10分了。要发榜的时候更慌了。一边听讲题一边看榜。一看榜,我们几个全部fst了。snzT2只有10分,我20,ys40。然而lzq有30,一众写暴力的甚至有40。又被所有比我强的人或者会暴力乱搞的人爆踩了,相当不爽。然而想起去年这时候的我,好像就是这种只会暴力乱搞然后得分不错的人。
准备复测,不知道为什么JYY一直要和我聊天。拿到数据,写了一个sh自己测试,发现只是T了而已。问候出题人全家,一个20W的题,后缀数组的log,而且100测,这不是明摆着和我这种自带巨大常数的选手过不去。这个数据一点梯度都没有,跑6~7s,得分不如暴力。询问后发现居然是在配置和选手用机一模一样的电脑上测试的,还TM用虚拟机。这可能是我在正式比赛中第一次被卡常。复测结束后发现snz是写错了,ys是空间开小了,他们都跑得飞快。看来我果然是全宇宙常数最大的人。
还好重测之后得到了60。然而loj上就可以80,评测机还是垃圾了。晚上没开CF怕心态爆炸。
Day2
早上觉得很困。发现虚拟机的屏幕不能全屏,辛亏我在雅礼学到了xrandr -s 10
。然后文字就有黑影,不会解决。开题,发现两道998244353,两道树,可能不是很可做。没有一眼题,就先去写gedit配置了。想了一个小时T1,一点都不会,只会超难写的40暴力。
然后看T2,暴力分好多,首先有40的简单状压,然后有20的链。先想了一个链的贪心,对拍后发现假了。果然贪心还是太弱了。后来又想了个不知道对不对的,反正过了对拍。然后想正解,首先根节点肯定要单独分,然后是不是可以给每个子树的根找一个集合对应起来,然后递归下去做?发现我不能确定这个集合。自闭了,没有一题会正解。这时大概是10点半。
然后浏览了一下T3,首先我把题意误解成了一个集合组的贡献是可达的点数,觉得这是sb题,然后发现sb的是我。暴力分好少啊,看起来只有12分。于是就先去写T1了。
T1写的是真的自闭,全都是细节,这个题也太烦了些。写完之后调试了很久样例,发现错在复制粘贴时少贴了一个else。然后就过了sb小样例。好像能测第二个样例,滚一下数组就行了。说着我把ll g[35][110][110][110]
改成了ll g[2][510][510][510]
。我还特地算了一下,空间只开了2个G,应该没问题。然后运行。运行一会儿光标没了,然后终端没了,按alt+tab卡住了,然后gedit里的程序没了,很快gedit也没了。我趁整个系统都没了之前进tty,登录就卡好久,然后tty也没了。心态都崩了。只好强行关闭虚拟机,开机时又卡住了。我绝望的在windows中查看submit文件夹,无意识地点开了readme.pdf,发现noi linux除了submit目录之外都会还原。看来今天是注定要爆零了。然而过了几分钟之后,虚拟机奇迹般的复原了。
然后我没有样例可测,只好自己gen数据。这个数据很好gen,却发现满数据,real time要3秒,然而user time只要1.3秒。吸取昨天的经验我不打算卡常了,只想对拍。却发现暴力也很难写就放弃了。
开始码T3暴力,首先码了\(l=n,k=1\)的8分,然后码了第一个点。这不用动脑子,码完却发现已经12点多了。我犹豫了一下是去拍T1,还是继续码,忽然迷之自信觉得自己不会fst,于是继续写第二个点的暴力。写完就基本没时间了。
期望得分\(40+60+16=116\)。和昨天的期望得分加起来正好是300。出考场,发现ys和snz的期望得分都和我差不多。T2的75分是简单贪心,然而我贪心太弱了想不到。
榜出来之后发现所有人继续fst,只有某lzq得分高于预计。snz吊打xyx失败,所以他很不满意,然而我FST的最多,整整30分。难道是T1被卡常了?我看result之后却发现自己WA了。代码能力还是不行,其他写T1暴力的人全部都能写对,除了我。又垫底了。
回家后第一眼就看到zc在洛谷上A掉了T2,他是真的强。