GDOI2020 游记

# 远古的回忆 - $\rm GDKOI2017$ 啥都不会, $\rm naive$ 的我,暴力都憋不出来几个,打铁了。 讲座基本没听懂。`Day1`讲座结束后,对着大佬们斥之为 `Trivial` 的 $\rm EXgcd$ 一脸懵逼,徘徊踌躇许久。 可能这是离 $\rm AFO$ 最近的时刻了。最终还是决定坚持下去,毕竟自己还年轻。 自认为 $\rm OI$ 的漫漫长路从此已探明,只余静候的万水千山。 - 佛山市选 ~ $\rm GDOI2018$ ~ $\rm NHOI2018$ 跟了一些高中组织的课,也算接受了启蒙教育吧……认为线段树能出紫题,就是个很高级的算法了。 教练给了一本《高级数据结构》,于是翻书自学(印象很深的是别人在打篮球时我坐在球架旁看倍增`SA`)。集训中经过数天的努力$\rm AC$了生涯第一黑(现在应该掉紫了)。 市选凭借着 $\rm DS$ 常识,写了几个会的暴力,然后就过线了。 省选时虽然有预备送分赛,但还是仅仅获得了零头分(最短路不会$\rm SPFA$),白嫖了一张 $\rm Cu$ 参与奖。 $\rm GDSOI$ 当然是混不进去的,膜了能过线的神仙学长 $\texttt{sc}$ ,但是他似乎发挥不是很好,与省队擦肩而过。 为了缓和局势,打了个初中区赛,由于普及程度不高,题目是普及组水平的。 于是就并列 $\rm rk1$ 了,恰好前几届学长手中都有 $\rm rk1$ ,于是就在这个零碎比赛成功蝉联了。 - $\rm NOIP2018$ ~ $\rm WC2019$ 暑假去了长沙见世面,膜到了 $\texttt{YJQ}$ 神,发现自己仍然什么都不会,尤其是数学。得到了进一步的启蒙。 大概会了一些基础算法之后,就迎来了联赛, $\rm Day1$ 的一道贪心送我上分, $\rm Day2$ 的低区分度令我莫名其妙地保持了优势。 于是就获得梦幻般的成绩,不错的省排名,当时自认为是因为自己学的板子做的题都挺牛逼的。 去了 $\rm THUWC$ ,两天做了两道数据结构题,但是其他的一窍不通。膜拜拿约的学长们。 接下来的 $\rm WC$ ,接受了多项式启蒙教育,由于不会 $\rm SAM,LCT$ 被怒斥(不是)了。考场上由于提答良心送分于是获得了 $\rm Ag$。 看到 $OIerDb$ 上自己的排名很靠前,着实沾沾自喜了一阵子。殊不知这只是上天给弱者的好运罢了,真正的高手在等待时机,而且比我更努力。 - $\rm GDSOI2019$ ~ $\rm PKUSC2019$ ~ $\rm NHOI2019$ 得知省队收紧,送分场取消,直接进行 $\rm GDSOI$。由于联赛的优势获得了入场券。 当时在试炼场(老古董了)通了很多专题,集训时学了不少新科技,看了看往年的题目,自我感觉良好。 谁知 $\rm GDSOI$ 难度不比送分场, $D1T1$ 就是 $k$ 进制扩展的 $FWT$ 变换,加之经验不足(和“送分大水题”这一奇怪的题目名称),$3.5h$ 搞 $T1$ 只有 $20$ 分。其他的暴力没有 $\rm rush$ 出来。 讲评时发现四个题都不太可做。学长近乎 $\rm AK$ ,进队稳了。 $\rm Day2$ 心态放平,写了几个暴力,但是仍然挂了分,最后以 $85$ 的总分惨淡收场。 最后看到学长 $\rm rk2$ 了,无限膜拜。 两年省赛连续酱油之后,开始感觉有点慌了,但是并没有意识到问题所在。 接下来就是 $\rm PKUSC$ , $\rm Day1$ 一个机灵`bitset`题送给了我, $\rm Day2$ 一个构造被我随机化了,加之没有数学和面试,于是拿到了 $①$。 算是坚定了信心吧,其实也是对定力危险的考验。有人问到我拿了奖之后想干什么,我说我想继续坚持现有的一切,除了策略上,不会有其他变化。 区赛又一个 $\rm rk1$ ,其实两个贪心题都莫名挂了一点点分,如果数据强一点我就没了。 - $\rm CSP2019$ 暑假开始进军计数,出完了一套 $\rm CmdOI$ ,回首看来,其实创意确实不错,但是垃圾题也不少。 获得了百黑,自我感觉良好。觉得联赛随便考就是了,于是集训的时候学了一堆无关的算法。 $\rm Day1$ 获得了大众分。$\rm Day2$ 降智了,在好运加持猜到 $T2$ 结论的情况下,该打的暴力没打,该切的简单题没切,分数平平。 排名比去年还低。 在已经遗忘的某个时刻加入了万U群,发现了真正的世界和许多大佬。有些比我小还比我强还比我努力。有些被我没有注意的同学其实早早就掌握了我不会的科技。 # 初三上学期 以文化课为基调。大体上保持每天中午 $1h20min$ ,每周六大半天的训练时间。(众多)大考前使用中午睡觉和补作业。 # 寒假 去 $\rm ZR$ 氪了一把,认识了许多大佬,被老师带着进入了很多新坑(坑尤为重要)。 比赛连续爆零,发现自己学了的东西都不考,暴力长长长,但是只要思考过的题目,能得到的码长很少超过 $2KB$ (这么短显然只有部分分)。称之为白学诅咒和白练诅咒。 网课期间,OI吸取了一定量的文化课时间,导致文化课走低 ( 植树节见到了学长,他说要珍惜中考的备考冲刺经历,不要等到将来高三才迎来文化课唯一的一次大冲。 **后记** : 我冲了!!! 奥利给!!! 得知开学较晚,省选时间线初定于 $5.22$ ,决定先停课莽一把。 # Day -nnn 停课前往石中集训,同届同学之中搞了一些知识分享会。 还有大量套题, $\rm USACO$ 题怎么这么神仙啊…… 写了长长的数据结构技巧笔记,长长的计数笔记,长长的树分治笔记,长长的网络流笔记等。 当自己的水平开始靠近大佬之后,才真正发现这段距离是多么遥远。 $\rm CF$ 掉成 $\rm CM$ 了,短时间内也没肝打回来,就当是积攒 $rp$ 吧。 发现省选推迟了一个月,但是现在回校已经来不及了,文化课,危。 # Day -n 考前爬了很多大佬的博客,有同届的,有往届的。又开了新坑,收藏夹链接总量膨胀至 $\rm 120KB$ ,觉得一己之力恐怕省选前填不完了。留了许多任务,中考后有缘再见吧。 中途需要体育中考,于是被迫营业跑了两个星期的河堤。由于模拟测缺考,时间成绩默认是 $0$ ,被安排在了跑得快的最外道位置。上跑道的时候有点慌,最终还是满分了。 最后几天闲来翻了翻(我认识的)同届大佬们的博客,发现大家在 $2018$ 年某些领域的水平就远超我了,启蒙进度也非常快,刷题量也大,我在背`FFT`的时候大家都已经在生成函数卷积计数了。不禁为自己的过去汗颜。 # Day 0 上午拍了个毕业照,下午赶到酒店,膜了膜各位大佬,和 $\texttt{lah}$ 大佬一个房间。 尝试默了个`EXP`但是学长说不会考,尝试冲击 $500$ 紫但失败了。开始看自己写过的东西越看越慌,觉得好多东西都不熟练了, $10:50$ 去睡觉了。 # Day 1 $7:00$ 起床,又看了半小时博客,才前往考场。 这场比赛对于同行的大多数学长们都是决定命运之战,在晨光中(谈笑风生)走向考场,油然生出一种悲壮来。 随便看了看座位表,发现按姓名排序, $\texttt{zjr}$ 大佬在同一个室,`%%%`。 $\texttt{ntf}$ 大佬在另一个室,惜哉难以一睹真容…… 密码无法分辨 $1/l/I$ 差评,试了三次终于解压成功了。 开题先通看题面, $T1$ 感觉是故弄玄虚的数据结构, $T2$ 看到多项式,$m\leq 1000$ 估计是小清新式子题, $T3$ 完全没见过。 $T1$ 题面很长于是略读了(危),很快想到了 $O(n^2)$ 暴力。在线段树上推了一下,发现了很好的性质,于是写了一棵线段树。 跑样例的时候能量都是对的,但是温度对不上,我傻乎乎地以为有 `SPJ` ,加之受 $CSP$ 经验影响,认为需要留时间给 $T3$ ,于是丢掉没管。 $T2$ 在草稿纸上暴风推了 $5min$ 式子,发现全都是套路 : 斯特林数,交换和式,下标平移,二项式定理。 手写式子推出来之后,莫名地感到欣慰,至少打破了白学诅咒。 写了个暴力计算推出来的式子,略微调试之后过了小样例,很开心。于是写了一个对消质因子的东西来算组合数,就过了大样例。 此时还有 $3h10min$ ,就开始看 $T3$ , $2h$ 思考无果,又只会 $10$ 分暴力 ($\rm CSPDay1$ 既视感)。 给 $T1$ 写了个对拍,还贴心的给自己写了 `SPJ` ,没拍出来错。 最后 $30min$ 检查文件,顺便看了看题面,突然发现 $T1$ 要求的是能量相同下尽量高的温度! 然后开始对着正确的题意 $\rm rush$ ,发现救不回来了,最后 $3min$ 无奈的给暴力写了一个剪枝 : 若线段树上递归左侧后答案未改变,才递归右侧。 发现了自己斜对面就是神犇 $\texttt{zjr}$ ,他表示人均 $210$。大家都很稳,自己挂题惨惨。 当时以为 $T1$ 变成暴力了,加之 $CSP$ 劣势,感觉进队无望。 **附** : 发成绩之后发现 $T1$ 得分高于预期。思考一番后发现,若插入位置随机,其实是期望 $O(n\log^2n)$ 的,于是拿到了第二档分(没错数据就是这么水)。 于是漫无目的地水了一下午,一题没做,晚上勉强看了点文章就睡了。 # Day 2 我要翻盘! 早上 $7:00$ 起床,振作了一些,又看了看博客。 今天会是 $\rm CSPDay2,NOIP2018Day2$ 还是 $\rm PKUSCDay2$ 呢? 好像这些 $Day2$ 自己发挥的都不是很好诶。 密码仍然是未知意义的乱码。 开题先通看题面, $T1$ 感觉有点神仙,但是 $m\leq 23$ 感觉是卡常题, $T2$ 是个一眼题, $T3$ 看起来怪怪的,感觉是套路题。 先做最可做的 $T2$ ,回忆了一下全局 $+1$ 全局异或和,然后加上 $\rm Trie$ 树合并就水过去了,非常好写。 然后开 $T3$ ,反演一波,就变成了求所有生成树的权值和。枚举每条边复杂度不太行啊。 然后想到 `CF917D` 的套路,把同种边压成一组,反正复杂度不会变大。 加了个剪枝 : 边数不足 $n-1$ 不跑。算毛估估了一下觉得挺稳的。 突然发现考前没有看矩阵树,一阵慌, $\rm rush$ 了一个矩阵树和人脑对拍若干组,没有发现问题。 接着 $\rm rush$ 了一个高消,也没有发现问题。 然后和反演拼在一起,调了 $30min$ 终于过了样例。 又自己瞎造了一些数据,没有发现错误,手模成本太高于是丢了。 在因子方面下功夫,造了个大数据,发现自己跑了 $2s$ ,觉得没什么问题了。 于是去开 $T1$ ,先设了个 $O(n2^n)$ 的状态,发现可以变为 $O(2^n)$ ,然后采用贡献预支,提前计算已确定的部分与每段距离的所有贡献。(其实就是所有已知贡献) 然后发现枚举新加入什么就可做了,写了一个 $O(n^2)$ 转移,状态量 $O(2^n)$ 的 $O(n^22^n)$做法。 后来发现转移的形式是子集求和,于是写了个分两段子集求和可以 $O(1)$ 查询,且空间较小。这样转移就是 $O(n)$ ,总复杂度是 $O(n2^n)$ 的了。 跑大样例花了 $\texttt{3s}$ ,觉得评测机配置好应该问题不大。 此时还有 $1h$ ,觉得没有可拿的分了,但是没有找到扫雷,于是就看了看文件,简单地拍了一下。 最后给 $T3$ 多加了一个剪枝 : 若所有边权相同,则直接取用上一次的答案。 最后 $1min$ 发现求解的循环顺序倒了,导致依赖值需要取用时还未求出,赶紧反了过来,考试就结束了。 出来和大家交流了一下,发现暴力分 $460$~$480$ ,掐指一算感觉进队无望。 # 后记 看了看U群上的讨论,大家纷纷表示简单场挂一题就输了,那我没了。 回到了文化课之中,学业繁忙,也没有去想省选的事。 最终出了分 : $60+100+10+85+100+85=440$ $D1T1$ 多了 $30$ 分很惊喜,但是 $D2T1,T3$ 都被卡常了,差评。 队线比想象中低,于是苟了进去。继上一届神仙学长 $\texttt{sc}$ 硬核 $\rm rk2$ 之后,我市省队人数终于增长了。 广东 $4\times E$ 吓死我了。 总结了一下经验 : - 比赛经验(常识)不足,策略不当,需要补套题。 - 开坑不足就会导致动力欠缺,真怀念空余时间有 $\rm idea$ 可想的岁月啊。