THU Training 2015

Published: 11 Dec 2015 Category: life

游记照例还是要更的。

Day -x

又临考了,发现板子还没背。。背板子的时候又发现好多算法还没学。。。

花了几天草草地预习了一下KM、带花树、单纯形。唉?敲了个模版在UOJ上TLE。。。不管啦。。。

还有几天就要出发了,然而电脑坏啦。。。拿到hp的维修部两次,两个店员一个说整个系统要重装,一个说网卡坏了300块装一个,最后找了个懂电脑的亲戚帮看了下,花了20块自己买了个网卡装上去。。。还是没好!弃疗啦。。。

于是我的笔记本只能拿来看番啦,翻盖式播放器?接个无线网卡还能用!算了就这么用啦。。。

对贴吧的安利帖进行DFS搜索,找到了一部叫樱花庄的番,发现这是我初二入OI坑前为自己规划的人生,小时候一直很向往那些搞艺术的人。。。

虽然一直被评价为“应付考试还行,但绝对不是那块料”,但是干些边缘行业也许还是可以的(喂,谁给你的自信)。。。

最近也看到初中同学在参加艺考,以前单修书法的同学的素描水平都比我不知高到哪里去了。。。

Day -1

提前一天就乘高铁去了,在车上复习了下神不在的星期天,发现这些老番的动帧做得比新番用心多了。。。

高铁上的暖气实在给力,坐了半天喉咙就不好了,于是从这天开始都在吃药,感觉药丸。。。这也导致后来几天也没和室友说过几句话。。。

晚上侦查了下附近,在刀削面店吃了点串烧,感觉还不错。回宾馆开小号开黑干UR的B题,最后也只出了60pts。。。

虽然是这附近最便宜的宾馆,但每个房间一桶矿泉水真是体贴又良心。

Day 0

早上在永和大王吃了点,味道和卖相都跟绍兴的一样,不愧全国连锁店。

紫光门口的十字路口,无论是斑马线和红绿灯的配置都十分微妙,最后还是只能入乡随俗地无视了这些。。。

下午好好地学习了一下大老师的人生哲理,虽然没有半点道理,但却使人信服。。。我竟然被孤独哲理引起共鸣了,感觉迟早药丸。。。什么时候也来个奇怪的老师把我带到某个奇怪的社团来重塑下我的人格?机房里倒有不少哲♂学家,但那种程度是不可能同化我的!

试机全程提答,听说全输1就有35pts,写完之后根本没有时间跑,于是就滚粗啦。。。竟然是rated!看来可以收拾收拾回家啦。。。

Day 1

早餐没有粽子油条之类的平民食物但提供宫爆鸡丁,果然是宾馆的档次太高吗?

一如既往地分到了整个机房唯一一台不能用的机子,真是年年都有这样的好运气。。。

T1跟某POI题蛮像的,不过好像性质更加优美一点,写个并查集就完事了。

T2随手造了几个函数发现收敛得很快,方程无解的时候好像会有循环节,总之看上去暴力挺靠谱的。。。

T3第一眼的直觉是分块搞搞,感觉不知道怎么下手就偷懒写了kdtree+乱搞剪枝,卡卡常数感觉前40分是能过的,后面再骗个20差不多完事了。。。

出考场听敦爷说T2的函数会“假收敛”,由于我是直接看第100w项的所以什么都没发现。。。

吃完吉野家会机房刷了发榜,T2开double掉到了35pts,$n\leq 20$都可以卡精度我也是服了。。。(现在发现大概是把第$n$项和第$n+1$项输错了?)

T3第一发裸kdtree的提交87pts,后面越剪枝分越低,由于考试时比较虚所以交的是比较稳重的优化版本86pts。。。感觉不是很科学。。。

听讲题时感觉T2被耍了,去年lyp的sum卡了1e-8的精度误差,这次竟然说不允许存在一丝误差。。。是在下输了。。。

T3似乎所有发挥人类智慧的算法都被卡了?标算是优化过的线段树套表,那为什么不出成传统题呢。。。由于kdtree也算是个无脑算法,所以分数还很可观,感觉捡了条命

还有。。。听说绍兴一中的同学写的kdtree都很快?大概是因为我出的模拟赛里卡太紧了?开两倍时限也有可能被卡到暴力分这种事不能怪我对吧。。。

晚上听wjh说过几天要考3000m,雾霾红色预警excited!

Day 2

推迟了10min去吃早餐,然后发现别人也都推迟了10min,所以还是等了好久才等齐队友。。。

开T1,仙人掌!扔了扔了,先去做其他题。。。

开T2,物理题!浮力势能是什么!扔了扔了,看来只能做T3了。。。

开T3,斗地主!还是两个人进行博弈!扔了扔了。。。

最后还是决定去写T1,分析了下subtask发现还是蛮良心的,做了那么久CC,写个树剖什么的还是随手来的

写完T1的72pts后看了看板,发现还是算出得蛮快的,于是码了个对拍,发现线段树数组开小了,感觉捡了条命。。。

拍完又看了看板,似乎没人出T2的暴力,感觉很安心,然后开始rush T3的暴力状压记忆化搜索。

凭着noip的经验码码码。。。11点码完了,测了发样例,跑得好慢。。。不过看前几排似乎是对的。。。于是这样大概算码完了?好像写太快了,接下来不知道该干什么了。。。

又看了看板,似乎还是没什么人出T2的暴力,感觉很安心,然后开始跑T3,前两个点很快就出了,第三个点估了估要跑40min。

重新仔细看了看T2,发现浮力势能好像“怎么搞一下搞一下”就可以算了,暴力枚举eps或者搞个分段三分什么的也许能骗到分?稍微动了点邪念,不过还是理智地放弃了。

最后给T3代码加了点非常胡来的剪枝,跑了跑样例好像有60%的正确率,后两个点大概也能骗个4、5分的样子。调了很久参数,选了一个看上去最稳妥的,于是就这么结束了。。。

走到吉野家的时候队伍以及快排到门外了,在门口碰到了蹭票的松爷,敦爷果断选择收买!听松爷说我这把胡了,但是估了估,出T2的人怎么打都有150+的分,感觉多半是口胡。。。

然后蹭到票的松爷一副计划通的样子立马消失了。。。喂,喂,收买的意义还没体现呢!怎么就这么跑了。。。

吃饭的看到了榜,发现T2只有两人有分,感觉很安心。。。T3混到了72pts,比预估的还要高好多。。。

出T2的同学T1都挂了,于是就这么莫名其妙地胡了一把,一点实感都没有。。。

T2和去年的那道三维凸包是同一个命题人,真是执着。。。

Day 3

又推迟了10min去吃早餐,然而别人又推迟了20min。。。

T1感觉有点意义不明,随手写了一个就扔一边了。

T2看到一副原题的样子,感觉就是在每个分段的地方算一下,指数分布函数的性质刚好在集训队作业里见过。

T3是CTOX,不禁回想起了一些不太愉快的经历。。。

T2和CF303E还有胡测的ydc的奖金在结构上基本是一样,分个段积分一下就没了。由于我不会积分,所以就打算像303E那样挖一挖函数的性质来做(快看,这里有个不自量力的)

$n$个指数分布函数,第$i$个函数的参数为$\lambda_i$,那么第$i$个函数取到最小值的概率为$\frac{\lambda_i}{\sum\lambda}$,只记得这个结论了,然而这个结论在分段计算上并没有什么用,搞到最后也只骗到了30pts。

结局就是昏昏沉沉地做了一整场的T2,基本没怎么看T3。。。事后感觉多半是被什么奇怪的东西附体了,到底是什么给我强开数学题的自信的。。。

“由于T1是个签到题,所以标准分大概会比较高,可能有个230吧。”走出机房的时候我是这么想的。

结果T3意外地容易拿分,标准分屠到了299(这1pt是故意不AK吗。。。)

达成成就:没有考到标准分的一半。回想了一下去年的Day3,我好像考了杜爷$\frac{1}{3}$的分,大概还算是有进步了?

Day 4

Day3被狠狠地教了一波做人,所以Day4打算怂一点打了。

开T1,又是物理题?!看完题面发现物理只是来唬人的,码了个暴力交上去66pts(事后发现是因为写了I64d导致WA了一个样例),看了看榜,竟然已经有不少人过了?!

戳开敦爷的提交记录发现只有1kb,但是怎么想都逃不了写棵线段树。。。于是暂时性的弃疗了。。。

T2大概算这次清华集训唯一一道真正意义上的交互了,$O(nm)$贪心好像很兹磁,暴力维护一下函数就$O(n^2)$啦。。。

于是就开始码码码,码了1h也没过样例,感觉药丸,随手交了一个$O(nm)$上去就先扔一边了。。。

回去看T1,发现敦爷resubmit了一个3kb的代码,顿时觉得很安心。仔细想了想,可以简单地用最大子段和标记维护,码了个发现只有2kb,感觉很兹磁。

再去搞T2的时候感觉继续调$O(n^2)$的话多半是没前途了,然后就写了个线段树暴力剪枝,在线段树上暴力递归修改,发现整一段里都没有可以改的点的时候就不做了。。。

因为$O(nm)$本身也只有$10^9$的运算量,所以加了点剪枝立刻就跑过了。。。

这是我第三次写这种东西,第一次是NOI2014的D2T3,由于不会写凸壳就写了这种猎奇的暴力,然后被卡成了暴力分。

第二次是ur的决战圆锥曲线,那时候由于会写凸壳了所以就一点不怂地写了块套凸壳,然而并没有注意到随机数列的递增序列长度是$O(\log n)$的(不知道是不是$O(\log n)$,反正很短就是了。。。)。

所以这次写的时候也没抱太多的期待,只要比40pts多就胜利了。

有段时间回想起这道题,感觉在这题上这么暴力大概是$O(m\log m)$的。。。现在想想感觉不是很靠谱,也忘了当时怎么证的了,多半是意识模糊的产物。。。

最后随便写了写T3的几个模拟点,找了找subtask1的规律,写了个和树状数组很像的倍增,结果被卡常数了。。。

由于是最后一天了,所以留在机房看完了评测,发现T2顺利地跑过了,于是莫名其妙地又胡了一把。。。

晚上为了花完票,到五道口地铁站旁找了1h的DQ。。。最后发现最优解决方案应该是把票留到第二天早上在火车站吃早餐。。。

End

拖了两个星期总算是把这个坑填完了。。。现在写游记似乎基本是单机了。。。

营员交流的内容纠结了很久最终决定去宣传一下孟爷开发的黑科技,现在遇到的最大的挑战是如何在不黑孟爷的前提下讲完整个算法。。。

轻国和轻库都被TX端了。。。又少了一个可以消遣的站点。。。