CCPC 2018 湘潭邀请赛游记
Day 0
打印了 Claris 巨佬的模板(虽然看不懂),顺便打印了几个自己整理的常用模板(然而最后全都没用上)。
下午收拾东西,不知道哪里一抽就把小黄兔和蛤乐器带上了。
坐地铁到了杭州东站,17:50 上了学校报销的硬卧火车,车上偶遇浙江工商大学的巨佬,得知他们参加过区域赛感觉打扰了。他们说他们学校另外两个队都坐飞机(因为他们去年拿了银),而且学校报销,无限羡慕 QAQ。
车上一位老奶奶问起我们是去湘潭干嘛的,我们异口同声表示是去打电竞 😂 。
没上车多久就忍不住吃面包,然后一不小心把明天早餐的部分也吃完了。刚开始还翻看了一下自己带的《编程之美》,然后感觉车上的环境完全看不下去就开始划水了。
熄灯之前 jackyan 巨佬让我拿出之前打印的 2017 湘潭邀请赛题册,于是我也没法继续愉快地划水了。拿出了题册一起看,发现怎么有两道高斯消元,好可啪。xywsxp 巨佬也过来观摩题目。其中有一题大意是在给定图中删去最少边数使得 MST 变大。 xywsxp 在集训队群里面问了一波,然后老刘秒回“最短边删除不是就变大了吗”,然后 Claris 神犇秒打脸表示要用最小割,然后老刘就问起出发顺不顺利了 🙈。感觉好尴尬啊(虽然本垃圾也有过这一念头),%%% Claris。
晚上 Hanano 巨佬表示睡什么觉并安利了达芬奇睡眠法,瑟瑟发抖。最后十一点过的时候我忍不住还是滚到床上去睡觉了 QAQ。
Day 1
睡觉时完全处于一个小时醒一次的状态,于是四点过的时候就受不了爬起来看日出,然后发现 Hanano 貌似在下面待了一个晚上 QAQ。
下车出站后坐公交一路飙到了湘潭大学东门,然后来到了人均 30 人民币一晚的住宿,终于知道为什么老刘不来带队了,感觉被卖了 😭。
早餐混进了湘潭大学食堂解决,食堂的师傅热心地表示支持支付宝的,然后说完就现场拉了个学生喊他帮我们刷卡然后我们转账给他。怪不好意思的 QAQ。本想照顾队友不吃辣的口味于是一起点了“北京炸酱面”,但面做好后发现竟然是臊子红油拌面 orz。队友貌似被学校食堂的辣椒酱惯坏了,还勇敢地加了几勺旁边的辣酱 🙈 。这锅我不背(逃
中午本想跟 xywsxp 一起吃石锅鱼,然而由于他的花样乱带路我们就抛弃他去吃低配版华莱士了(逃
下午领了狗牌和衣服后就是热身赛了。热身赛只有一个半小时,感觉好短 QAQ。调了一下环境,本来想用 Sublime 结果配 build file 的时候貌似写错了一个地方一直没调好,于是就只好用 Dev C++ 了。
一看 A 题,感觉是个暴搜,然而不敢上,于是就开 B,发现 B 是个超级大模拟,怕写挂还是不敢上,于是就开 C 题,感觉 C 题貌似可做,想到可以把原矩阵和目标矩阵异或一下只要判断异或后的矩阵能不能按题目规则化为全 0 矩阵就好了。然后和队友脑袋一热猜结论只要 1 的个数能被 4 整除就可以了… WA… 然后很快就找出反例了。Hanano 巨佬貌似有自己的想法了,然后 C 题就交给他去码了。D 题显然是个 DP,然而我当时 DP 方程式推错(实际上少算了非第一个数开始的能被 3 整除的数)。差点以为热身赛要爆零,还好 Hanano 巨佬在最后十分钟左右 A 掉了 C 题,然后我立马开始码 D 题,结果发现样例没过,然后就一题滚粗了。
南邮巨佬好强啊,热身赛进行了一半就 AK 走人了。
在去觅食的路上反应过来了错在哪里,然后回招待所加了一行代码就过了样例,心情跌入谷底。无心复习的我晚上打了若干局 Wordament 和数独。
Day 2
早上起来感觉慌慌的,把开幕式翘了直接去了赛场。
Hanano 赛前就猜 F 题是签到题,比赛开始后第一个就开了 F 题,挂了一次后 A 掉了,太强了orz。
jackyan 貌似阅读 A 题的时候到了一点语言障碍,本来还在推 K 题的我过去看了看,发现是道大水题,然后就 1A 了,于是 jackyan 就去开 B 题了。
A 掉了 A 题后我意识到 A、B、C 三道题貌似是一个系列的,就去看了看 C 题。感觉是个线段树,然而没想出来怎么区间合并,所以就感觉是分块或者莫队。然而我都不会,所以准备丢给队友 🙈。与此同时 Hanano 又用容斥原理 A 掉了 K 题,好强啊 QAQ。所以我就去看 D 题了。
D 题我推了半天没有太确切的思路,看了一下榜发现没人过,果断放弃。Hanano 让我跟他去看看 G 题,然后 Hanano 巨佬很快想到了正解,1A,太强了orz。
看了看榜发现好多人都过了 C 题,于是我们一起开了 C 题。我们用莫队 + 树状数组 + 二分瞎搞出来了一个复杂度 $\mathcal{O}(N\sqrt{N}log^2{N})$ 的算法。由于队里就本垃圾不会写莫队,Hanano 表示状态不好,所以 Hanano 写了一半后就交给 jackyan 巨佬去写了,没想到第一发交竟然是 WA 不是 TLE,顿觉有希望。瞎改了一下莫队后又交一发,竟然 A 了。进入疯狂膜队友模式 %%%。
接下来就是循环卡题的时光了QAQ。我们主要尝试攻 B 题和 J 题,另外我也继续把 D 题和 I 题考虑了一波,然而很遗憾直到比赛结束都没搞出来,五题滚粗。本垃圾 A 了一道大水题后就全程划水,好惭愧啊 QAQ。
另外,午餐竟然是麦当劳,超级好评!
下午讲题的时候得知 B 题竟然是结论题,只要一篇论文一小时就好,吐血 QAQ。讲题人表示题是叉姐出的,有问题问叉姐,然后就光速讲完了,留下我一脸懵逼。
没想到竟然水到了一个银奖,然而摸一下奖牌后又要还给老刘堆在集训室了 QAQ。
jackyan 巨佬貌似对我有了一句新的口头禅 “你羞愧吗?” QAQ 😶
下午五点过就来到了火车站…… 打了若干盘斗地主,每次我发牌 jackyan 都会莫名其妙地当上地主,然后将本垃圾狂虐 QAQ。
然后湘潭两日游就这么结束了(逃
赛后总结
可以明显感到这场比赛中我太水了。
这场比赛反映出了我个人在思维能力上的不足。平时做专题的时候侧重点都在于学习新的算法而忽略了对思维的培养。这就造成一个很尴尬的局面,简单的思维题(诸如 DP)做不来,而比赛时需要稍微难一点算法的题目又不可能是裸的模板题,所以还是做不来。 🙈
看起来下个月要抽时间多练练 DP 以及数学了。 QAQ