AC. 梦想

frank_c1

CTT 2017 游记

发布于2017年12月07日 | 2条评论 | 1,405阅读 | 大事记,比赛经历,点滴感悟,生涯框架

虽然说是基本算是退役了,但是清华集训可是第一次来哇,还是好好记录一下吧。

(Q:你不是高三了吗?为什么不是最后一次了

(A:我…… 我还想以另一种身份再来参观一下哇,希望能有机会(滑稽

Day 0

搭上 G20 的快车直奔北京!(雾

大概三点左右到了西郊宾馆,取来了物资以后就试机啦。

试机完后跟随众人前往土口野家,发现人巨多,堂食简直要出事。

回房间玩耍了一会儿就睡觉了。

(2018 前来填坑啦~)

Day 1

进场看题。第一题和树的点度有关,Prufer 序列一波以后变成一个组合计数,然后就只会 O(n ^ 3),至多用 FFT 优化到 O(n ^ 2 \log n)?决定先放一放。第二题似乎十分复杂,先放一放。看第三题,居然是数据结构题,不敢做不敢做,滚回来看第二题。第二题看懂题意后觉得有点像 SRM 那道基佬题,于是用费用流建了一波图发现似乎是可以的,码码码,大概 10 点左右 AC,愉快多了。接着放弃信仰开始码第三题暴力,写了 32 分以后感觉搞不动了,接着弃疗码第一题,发现 FFT 过不去第二个 Task,但是能过第三个 Task,也不错啦有 45 呢。比赛结束,居然实时出榜好评,发现有 rank 7,有点开心(是唯一爽的一场 TAT),原来过第二题的人没那么多哇。

中午准备吔吉野家,试了一下点外卖,居然可以用券,不错啊?新技能 Get,后面几天的中饭晚饭不愁了。在房间里颓了一会儿去听讲题,FIT 楼看起来好高端的样子哇。第一题有点厉害,第三题感觉 Idea 不错然而数据真是太难造。晚上吔吉野家,在 fls 房间玩耍了一会儿回房睡觉。

Day 2

进场看题。第一题一看数据范围 44,完了,不会是搜索吧?第二题一看数据范围 10 ^ 6,又不是计数,可能是可做题啊?第三题一看恐怖的奴隶主心凉一半,后来看看题意可能还是可做的?先刚第三题,有个简单的矩乘做法似乎能过啊?不对我算错状态数了,只有 60 分…… 怎么优化呢?苦思冥想了半天没什么头绪,遂放弃,看起来这 60 分挺好写的,我应该 30 分钟就能写对(Flag = 1),不如待会再来。刚第二题,发现随便搞搞就行,开始大力码码码,爆了好几发 OJ 才 AC,掉进无数坑,果然没有充分思考细节就开始写是一种作死的行为呜呜呜。这时大概十点半了,我还是觉得第三题 60 写写很快,于是开始搞第一题,一开始想了一个 naive 的 O(2 ^ {n / 2}) 算法,对了下样例发现这算法根本就是错的,怼着样例打了些补丁算法复杂度爆炸,不管了有分就行,开始码码码。不对啊我怎么无论怎么改都是 12 分呢,难道这个算法还是错的?有点怀疑人生。想想不写第三题恐怕要 GG,赶快开始码,码到最后真的没调出来 …… 112 分光荣垫底,今天大家分数都好高啊呜呜呜。清华集训前没有认真训练,现在自尝苦果咯。

考完发现后边有松爷,还有 noname,然后 mls 似乎和他们愉快玩耍了起来,于是我和 fls 先回到酒店准备开吔吉野家,还没点完餐听见有人敲门,屋外出现了松爷,mls 和 noname …… 于是大家开始一起愉快地吔吉野家。吔饭以后我有点惆怅,开始 Geometry Dash 舒缓心情。快三点的时候跟着众人去 FIT。第一题是松爷出的,这次居然不卡常好评!第二题是 noname 出的,良心题好评!第三题是徐明宽大爷出的,原来是是矩阵乘一行的小 Trick,而且还在 CTSC 2015 讲过,啊我当时貌似在神游?然而这个东西没想出来也真是自己菜。晚上想起 mls 几天前安利的纪念碑谷 2,下了一个开始玩,玩着玩着觉得挺好玩的,临睡前决定再过一关就睡觉,然后过完这关通关了?这么快的吗 TAT

Day 3

进场看题。第一题又是一道数据结构题?但是第一题位置的数据结构说不定可做呢。第二题好长好长啊,不想看哎。第三题一看 Bike 数学题,药丸。直觉告诉我第一题是可做题,开始大力刚,先想个暴力做法,然后我们来优化一下,分析一下,哇到处调和级数,这个做法复杂度好像挺对的耶。大力码码码,大概十点多 AC,愉快多了。第三题思考了一会儿发现我的智商并不足以构造出解,不如直接搜,发现 n \le 30 可以搜过,n \le 100 可以搜过,n \le 10 ^ 5 显然搜不过,行啦有 70 弃疗。开始钻研第二题,看了 30 分钟愣是没看懂样例 1,比赛结束。看榜发现第二题果然是丧病题(UPD 前两天 fls Google 到一篇这个问题的论文,哦原来这是一个早被研究过的问题啊 …… 早知道清华集训前多去翻翻论文),自己 rank 19,一般般但不算太差。

回到酒店准备开吔吉野家,颓了一会儿后出发去 FIT。第一题是 n + e 出的,第三题的确是 Bike 出的,第二题是 xllend 出的,太可怕了全程懵逼,完全不懂不平等博弈这套理论 TAT 听说第三题出锅了,不少选手要求取消 Day 3 成绩,不少选手赞同。不管啦反正对我来说取不取消无所谓,都进不了前 15。

Day 4

今天进场前我和 fls, mls 说,我发现每天我就靠一道签到题来支撑信心,AC 这题以后打打暴力成绩其实也就还可以(Flag = 1)。进场看题,第一题是计算几何,还有九条可怜。前一天晚上某群一堆人放烟雾弹说有题可以 WA 到怀疑人生,不会是这题吧?先看其他题咯。第二题是个树题,一幅 AtCoder 画风,必有高论。第三题是个计数题,我以前口胡过?一看数据范围,不可能吧可以做这么大?!!完了滚粗。想了想可能是第三题比较可做,先写个容斥搞了 23 分压压惊。接下来能怎么优化呢?权值是分层的,一层层 DP 就可以变成一个权值 0 / 1 的子问题,这个子问题貌似不难的样子。搞了一个小时还是没清楚细节,回忆了下这似乎是道第三题 …… 恍惚了一下觉得第二题可能才是可做题,遂放弃搞第二题,时间已经过了两个小时左右。这 Day 4 的最后 2h,也是清华集训的最后 2h,我就和沙茶一样盯着屏幕看了 2h,期间闪过无数种可能的思路被我一一否决,还想到过搞第一题,但已经没有时间写出甚至第一档暴力了。没有办法,弱就是弱,接受现实吧,在倒计时还有 30 秒时,我想到。面无表情地点开榜,毫无意外地排名末尾,第三题真的是可做题。尽管有许多遗憾,但一切尘埃落定,没有办法逆转。

出考场后,像是有种什么东西在离我远去的感觉。天气很晴朗,不像是伤感的气氛,但为什么,有一种莫名的悲伤呢?或许这就是退役的感觉吧。没有伤心欲绝的那种痛苦,只是一种淡淡的难过,难以描述的情感。眼泪难以自抑,就这样任其肆意流淌在脸颊上。

下午讲题并没有去听,只是在清华园里走了一会儿就回酒店去了,心情也好些了吧。

晚上寒武纪智能请集训队吃饭,支持。吃完回去又碰到 xy 请吃饭,支持。然后我们就目睹了 xy 劝松爷和 noname 喝点小(白)酒的场景(雾)

Day 5

从北京回到杭州。清华集训就这样结束啦。

总结

毕竟还有一次冬令营,也不能就这么认栽。

1. 写题前三思,充分思考再动键盘,不差这一些时间。

2. 暴力分再少也要义无反顾地去写,万一这是关键的几分呢?

3. 无论什么时候,面对什么事情,都不能划水,一分耕耘,一分收获。

  • WerKeyTom_FTD

    原来一天的时间有360h么233