2024 CCPC Final 游记

    2024 CCPC Final 游记

    希望能带来好运!

    Day -1

    早上六点起床,打车前往福州南站,我是清晨告别洋流启程的沙砾 …

    昨晚收拾了很久,没想到今天还是忘带了三样东西:U 型枕、剃须刀、模板!福州南站还把我的花露水给扣下了。

    早上十二点多到达新塘站,再坐了一小时多的出租车,到达港科广的时候已经下午两点多了,2020 ICPC World Finalist 学长-李进 在校门口迎接我们,非常感动。

    原定计划是下午三点到五点去参观广州腾讯 TIT 大厦(我要冲 Q 币!),掐表一看也来不及了,再加上车程太长非常疲惫,就取消了这次行程。

    来到校内宿舍,我的天!这就是港科广的宿舍吗,两室一厅,有电视冰箱微波炉饮水机洗衣机。比较可惜的是房间内没有桌子,不过都这个条件了还要啥自行车。

    在校内吃了名叫 “一碗贵粉” 的米粉(点了 25 块的超大份,权当是早午饭一起吃了吧)。

    随后在宿舍里睡懒觉,一直睡到六点多。在宿舍的楼下与傅老师会和(傅老师:😅模板也能忘带?),这时候傅老师请客,让学长们带我们出去吃潮汕牛肉火锅,感谢傅老师的盛情款待!大口吃肉这一块。然后我们还去买了广隆蛋挞王的小吃,真不赖。

    晚上回去随便写了一些题就睡了。

    Day 0

    早上八点多起床,发现傅老师已经把我们的伴手礼领回来了(傅老师才是清晨告别洋流启程的沙砾),一件参赛服、一份参赛手册、一个赛博风格的鼠标。

    早上九点半到体育馆参加开幕式。一进赛场就被大大地震撼了,这舞台、这机位、这地毯、这打光,一切都是那么的梦幻。

    听到选手代表 Studying Father 的发言,我也有发自内心的共鸣。与算法竞赛结缘已经七年了,算法竞赛给我开眼看世界的机会,让我结识了许多同样对计算机科学与算法充满热爱与兴趣的好友,我得以走出长乐这样的小县城,来到福州、南京、上海、昆明、西安、广州等大城市,继续为了梦想而奋斗。

    就像 [六省联考 2017]“分手是祝愿”与“相逢是问候”中所说的:时空将你我分开,信息将你我连结。

    开幕式结束后,我们来到了场馆外合影。随后就去吃了吃港科广的自助茶歇,实在太爽!随后又去场馆旁边的 GYM 里逛了逛,那叫一个气派。中午十二点半来到了餐厅,造了一顿麻辣烫。

    下午两点就来到场馆内进行热身赛,来到座位,发现对面是复旦的队伍、右边是西北工的队伍。好家伙,都挺强的。

    开场看到 B 题就发现这个题目是去年 CCPC Final 的签到题,犹豫了十几秒钟,直接上机开写。发现我好像是第六个 AC 的(马后炮地说,早点上说不一定可以抢到一血)。

    接下来队友也发现 C 是签到交互题,就直接上机写。与此同时我去读 D,不知为何我的理解重定向成了 “每次将两个相邻的数合并”,将这个题看成了一眼秒的签到题。后续和队长说思路的时候我才意识到想错了,实际上根本没有 “相邻” 的这个限制。不过看对了题意之后队长也是马上自己单开了,很牛逼。

    接下来的时间都在攻坚 A 题,不过确实不会做。赛后才得知 A 题是去年 CCPC Final 的 A 题,只过了 12 个人。看来还要继续加训难题啊。

    在这期间,小青鱼从我们队的后面路过。那一瞬间我好想起身和他一起合个影,结果还是胆小的心理主导了我的身体(啊啊啊你怎么能这样)。现在想想可真是后悔。希望以后还可以与小青鱼相见。

    晚上五点半来参加 Debug the Night:音乐派对(音趴)+自助餐,实在太爽!我炫了好几只的白切鸡。有点可惜的是我们队是在二楼吃的,如果在三楼(音趴举办地点)吃的话,说不定我会自告奋勇地上去唱一首呢。

    晚上傅老师带着 FZU 以前的大神学长学姐们(2020 ICPC World Finalist 学长-李进,2020 ICPC World Finalist 学姐-吴媛媛,2021 ICPC World Finalist 学长-郑晨阳)和我们队开了一次座谈会。收益颇丰,能回忆起来的一些内容有:

    Q:如何更好地管理机房?管理机房可以有哪些内容?

    A:平时需要挂日常 / 周常的训练给大家做,要调动机房同学学习的积极性。平时的总结与反思也可以挂出来供大家交流参考(以前 FZU 是有一个 wiki 专门来存放总结的,现在正在进行恢复工作中)。

    Q:如何引导一些基础薄弱的同学们?如何给他们指一条明路?

    A:实际上不需要给基础薄弱的同学们过多的引导,需要让他们自己去摸索与尝试。平时训练的时候,只需要告诉大家金银铜分别是什么表现,让大家对自己的目标有数即可。

    Q:我在写代码的时候有一种强迫症,我老是想追求把代码写的很漂亮,请问这种心理是否有问题?

    A:没问题,这或许是一件好事。一般来说写的漂亮的代码准确性都比较高,尤其是在写数据结构或者模拟类题目,代码的模块化、封装化、可读性就显得尤其重要。你学姐曾经写了一个 350 行的数据结构题,过编译后一个 bug 都没有就过了。

    Q:去年的 EC Final,从现在马后炮地来说,那个 L 题实际上并不难,仔细想想就可以看出这是个势能线段树的题目。但当时我完全被题面以及榜上个位数的通过数给吓到了,场上如果遇到这种疑似歪榜的题目要如何处理呢?

    A:这种题目一般都是金牌题往上的难度,如果这个题目的类型是你们某个人专门负责训练的题目类型(例如数据结构),那就是完全有机会可以开出来的题目,一般来说封榜前有十个队伍通过的题目都是可以开的。可以尝试去开。

    Q:如何更好地冲击成绩(例如金牌甚至 WF 出线)?

    A:(承接上一个问题)后期题需要各个队员分模块地进行训练,一般来说可以分为动态规划、数学、数据结构的三大类,尽量去做自己所负责模块的难题,才可以提高队伍的上限。前期题也需要分工合作解决。

    晚上回酒店,简单整理了一份临时模板,让李进学长帮忙打印了一下,万分感谢!而后随便写了一些题就睡了。

    Day 1

    早上九点开场,开场从后往前开了一些题,发现都不太可做。

    十几分钟的时候有队伍开出了 G,于是就转去看 G。不过我的 G 题也实在是想的太歪了,我一直在想如何合并两个非 11 连续段,和正解完全不沾边。随后又跟榜看了一下 C, F 题,但都没什么很好的思路。

    队长观察出了很重要的性质:当序列乘积超过 2×1052 \times 10^5 时,最优决策一定是将头尾的 11 过滤掉以后直接将序列相乘。

    于是队长便上机写,陆陆续续有一些小 bug,到最后静态调试的时候,突然想起来周四 vp 的时候队长也干过 const int N = 5; 的事。看了一眼模数,好家伙,怎么写成 const int p = 2e5 + 5; 了?实在难绷,改了之后于 00:58 通过。

    C 题也是被类似构造的题意给吓住了,实际上最后一次操作的限制是很强的,从这一点入手问题就迎刃而解了。可惜当时没有观察到。队长一眼就秒了。于 01:18 稳稳通过。

    接下来在开 F,我的 F 题也一样歪的离谱。我一直在想给定一个状态 SS,到底会生成出什么样的状态 TT。队长一句从左往右考虑直接点醒了我,是啊,应该考虑给定一个状态 SS 和状态 TT,要如何操作才可以使得 SS 变成 TT,此时就可以从左往右地考虑,类似一个匹配的过程。

    于是考虑设 f(i,j)f(i, j) 表示考虑到了 SS 中的前 ii 位,已经激活了 jj 个磁铁时的方案数。

    此时发现若 ii 没有被激活,则 ii 在 TT 中对应的位置 p(i,j)=i−k+2jp(i, j) = i - k + 2j,随着 i,ji, j 的增大而增大。故新状态的对应位置一定比旧状态更大,故我们只需要保证两个相邻的对应位置之间没有 1 即可完成转移。

    不过此时队长却抛给我一个问题:那 ii 被激活的时候你要怎么考虑呢?此时 p(i,j)p(i, j) 的公式不就失效了吗?

    想了一会,突然灵光一闪!吾有一计:你把他当成 i−k+2ji - k + 2j 不就好了,仍然不破坏单调性啊。

    队长表示很可行,于是就放我上去写。写的居然出奇地顺利,不是哥们,怎么过编译后一个 bug 都没有,调都没调就直接过了(02:43)?怪不得老傅赛前带我们见学姐,原来是让我们接一接学姐的超强码力呀!(小趣事:赛后补题的时候重新写了一遍,调了好久好久才过 …)

    在此期间队长和队友交流了一下 H 题,队长还是觉得不太稳,就让队友再多磨一会。此时我示意队长 L 的一血一小时以内就出了,说不定可以开。

    我的 L 题也是想的很歪,没有好好读题还以为 KK 是给定的,队长提醒我 KK 仅仅是为了约束回答在 int 范围以内而已。想了一会,队长认为对边分治不如直接对链进行分治。队长问 “均匀随机的树的直径长度是什么级别的?”,即答 “O(n)\mathcal{O}(\sqrt{n})”(曾经刷 EI 大神的博客看到的),队长大胆猜想一个点到与其最远距离的点的距离也是 O(n)\mathcal{O}(\sqrt{n}) 级别的,每次取出这样一条最长的链进行分治,每一层分治的规模 ss 都会变成 s/s=ss/\sqrt{s} = \sqrt{s},平均迭代 66 次就会变成 s=1s = 1。

    于是哐哐开写,于 04:07 一发 AC,非常牛逼!

    接下来的时间我和队长开了 B 题,推了一些朴素的结论。没时间再去讨论那么多,把已经想到了的东西写了出来,最后也确实过了样例。很可惜 WA 了,也许还有一些情况没讨论清楚。

    队友的 H 题也没来得及写完,比较可惜。


    和上次 EC Final 一样,再次铜首。不过这次是铜首第五名,距离银牌线更进了一步。

    回顾这次比赛,我的发挥简直可以说是灾难。思维上,想了三个题目三个题目都歪了。实现上,也没有多多上机实现解放队友。思维还需继续磨练呀!队友指出这可能和我平时自己思考的时间太少有关,以后的训练我要尝试思考四十分钟或一小时以上再看题解。路漫漫其修远兮 …

    颁奖结束后,我看见哥哥(jiangly)还留在座位上,我十分想要留下和哥哥的合照(也许这是哥哥最后一次正式赛了 TAT,小青鱼也是同理),我走到哥哥的座位前方,羞涩又一次主导了我的身体。不过队长一直鼓励我 “去吧,快去,快去”,我终于鼓起勇气!

    “哥哥 …… 我可以和你和张照吗?……”
    “可以。”

    看到平日里那遥不可及的偶像,居然真的站在我的右侧,摆出大拇指与我一起合照。再多的词语也难以描述,这就是青春!(写到这里的时候真的忍不住热泪盈眶,真的太感谢哥哥圆梦)。

    晚上去吃了韩国烤肉自助,感觉再吃下去真要成为大卫带了。不行了,真该减减肥了!


    偶然间翻到我的第一篇游记CSP2019 游记的这样一段话:

    有意思的是在饭店里遇到教练与省里的各位教练聚在一起侃侃而谈,以及身后一桌的 OIer 聚在一起互膜/膜某人/装弱还是挺触动我的,就觉得,无论未来的路怎么样,也要坚持学 OI。

    无论未来的路怎么样,也要坚持学 ACM。

    I wanna rage my dream!