CTSC&APIO 2017游记

Day 0

早上4点多起床赶飞机,起床的时候发现闹钟调成下午4点的了。。。(虽然说早就已经被父母的洗漱声音吵醒了)

飞机上碎觉。到了北京发现比福州还热。。。而且北京今天意外地好天气,没有传言中的“雾都”那么可怕,至少天还是蓝的。。。

下午去八十中试机。试机的题目是NOI2016的优秀的拆分和网格。于是就想敲个SA的板子,然后敲到后面板子不记得了,就打开了UOJ,就看runzhe2000和dick32165401都已经敲完FFT的板子了orz。然后等我准备跟着他们一起写FFT的时候发现他们SA的板子也写完了orzorzorz。

晚上在学校吃完饭就会宾馆颓,发现Pokemon Sun&Moon更新了,然后就颓颓颓。。。感觉第二天要挂。

Day 1

早上六点半被自己设的闹钟叫醒(MEMORIA叫醒力MAX)。然后发现酒店有订定时电话叫醒服务。洗漱以后坐大巴去学校吃早饭。吃完早饭就去考场了。

考试开始。看了一下第一题,woc这什么题这么长,不看了下一题。看了一下第二题,题目好短啊,看了一下数据范围好像n方可能可以做而且有50分?(其实不可做)再看了第三题,概率期望题,有修改和删除觉得可能是线段树分治?然后就不会了。然后回头看2,想了许久没有想出n方做法。。。然后想到了一个5方的暴力,就开始写写写,写完以后才发现可以通过把floyd改成spfa优化成4方。。。然后就写写写,写完spfa。写完以后开始看第一题,觉得第一题30分好拿要先拿。就写了一个n方的暴力,然后我把样例里面特征值和位置的对应关系的表打出来,发现居然是连续的!然后我一拍脑袋如果是连续的话那不就简单了吗?把第一位的特征值找出来后面的加一下不就好了。结果一写发现大样例WA。这就很气人了啊。于是我就乱打了一个10 233 3什么的进去,然后用n方的暴力把位置表打出来,做个前缀和,猜了一个结论,发现它居然是按照前缀和为第一关键字,位置从大到小为第二关键字排序的!于是就随手写了一个std::sort,然后发现大样例过了!爽的不行。我试了1e7的极限数据,发现要跑3s。于是就手写了一个基排,只跑了0.3s。代码主过程居然不到5行。。。然后拍了一会就开剩下两题。最后一题我那个公式死活没有看懂,可能是因为我太垃圾了吧(zzx说如果没有给那个公式的话我说不定会不会就看懂了呢?)。于是就开第2题,分析题目的性质,性质就是图是一棵树,加上一条边是环套树,然后环套树怎么求直径呢?环套树怎么求直径呢?怎么求直径呢?怎么求呢?。。。环上面的好像不是很好处理,一开始我只想到了单次n方的DP,这样还是4方的啊?然后我把那个DP式子里面环的min暴力展开,得到了一个可以用单调队列维护的式子,然后就很愉快地单次On解决啦。跑了一下600发现跑不过,所以估计只有25分。(花这么长时间只多拿了15分是不是不太好啊)最后还剩下45min,开始看最后一题,发现我会输出nan(哇我是傻逼吗),然后就真的输出nan了。。。最后半小时弃疗,沦为吃货选手。好像我旁边的那位选手看我开始吃巧克力自己也开始吃了。。。

出来的时候貌似好多人都会做第一题。刚出门最早听到的一位选手说的是自己是冲着AK去的,又说哪里写挂了只有200多了。虽然不认识但是还是感觉他好强啊0.0,感觉不是一个水平上的人。。。Espace说今天第一题只有NOIP普及组难度,woc我好虚啊,感觉对于别人来说是NOIP普及组的题对于我来说却要花上如此长的时间。

中午吃饭(花了5张票,我以前在学校也差不多是这么点的也只要不超过15块钱,帝都钱真是小啊)。下午看成绩,第一题a了,第二题25拿到了,第三题0。125,该拿的都拿到了。看完觉得没有问题我马上就走了。(发现代码忘记拷了,cy后来提醒了才想起来)在楼下听见一个学校的几个同学在讨论,说一个同学拿了175,那个同学还说“我就是把裸暴力都拿满了呀”。哎,感觉自己真的是水平不够,对于别人来说可能只不过是裸暴力,而对我来说却是有一定难度的。

然后去报告厅听讲评。woc第一题这么多人都过了。第二题是IOI原题?!题解的时候,O(n)求环套树的直径的做法被一句话带过了,好像被人吐槽了?不过感觉25分应该非常多人吧。第三题暴力分居然有50?我整个人都吓尿了。杨哥哥好像也拿到了这50分。好像据说并不需要怎么用到那个公式,或者说不用那个公式其实也是能做的。然后不完全统计里,拿到50分的就有30多人,感觉没什么希望了啊。不过其实对我来说也无所谓了,我也就是来打个酱油的,能拿到牌我就已经很开心了,不论是什么牌,我都无所谓,反正能尽力,并且找到一些比赛的时候的问题和漏洞才是最重要的吧。

Day 1.5

早上去听候选队的论文答辩。因为比较晚去所以坐在最后一排。听课的时候偶遇松爷。

下午被骗去听《王选的世界》。听完以后和dick32165401和ziqian2000一起去打球。

晚上在宿舍颓颓颓。感觉第二天会挂得很惨。不过能有牌我就很开心了,不管什么牌我都无所谓了。

Day 2

凌晨4点的时候被突然转身压到我的Espace吵醒。然后接着就没怎么睡好。。。

早上第二试。我先浏览了一遍题目。第一题看到第一句话就觉得是毕姥爷出的题,然后又看到了一大堆组合数乘起来,想起了六省联考里被毕姥爷的题支配的恐惧。第二题一开始以为是吉利出的题,据说是准备出在ZJOI里的题。本以为部分分很多。第三题感觉十分麻烦又是三维投影社么的就觉得没有什么好的想法。然后回过头看第一题。打了一个组合数的表,找到了一个logN求组合数模2的方法,然后看了一下发现直接n方DP有70分。然后继续想,本以为可以线段树优化,后来又找了一会儿规律发现满足组合数为奇数的条件是在二进制下一个数是另一个数的子集。然后开个数组把转移记下来然后再枚举子集就好了?然后写完以后发现1.5h过去了,对拍+检查了0.5h就开了剩下两题。第二题发现能一眼看出来的只有第一个5分。然后就先写了5分,后来觉得m=n的可能可以流但是想了好久没想出来怎么构图。于是决定开最后一题。最后一题的30分是可以模拟退火的。然后就写了一个模拟退火,结果调参调了好久最小样例都过不了,于是就弃疗了QAQ。

出来以后发现杨哥哥第三题写了3维的模退,虐场的即视感。

吃完饭回去查成绩。第一题a了,第二题只有5,第三题语气好给了10分。zzx貌似rank4进国家队了。dick32165401 155虐场了。immortalCO好像被卡rank7了。。。好像这场130-140的比较多吧,115真的不算什么,感觉滚粗的即视感。

下午听讲评,第三题居然是搜索,xmk大爷遗传+模退强行艹过去了啊好强啊orz。第二题是策爸爸的题啊,那个对偶我是真的没有想到啊,好像有一个很强的神犇90分啊orz。第一题好像大家都a了,好像我校的都是带根号的只有我枚举子集啊。。。

晚上颁奖。杨哥哥金了好强啊,我好像被线卡了15分啊。。。钟知闲口试过了入选国家队真是恭喜啊。(感觉别人的回答都是非常自信的只有他回答的时候在装弱真是让人捏一把汗啊)

这次CTSC虽然进步比较大但是还是有些地方值得我反省:

  1. 这次我两天自以为a完题以后就有种非常兴奋然后就飘飘然的那种感觉,这也导致了后面可能写暴力也不会特别集中精神。
  2. 想题的时候不要两道题一起想,这样比如说两道题如果相似一点的话可能会串题之类的。而且思路也不集中。(这次的Day2后面我就着急)
  3. 这次有点着急了,本来a完两道以后我就觉得稳了,但是这次则不然,我a了的其他人也都a了,而这场比赛决胜的关键就是在于a掉这两道题以后,剩下的暴力分,也就是这些“零头”的得分。所以在考场上a题了也不要太兴奋,要这样想:我会做的别人肯定也会做,我不会做的别人可能也不一定会很快地做出来。所以冷静,保持一个合理的做题节奏还是很重要的。可能在以后的比赛中,并不一定我都能想到正解,这个时候打暴力,打高分暴力的作用就体现出来了。
  4. 当然,考场上的决策也是很重要的。这次day1day2的决策在a完题以后都很不对,day1a完题以后并且写完第二题10分暴力以后,不是去写最后一题的50分暴力而是去肝提升空间很小的第二题25分暴力。虽然我自己对于题目意思的理解不清也占了很大的成分。day2a完题以后的3h只拿到了15分,而实际上能确保拿到的只有5分,因为最后的10分并不是能确定拿到的,毕竟样例都没过,能拿10分完全只能说是运气好。

这次值得以后学习的地方:

  1. 在我两天ac题目的时候,我并不是一下子就一眼看出来就a掉的,而都是先写一个朴素的暴力,然后从暴力中找到一些性质或规律,然后找到更高效的做法。所以考场上写暴力还是十分重要的,不论是拿部分分也好,还是启发正解也好。
  2. 考试时保持良好的心态还是很重要的,不论结果如何,但是能在自己出考场以后说出:“啊!在我能力范围以内的分我都拿到了”这样的话才是最好的。拿不到的分就不要想着去拿,而能拿的就要尽量去拿,最好是都拿到。

Day 2.5

倒霉的一天。

因为今天空闲所以打算迟点起来。然而5点多的时候还是被太阳亮醒(倒霉*1)。起床的时候发现自己好像有一些感冒了(倒霉*2)。熬到过了6点25到40的一片闹钟雨以后才安然入睡。直到8点的时候dick32165401的电话才把我叫醒。我们昨天都约好了今天去清北参观,结果因为昨天并没有定好时间所以就不了了之。于是急忙下楼买早餐,发现排队到我的时候发现自己钱包找不到了(倒霉*3),于是就用之前买东西剩下的硬币买了点早餐。后来回头的时候发现钱包在自己衣服口袋里,因为连帽衫口袋里的东西存在感太低就被忽略了。。。然后回酒店边补番边吃早饭。吃完以后已经是9点半。

赶到地铁站,上完车以后发现wzt票买错了,本来可以直接坐到终点站的结果被他买成要转线的了。后来转线的时候因为wzt自顾自地走就走散了,结果我地铁坐反了。本来坐之前有问一位路人,她说13号线是环线,都可以坐到五道口,然后我就上车了。上车以后一位口音纯正的北京人告诉我说我坐反了。看来那位姑娘也是外地人啊。。。(倒霉*4)

地铁上感觉自己人越来越不舒服,头变得很胀,身体有点发热,感觉自己真的感冒了。想了想昨天,好像昨天考试的时候我的座位刚好就在空调吹的位置的正底下。。。吹了5小时不感冒才怪。。。也有可能是我昨晚洗澡用太热的水洗,然后出来的时候太冷的缘故。

走到THU的门口,发现akf,hsr和zgg已经在等我们了,于是就坐在学长的单车后面一路进了校园,感觉清华的校园好大啊,里面的学生基本上出行都是靠单车。

坐到了清华食堂,dick32165401和runzhe2000早就到了,然后我们就和学长们一起吃了一顿饭,谈笑风生了一会儿,后来因为学长们要上课就出来了。

下午去逛北大。在北大还遇到了黄学长和附中的神犇们。

晚上点外卖,然后颓。看番的时候遇上cy查房,被d了一通,rp--。

Day 2.5

早上听课。

下午听课+试机。

晚上听课,cls的计数题。

Day3

Apio。

开始考试的时候一看,卧槽怎么两道交互题?看了一下第一道感觉并不那么像交互,可能只是一个伪交互。想了半天没想出来怎么做,然后很长时间以后才开始写11分floodfill暴力。然后再看第2个子任务,发现它是求一个区间的连续段的个数。想了半天分析出二维偏序的做法,然后上主席树。写完主席树并且过掉以后,监考人员就说时间过半了,我瞬间就方了。我一半的时间才拿了23分这是要滚了啊。后来开第2题,觉得这是一个很考验脑洞的题,花了2h过了4分和第二个的7分,花了这么长的时间是因为我好像并没有很好的结合grader和自己的代码来找规律,只靠自己脑子纯想,后来做完以后才意识到这个问题,不过也太迟了,因为得开第3题了。第3题看出来是分数规划,但是并不知道要怎么规划那个价值的函数,不知道它是要求最大值还是最小值还是最接近0的,也不知道会不会走出无限步的情况。所以我对于这道题的思路可以说是很乱了。本来想对着第2个子任务写,结果发现并不成功,而且正确性好像不对。然后最后10min只好开始rush第一个子任务,失败,0分。最后只剩下了34分。。。好像连去年的Cu线都没达到。(今年的Cu线也没达到)

好像我校的其他人好像都金了啊。我好像是唯一一个狗牌的。

感觉这次问题比较大:

  1. 决策不对。如果第一题没有花那么长的时间的话可能会更好些?
  2. 基础不实。分数规划一类问题的解法好像还不是很清楚。
  3. 智商不够。据说第二题好像得分和智商成正比?这个问题我也解决不了了呀。

下午听完讲评去打球,结果打到全校都没我们的人了我才反应过来,饭也没吃,车也都开走了。我也很绝望啊。找路人问路还被路人当骗子耍,社会是真的险恶这种人就应该拿刀子杀,不懂就说不懂,随便拿一辆公交车把我打发走是什么态度。后来终于打到了的士,回到酒店就看番吃泡面。

Day 4

早上听课。

下午听课。

晚上坐飞机回家。

原文地址:https://www.cnblogs.com/cocottt/p/6869477.html