XCPC三年游记

基本是流水账，并非不能提供关于算法竞赛的前人经验，属于是长篇朋友圈了。

倒叙之前言

2021-11-28，随着我最后一场比赛ICPC上海的落幕，我的XCPC生涯也结束了。放假两天之后，有了这篇退役贴。

战绩如下吧大概：

• 2021-07-18 ICPC 沈阳 铜牌
• 2021-10-31 CCPC 女生Only 金牌
• 2021-11-14 CCPC 广州 铜牌
• 2021-11-21 ICPC 沈阳 银牌
• 2021-11-28 ICPC 上海 铁牌

最打脑壳的应该是退役场打铁了吧，不过比赛结束时，我与算法竞赛的一切故事都结束了，比起悔恨之类的情绪，更多的是一种无力和绝望感。

下面就是强校弱队、零基础、没天赋且不努力选手，我的XCPC之路。

XCPC之路

严格算来，我的XCPC走了三年。大一第二学期报了算法竞赛的选修课，然后以此为契机参与了校赛和暑假前集训。当时完全不懂算法竞赛是什么，不过我第一个学期语言课成绩很好，于是拉了另外一个成绩很好的同学，和一个高中数竞选手同学一起去打了校赛。准备校赛的方式就是自学紫书，最后我可能把紫书看到1/3左右（不过现在想来，这不是相当于完全没看吗），然后没有过校赛的初赛。不过校赛初赛的体验很好，我非常喜欢这种三个人一起努力解题的模式（虽然只是努力解出了签到题……？）。校赛失败后，我的第一个队之同学队就散伙了。

但是还是要恰分的，再加上教练传销功力nb，再加上当时我不知道从何而来的一个要打这个比赛的倾向或者说念头，于是进行了一个暑假前集训的训。我校的暑假前集训实际上是校队的第零轮选拔，其内容就是分成几大专题进行板刷。当时的我对于一些算法竞赛常识一无所知，对算法的复杂度之类可以说没有一丝敏感度。每个专题第一周放题出来，独立对这些板题进行思考，只能认识到自己的愚蠢，并且尝试用一些假做法暴艹；第二周放出题解后，学个线段树都要两天才能看懂它在说什么。

这种状态持续了两个多月，来到暑假，作为尾部选手开始了更折磨的一轮选拔。

（过题和补题情况如图，应该可以看出来有多折磨）

收获也很多，可以说锻炼了强大的抗压能力，以及逐渐上手一些常识问题：例如如何重载运算符、如何重定向文件输入输出、熟悉STL的使用、各大OJ使用等，很好奇OIer会不会也有这么一个摸索阶段。从最开始的完全垫底，只能签到，到后面可以到中下游游玩，甚至抢到过一次签到的一血。然后一轮结束就快乐回家过暑假了。感谢暑假时坐我旁边的兄弟和舍友妹子使得我的一轮集训生活没有那么压抑。

大二开学，第一个XCPC活动，校赛之趣味赛来了。作为一轮集训落榜生，在其中一场勇夺第二。奖品包括一只企鹅、一张能在综测加分的奖状、一本《编程珠玑》，以及珍贵的勇气和信心。

大二下学期，又开始暑假前集训了，也就是板刷专题时间。这时我已经基本上手了，所以没有再出现大一时那种茫然，于是开始愉快地写这些板题。不过此时正值疫情在家，加上没天赋且不努力，所以错过了最好的板刷时机，写题只是为了草草通过选拔罢了，时间都拿去卷文化课和其他一些东西了（最后还没卷出个什么名堂）。这可能是我XCPC生涯最称得上后悔的事，此时大一坐我旁边的老哥之一已经板刷到了rank 1吧大概，那么为什么我只是看着？

由于疫情，一轮选拔也是线上举行，而且由于没有办法保证公平性，所以记得似乎是没有选拔环节，大家都进入二轮开始随机组队训练。然后在开学前期通过几场线下赛进行了选拔，并且分配了队友。在集训队的新一届div2中，我仍然是尾部选手，故虽然也写了组队倾向，但是估计只能等待随机分配队友了。组队倾向里面还写了一个之前二轮随机组队时遇到的老哥，虽然是线上，但是当时一起切了一道矩阵快速幂的题，让我又体会到之前组队打校赛的快乐，于是这位老哥成为了队友之一。另外一个队友是一个雅礼的OIer，比我们两个小一届。我们组成了我的第二个队：UESTC_waterer，终于带上了校队的前缀。

随着这个队的成立，我来到了大三。组队后，由随后的几次队内训练赛记rating，并且分配区域赛名额。在包括XCPC的网络预选赛在内的几次训练赛中，作为弱队在校内被暴打。然后我意识到今年我无法打区域赛了。

还是由于疫情，校赛也没有在上半年举办。于是这次校赛我有了正式队友。上一次打校赛时止步初赛，而集训队内打校赛实际上不用打初赛，于是我单人打星了初赛。感受到了实实在在的进步，今时不同往日。不过校赛正赛摸了个二等奖（我甚至一直记得的是没有得奖，终测都没报！刚刚翻聊天记录甚至才看到）。

由于沙大大三下会把学生全部赶去实习，并且将所有课程集中在前五个学期上完，所以我开始同时焦虑找实习、卷文化课（这个学期结束所有课程，压力尤其大）以及竞赛加分（指望不上区域赛了）来拿到保研的事。对于XCPC对于保研的性价比低一事，算是有了一些初步认识。于是算法竞赛方面，可以说是完全摆了。此时心态已经调整为，等大四了再更纯粹地去享受XCPC罢。

找实习的途中，曾经在二面问过一个最长公共子序列的板题。让我现在回想，我都不敢相信我当时居然不会写。以及不敢想象在不会写该题的情况下是如何通过的面试（）。不过作为从来没有认真进行过系统训练的零基础选手，就打CF、做校队到处拉的题，确实不太能意识到这是一道如此入门、如此基础的板题。我终于深刻意识到我的算法知识到底是建立在怎样的一盘散沙上。

记得三面问了一个套着工程皮的串题，当时扯了一通建trie树、AC自动机，进行了一些时间复杂度和空间复杂度的分析。我想这些东西，如果我没有接触过算法竞赛，是扯不出来的吧大概。最后的最后，心中一块找不到实习的悬着的石头就落地了。此时对于算法竞赛的感情就是相当的复杂。一方面我的简历上此时只有趣味赛和一个水赛（或许有人听说过赛氪）的奖，一方面我切实使用算法竞赛学的知识找到了实习，拿到了第二个企鹅，比当时趣味赛发的那个精致了许多。

寒假集训也是记rating的，我们队仍然被暴打。不过最后一场有两个大模拟题，其中一个大模拟是另一个大模拟的checker，我上去一通暴艹给一并AC了，只记得打得很爽，这场排名比较高，不过总的rank上仍然没有什么变化。集训结束的晚上，就收拾收拾连夜飞去实习了。

实习的第一天吧大概，晚上打开CF看了眼比赛安排。于是就被同样打XCPC的隔壁工友发现了。工友来自SZU，一边上班，一边继续XCPC，是名副其实的大四追梦人。工友的水平比我高很多，实习期间看老哥时不时有比赛打，心里暗暗下定决心，我大四也要继续XCPC。

大三下，也就是实习的这个学期，有两个算法竞赛相关比赛，都是可以保研加分的。天梯赛和蓝桥杯。天梯赛可以去三个队，一个队10个人，校队按照CF rating上人，但是我是第31还是32位吧大概。于是我报了蓝桥杯以求能有书读。蓝桥杯的省赛和新一年的校赛在同一个周末，此时UESTC_waterer已经分崩离析，其中一个队友已经决定退役，雅礼学弟和别的缺人的队打校赛去了。于是我回到成都打蓝桥杯，但只是在学校散步时想到他们正在校赛，仅此而已。

蓝桥杯省赛，属于是OI赛制，弥补了我高中没有接触过竞赛的遗憾。在高一的时候，就听考到绵阳的同学讲了她们那边有信息竞赛，而老家的高中实在是没有这个条件。省赛就在沙大的机房中举办，而我旁边与我相隔一个python选手的另一个cpp选手竟然是大一暑假集训时坐我后面的好兄弟。打完了之后和老哥交流了一下做法，让我回想起高中时每次文化课考完也是这样和同学们交流题目做法，让我想起在CSP和NOIP打工时看到中学生们走出考场/赛场后的样子，有一种跨越了时间实现愿望的满足感。

回到工位，在普通的一天，队友突然带来一个消息：我们有区域赛打了。与此同时，蓝桥杯省赛结果也出了，妥妥的省一，国赛拿个奖，保研加分就有了。一时间心潮澎湃。后来蓝桥杯国赛只是拿个了国三，对于保研来说足够了。

好，于是开始备战我的第一场，也很有可能是最后一场区域赛：沈阳ICPC2020。最初打算在五月底进行，五一小长假我们远程训了四场，另外我也准备提前请半周的假回学校狂训几场，机票都买好了，跟Mentor也讲好了请假，就差填系统了。然后就由于疫情延期了。

同时，今年轮到我们这一届来准备暑假前集训的题目了。队友此刻水平已经今时不同往日，是DP专题的负责人，我由于觉得学DP对找工作很有用（），于是也选了DP，出了五道板得不能再板的DP题。这段时间就是一个007的概念，白天打工，晚上给校队打工，走在路上都在想题面怎么写，自己还要抽时间训练补题备战区域赛。

沈阳延期到2021-7-18，我在前一周离职，连夜回到学校，无缝衔接暑假一轮集训。我原本以为这是我的第一场也是最后一场区域赛，直到我被告知有队缺一个人。于是我和我的第三个队：UESTC_shoegazer一起参与暑假集训，而waterer的队友也已经重新组队，并和新的队一起参与暑假集训，我们将分别继续我们的XCPC之路。

白天是在各自的队被多校、火车轮流折磨，晚上作为waterer抓紧继续训别的场。一周后我们到达了沈阳。到达沈阳后，正赛前两个晚上也在继续训，在热身赛做到一道前几天才训过的原题，感觉良好。

竟然能打现场赛，周围不少强队，氛围很好。我们的目标是保铜争铜吧大概，因为铁牌不予报销（）。开场签到挺快，但是第二个签到太急，交了个假做法导致+1，冷静下来之后也顺利过了。继续跟榜，看到有两三道题都有队比较快过了，我们三个就也开始开这几道题。后来才知道，其中一道是FWT，另一道是推柿子，再另一道是打表+dfs剪枝。可以开的程度递增，因为当时我们队根本没一个人会FWT，也没人会推柿子，不过姑且可以一试。打表题是最为离谱的，我们打了表，发现了一点点规律，甚至已经试图交dfs+少量剪枝，不过本地大数据就没跑出来，于是放弃了（而且当时判断有误，并不觉得这是正解，于是大家继续推柿子）。

事实上这场有三道签到，还有一道在3h我们试图再看榜时才初现端倪，是一道题面占了一整页的，套了个机器学习皮的阅读理解题。我们没人会专业知识，于是看了半天，纯看样例猜了想让我们干啥，一通写，终于签完了到。然后就继续罚坐了。

封榜对心脏不好。本来都以为铁了，最后还是摸了个铜，开心得不行。现场赛颁奖氛围很热烈，甚至还有一些我不好说的乐子，不过退役贴上就不过多去嘴别人了。最后的最后，我们把牌带回了学校，然后UESTC_waterer正式解散。

UESTC_shoegazer是由两个沙大准大四生（我和另一个老哥）和一个计院准大三学弟组成的弱队。不过学弟似乎学习能力过人，在天梯赛选人的时候，他也是那个rank 31/32的人，而现在已经在黄名附近试探几次了。我打CF却完全不行，手速和智商都跟不上，导致都退役了还没过进队线（）。

div1的暑假集训会覆盖整个暑假，由牛客多校、hdu多校、开火车、申必题目互测组成，基本就是坐牢、坐牢、坐牢、轻松地坐牢。于是我们做了一整个暑假的抗压训练。多校和火车的题目，基本只有签到题是会的，别的都像是全新领域，特别是数学题。我仿佛回到了大一被一轮选拔折磨的时光。直到XCPC的几场网络赛和随后的国庆集训，我们还是继续被折磨，由于终于合场，div2的前排队伍也开始暴打我们。

不过这段时间却是我最快乐的时光。白天打多校或者别的什么抗压，晚上补题或者学习到十点半赶在机房楼和宿舍关门前回去，一周放两天假也在位置上补题。除此之外，队里每天都很欢乐全是二次元，太爽啦.jpg，苦中作乐，抗压很成功呢。

开学后就没有多校打了，大三队友还要上课，于是我们一周训三场，开往年的区域赛，中国的打完了打别的地方的，区域赛打完了打多校。开学后我就没有机房这边校区的宿舍了，只能坐校车通勤，大概花在校车上的钱现在也有五六百了（）。没有VP的时候，就在机房默默补题和学习新科技，毕竟机房设备齐全可太爽了。在机房的时候，会看到别的队伍也一样在坚持训练，包括div2的后排队，而我此刻才意识到，我在waterer的时候，可从没有这样主动学过，也是有比赛打了才知道赶紧训几场。既没天赋又不努力，就是这样的。

但是此时想这些也没用了。第一个正式赛名额很快就来了，不过并不是shoegazer的，而是CCPC的女生专场。校队刚好凑出三个妹子，于是我们就上了，这是我的第四个队：UESTC_姐妹花了属于是。这个队由一个大四学姐（我）和两个大二学妹组成。比赛前一周拉了一场往年的多校训了一次，就算磨合了。

于是2021-10-31的早上9点，我们开始打这场奇妙的比赛。由于签到题太多，开场就是三个人轮流签到，签了五道题后终于停了下来。罚时相当优秀，此时排名来到了我想都不敢想的rank 2，感觉一旁的志愿者大哥吹气球都吹麻了。然后竟然就开始罚坐了。接下来可做的是一道貌似状压DP的题，和一道串题。我对串题实在是没什么见解，就想了半天DP，不过复杂度怎么想怎么不对。此时学妹说想乱搞一下串题，上机一通操作串题就过了她说乱搞...可不是乱搞的.jpg。压力来到我这边，我觉得这状压根本不可避，不过一通分析发现有效状态数应该没那么多，于是每次转移时搞了一些去重和去无用状态的操作，也过了。此刻金牌区已稳，斗志已然丧失，其他的题也开不出来，于是开始聊闲天了。不过学妹看另外一道串题，又想乱搞，但是怕被卡hash，上了双hash，结果到最后也没调出来，事后知道是正解，但是不用双hash她说乱搞...可不是乱搞的.jpg，很可惜。最终rank 13拿了金。更前排队伍竞争很激烈，但是我们也开心地拿金跑路了，UESTC_姐妹花了属于是的故事也结束了。

然后UESTC_shoegazer的比赛日程表也有了，由于疫情原因，各个赛站都搞成了网络赛，所以原本只有一个ICPC名额的我们队可以打两场了（如果早知道第二场会铁…）。我们报了CCPC广州，ICPC沈阳和ICPC上海。

2021-11-14早上9点，CCPC广州开始了。为什么CCPC在早上9点这么个阴间时间。不过这些都不重要，重要的是有比赛打。开场签到顺利得意外，签完到后进入了金牌区，然后开始轻松地开银牌题——吗？为什么下一道题上汇聚了“仙人掌”、“计数”、还有一个完全看不懂想表达什么的式子捏？队友试图解开式子里的玄机，我去开其他题了。

读了一些别的题，只能说完全不可做。学弟喜欢串题，虽然整套题中唯一有串的题实际上不是一道串题，不过他们一通讨论觉得可做，就冲了，直到比赛结束。我看着仙人掌题的过题数越来越多，心里面很疑惑，这么多队都会仙人掌计数？封榜前还在银牌区中部呢，我此时已经默默接受了三题银的设定。不过最后其实铜了，大受打击。发现抗压训练还是做得不够，以至于被膈应得两天睡不着觉，没事就上知乎看看大伙怎么骂，写了巨长的参赛游记，以及对斐波那契数列产生了阴影，那几天的感叹词都变成了卧槽，斐！。

2021-11-21早上11点，ICPC沈阳开始了。机房里又来了一个熟悉的人，这不是waterer的前队友吗。确实，我们分别在两个队，但又在新一年都打沈阳站，复仇场了属于是。另外这些人找到规律了吧大概，题目是电竞相关的就是签到题，总之快速签完了道，然后开始开铜牌题。铜牌题我一道，队友一道，虽然经历了抢机位，不可避的罚时等等也都顺利开出来了，然后又开始罚坐了。起先过题最多的其实并非银牌题，不过成功地把我们骗去死磕了，想不出来，其中一道串题，学弟在我们罚坐的时候上机敲了很久，结果做法假了。直到快封榜的时候，注意到H过题人数暴涨，学弟放弃敲串题，三个人合力对H一通分析，最后我终于猜到了结论，大家合计确实没问题后，给赛前连续敲了几天图论（甚至前一天晚上回沙大的路上还在讲一些奇妙图论算法）的图论大师队友以最快的速度把这题给敲出来了。最后凭借比较快的反应和比较快的跟榜速度银尾了，开心得不行。

于是感觉我们已经成为保银争银队了。其实CCPC广州情况比较特殊，毕竟确实有很多前排队伍被那个诡异的组题区分到大后排，而且我们是感觉其他题可做所以没手推仙人掌，等等，找了一堆理由给打铜。几次训练赛都打得不错，其中VP今年第一场桂林CCPC甚至是银首（要不是队友数组开小了就金了？），VP了几场往年多校，至少比今年多校打得好很多了。于是非常乐观，来到了上海站。

2021-11-28早上11点，ICPC上海开始了。开场签到不太顺利，第二、三道签到都+1。于是签完四道题，已经在银牌区后侧了。我意识到如果之后出不了题，会铜的。开始跟榜，把此时有人过的题都看了一遍，并且三个人都没有思路。不过三小时左右，H过题数开始大幅上涨，于是冷静分析，口胡了一个离线的策略，觉得这样能保证在整张图$O(n)$了，然后我自己还没搞懂，学弟就会写了，于是上机。我大喜，觉得这下该银了，于是开始开别的题。此时学弟发现之前想的写不了，必须要加一个启发式合并，并且又想了另外一个离线策略，并且严格证明了他策略的正确性。也就是说，虽然很波折，但还是开出来了。于是我和另一个队友继续开别的题。我比较喜欢B题，于是打了表看了半天，只发现和形成的环的形态有关，队友试图人肉拟合出某个式子也失败了，于是去揣摩M的题意了。

然而，离线+启发式合并，直到比赛结束我们也没有调出来，WA完了，不知道错在哪。眼睁睁看着从银逐渐掉到铜，掉到铜尾，然后封榜，我就知道了，八成要铁了。后来才知道这套题还有构造，但是最初跟榜时还没有浮现出它的可做性，我向来是神经兮兮猜结论的类型，总觉得构造题我能搞（事实上也真的搞出过很多申必构造题），也挺无力的，发现B我们不可做的时候已经太晚了。

作为退役场，发现自己铁了的时候异常地平静，被无力和绝望包裹。我知道这场比赛结束后，我和XCPC的所有故事就立刻结束了，在此之后，思考没有意义，分锅没有意义，反思没有意义，学习没有意义，补题没有意义，改进没有意义。因为一切都已经结束了，我不会有下一场XCPC了。当天晚上，恰了火锅，然后UESTC_shoegazer也解散了。回沙大的路上，用打铁是ICPC的一环、集齐所有颜色的牌之类的无意义语句使自己平静。不过终究是结束了。

三年XCPC，其中有效时间满打满算也没有一年。平衡算法竞赛和卷别的东西的时间确实太难，直到今年暑假尘埃落定，到ICPC2021上海站之前，这段不到五个月的时间是最纯粹、最充实的，当然也是进步最大的。最后在各个区域赛能拿到这样的结果我已经相当满足了，不能算是含恨退役。

题外

退役前一天晚上，聊闲天的时候提起为啥来你校，为啥来打这么个比赛。我努力回想后，发现很可能是因为校队一个拿过金的学长曾经到高中班上宣讲，使得我隐隐产生了这么一个倾向，不过都快退役了我也并不知道他到底是谁，然后对着Lutece的Honor在OIerdb上一顿查，未果。