APIO/CTS2019及北京的故事

期中考试总算是过去了,排名没有4位数,语文好像莫名其妙的高。

于是就去了趟帝都。

CTS

Day1

一上来,两个数数一个题答。简直自闭到极限了。于是就一直怼着T2lun题打,觉得应该是个最长不上升子序列计数然后模改一下,然后3h后发现自己fake了,不能直接乘组合数转移。欲哭无泪,于是花剩下的时间去敲了T110pts暴力,然后手玩题答前三个点。

最后我用OI知识得到的分数还不如手玩的多。

一出来WCX就Ag/Au稳了。(WCX:你们两天得的分肯定还没我一天多!Orz)

Day2

题目一发,看见一道计算几何和两道计数。哦,Fe稳了。

于是就打了个暴力,觉得这种状态很多而且最优解唯一的计算几何不好乱搞,就弃疗了。

出来发现大家都很惨啊。

讲题目的时候发现有人乱搞T1拿了95pts,有点小后悔哦。

论文答辩

大概就是:数据结构王朝没落了,计数元年开始了。

讲全局平衡二叉树的学车爷被色多项式拱下去了。

期间还发生了许多有意思的事情:

评委问zzq:“请问一个概率对一个很大的数,也许是个质数(998244353),取模,怎么办啊?”(考了四道计数还问这种问题。。评委怕不是题目都没看吧)

ps:dzdzzq:“尽管你是rank1,但我要是就不让你进队你咋办?”zzq:“我明年再来。”Orz就完事了。

评委问rank2:“你们学校已经十几年没有国家队了,你认为是为什么?”(很眼熟的问题啊,当年laofu也是这个问题)

评委问rank3:“假如三道题你都不会做怎么办?”(这不是YMD的问题么。。)

评委问rank4:“我觉得你准备的不认真啊,怎么ppt只有9页啊?”(感觉是个zz,难道ppt长短决定认不认真么。)

最后dzd讲话好评:

“为什么C没了呢?”

“多事之春”

“一股神秘力量在干扰着我们。”

“我们进了,但这事没完。”

“绝不就范。”

颁奖仪式

拿了个Fe(参赛证明)滚了。WCX拿了Ag,三巨头Cu

APIO

于是就到了APIO,感觉IOI赛制应该蛮有意思的。

题目一发,怎么满满的数据结构风。。。。

China的题目顺序印反了有点小伤,不然我数学题说不定就(hai)切(shi)了(yi)呢(yang)。

于是开始猛肝T1,这个T1真的很烦,部分分很少还不是很好写,重要的是每个部分都要用到特殊性质,对于最后的正解并没有什么启示作用,导致我打了3subtask还是没想到正解怎么搞。

当时的想法是,这应该是个带修改的“归程”,所以说不定是三个log之类的。如果当时想到这至少是个动态图,那么应该往\sqrt{n}方向想一下就想到分块了。

最后3h后我才拿了T143pts部分分,感觉打铁感++。

然后花了10min敲了数学题的10pts爆搜,开始搞T3

很后悔为什么没有直接开T3,不仅暴力分足,而且不同的暴力分对正解还有启示。sub2我用的是每次拿出来计算贡献的方法,sub3开了个线段树统计答案。之后想了下,只要把这两个算法结合在一起,正解就差不多了。考场上已经想到了sub4的暴力怎么搞,然后就时间到了。

最后43+10+60=113pts,不知道能不能苟个Cu。一出来zeven说自己180pts+,瞬间感觉很慌。

WZW:

“这T2不是sb题么,应该没几个人做不出来把?”

Cu至少160pts”。

AK的估计有几十个。”

被他说得更慌了。。。。

讲课:

第一场:关于内存的一些算法。

感觉很资瓷啊,虽然和OI关系不是很大,但是这些算法感觉还蛮有意思的,模改一下搞个题答/交互应该蛮不错的。

第二场:纯属混日子的不知所云。

不知道讲题的人什么心态,“从集合角度看DP",本来以为会讲子集DP什么的,结果讲了四个小时01背包和完全背包,而且不停说:“你们的方法比较反人类,我这种好理解之类的”话,然而其实本质没有什么区别。感觉真的是来混日子的。

开场不久礼堂就走了一大半,UOJ的群里已经开喷了。。。

第三场:PNG图像处理与渲染技术

竟然是首师大附中的人讲。而且似乎不是Oier?大概是个什么CG社之类的同学,基本OI无关吧。

第四场:树上线性问题

感觉是最OI的一场了,尽管题目挺难的,但是还算是有所收获吧。

颁奖典礼

感觉今年线比较神奇,而且意图明显:

Cu=暴力打满。

Ag=切掉T2+暴力打不满。

Au=切掉T2+暴力打满。

于是我作为一个暴力选手拿到了OI生涯的第一块牌牌,但是是个Cu。。。

JXLHYF、和灿也是Cu,ZevenAg

中间的相声虽然感觉是直接网上蒯的段子,一直“教师节”个不停,但是还是很不错的。

OI无关:

感觉北京,或者说首师大附中的文化气息真的蛮浓厚的,压力没湖北那么大,hsy的社团更偏向“同学们自己搞,老的带新的”这样,于是就有很多“动漫社”“CG社”之类的,首师大的社团更加传统文化一点吧,看他们表演跳舞啊、合唱什么的风格都很“红”,而且感觉训练的挺像那么回事的。

清北行/与前辈们的交流:

算是把之前的研学补上了吧。

感觉北大的校风似乎比清华要自由一些,建筑漂亮一些;清华要更严谨,校园也更大一些。

清华感觉有些刻板诶,“一个人只能带三个人”是什么奇怪的规矩啊。。。很麻烦才进了门。

见到了XYK,想起了他写的“撕了北大的约选清华却被拉去修大坝的故事”,还有“XYK的堕落园”。

再次见到了ZZD学长,感觉有点发福啊(...)。交流了一些有关于学习经历与做题技巧之类的东西,虽然学长退役已经蛮久了,OI功力还是丝毫不减诶。

然后见到了CJ第一届的大师兄与传说中的莫队。

参观了下木仓科技,感觉很有激情啊,成员都好年轻,都已经很晚了公司里却还有很多人(似乎已经看见我今后的生活了= =),听大师兄讲了很多有关毕业后应该干什么的东西。随着OI的进步,当年的前辈所会的或许到现在已经不算什么,但是开创了先河的人还是很值得尊敬,他们尽管已经退役了,但是仍然在不断学习,在各种新兴的科技公司为我们默默服务着。

莫队有点腼腆啊,跟我们唠嗑的时候一直喝水。

听到了很多故事,原来强如莫队也不是神:

“高一的时候也不知道之后要干什么,也不太懂OI该怎么去学,每天我们组里几个人就在机房里打游戏,甚至一直到通宵,然后学科和竞赛都没搞好,NOIP什么奖都没有。学科老师还有我父母都说:‘你看看那个莫涛,曾经成绩那么好,现在搞信息学竞赛成绩变成这样,别学了算了。’”

“但是我还是觉得,竞赛还是蛮有意思的,我还是要学,我准备告诉他们,不是竞赛的问题,是我自己的问题。于是我就花了一个学期学文化课,变成了第一,再次被获准开始学竞赛。”

“当时网上题目很少,要花很多时间才能蒯到题目,还是英文的,为了做一道题得翻译半天,但是就是当时刷了很多题目,比如POI之类的,实力才真的有了一个质的飞跃,从只会做之前做过的题目到会做没见过的题目。于是就进队了。”

“至于莫队算法啊,是我从区间K大数中想到的。”(感觉很神奇,原来最开始莫队是用\sqrt{n}去搞了主席树logn的事情。。。)

“知道自己是个什么样的人,再想想自己想成为什么样的人,最后努力去成为那个人。”--莫涛

北师大附中:

见到了很多之前比赛的时候熟悉的面孔,比如之前那个爆踩我们的女队= =。

朱子健(ZZJ?)的DP

收获挺多的,每道题目都可以想一下。但是我们总是get不到正解,除了我见过拿到斜率优化的原题以外,并没有做出来什么题目。

偷听到ZZJ和他们的人说话:“他们思路都还挺多的,会很多板子,可是总是想不到正解上面去。”确实,我们感觉之前方向一直是“多",结果往往不够“深”,会了很多数据结构切不掉APIO、打了一堆多项式和计数板子却切不掉CTS,这就是我们存在的问题。

与胡伟栋的聊天

胡教练(师兄?)很了不起,几乎以一己之力把北师大附中拉了起来。讲了一些有关于代码编程上的小技巧,然后应向老师要求吹了一会:

“我没拿过国家第一,只拿过世界第一。”

“楼天城刷爆各大比赛,没有对手,我碰巧战胜了他”

“你又不用要求太多,只要进国家队就够了。”

不知名巨佬的非传统题选讲

这些题目都很有意思啊。我想到了一些不错的解,之前写过的题目和博客帮助我想到了一些解法,比如二进制拆分枚举什么的,但是我不知道为什么,总是在离正解的最后一个关头突然偏了,比如想到二进制枚举却以为复杂度是错的。。。

感觉题答题和交互题更考验选手的水平一些,尤其是交互题,真的很有趣啊。

徐明宽的非完美算法讲解

宽神讲这个真的是实至名归啊。他乱搞的水平在全国应该是数一数二的了,当年退火切掉CTSC进国家队,IOI随机化拿到74pts最后全场rank2。当年毛爷爷就是不愿意乱搞,一直想着碾压式的胜利,最后反而以捧杯实力银牌滚粗了。

于是我们就度过了快乐的一个下午,想着怎么乱搞每一道题目,正儿八经的分析退火的正确率,还学到了手写UI后人类智慧玩游戏这种神奇的操作。。。

小插曲:

宽神:如果做不出来,往往看看部分分会对思路有很大的帮助。

众人:那么K=1(CTS2019随机立方体)是什么。。。

宽神:骗你的。

数学小讲堂:

基本都是:

对对是这样。

这一步怎么来的,想一会。

他讲到哪里了?

掉线了。。。

果然数学还是个硬伤。。。

测试:

传统+题答+交互。

传统题是个计算几何,就是线段与直线判交,要求nlogn,然后我N^2打挂了。

交互题是IOI2015的题目,杜教:“如果我想出来这道题的3.5N做法,比打出一个带垃圾回收的可持久化树套树更有成就感。”我并不会求平衡中心,也不会3.5N,拿了35pts滚了,hzj吊打了前国家队,orz。

题答题是个奇怪的东东,显然是NP的,我想出了一个贪心策略,于是开始码,没有checker和评分标准真的很烦诶。这样有了23pts。后来发现可以对操作序列随机化/退火,结果最后忘了把随机化后的答案装进.zip里,只得到了一次贪心的分,后用luogu在测了一遍,发现时间足够(每个点跑5min)的时候可以得到80pts,第二个点标准卡的很死,退火表现不是很好,但可以10^{10}的爆搜。而且其他点退火时间实际上可以更长,期望应该加起来有90pts

最后发现我们全员被BJ女队爆踩。。。差距还是很大啊。

总结:

这次联合培训收获还是很大的,但是也着实发现了许多的问题,于我个人而言就是:1.数学学得不够好。2.套路和板子会了很多但是非套路题想不出来。3.不敢/不会/想不到乱搞。

于整个hsy信息组而言就是:口胡风气很严重。

讲课的时候前面有两个人一直:“这不是这样搞一下就完了么?”“这不是水题么?”“这不是和我说的差不多么?”时不时还念叨一些很高级却和题目无关的算法,如果只用嘴的话还真的可以吊打国家队了。ZZJ和宽神讲课的时候明显不耐烦了,后面的BJ女队也很尴尬的看着他们秀,感觉有点丢脸。

后记:

NOIP炸穿的我没法去夏令营,于是灰溜溜的抱着块Cu滚回来了,希望那边的7个,尤其是高二的两个人能拿到一个理想的约吧(说好了进队然后回来带我们呢)。THUSCRP++!

Upd:BJpers2拿了1=

0%