2026 GXCPC 邀请赛 游记

· · 生活·游记

前言

队友：@Cuber_26 @TangWK

榜单：https://ac.nowcoder.com/acm/contest/136164#rank
https://rl.algoux.org/collection/official?rankId=gxcpc9th

省流：rk14，邀请赛rk11，最慢8题，邀请赛金

至于为什么我们四川大学的队伍不去打SCCPC？当然是因为名额轮不到我们。

正文

我的大一第一次xcpc正式比赛。

周五晚上十一点半到凌晨一点的飞机，到酒店已经两点半了，还好队友熬夜等我不至于露宿街头（

周六热身赛，上机发现参赛手册上的环境都没配。通过群里了解到有的机房用win7，有的机房用win11，电脑配置也截然不同。我们队有幸分到win11的机房。提前十几分钟发了纸质题面，但是说是不让提前看。开始后，AB签到，CD被队友认出来是网络赛原题，讨论了一下就过了。由于热身赛电脑能联网且能看手机，rk1 15min就ak了。

到周日正赛，主办方说已经紧急配好了参赛手册上的环境。本以为能像热身赛一样让我们很早进，但是到九点整我们的机房才开始让进人，并且比赛没有延时。进去后也状况不断，我们的机子没登牛客账号（为什么要用牛客？），也没发纸质题面，只能干坐着听到几个签到题已经过了一车。并且此时电脑还是能联网，但是要求录屏。登录后，我们三个人挤着看一台机器上的题目，艰难地把三个签到ADG给做了。

半个多小时后，终于送来了纸质题面。队友开了B、F，我开J。读了题后有了简易做法，我以为也是签到，直接接管电脑开写，但是写完后发现做法被自己轻易地hack了，刚好队友要写B，我便下机继续思考。队友过了B的样例但是提交WA了，以为是精度问题于是又交了两三发卡精度，结果自然是继续WA。此时另一个队友跟我讲了他的F做法，我也觉得没啥问题，于是他上去写，也WA。我提出这F就是判个二分图，队友也修改了一下之前的做法，在72min时过了F。

然后就进入了三线卡题。Cuber调B，twk开H，我继续看J。我得出一个看上去逻辑比较正确的J做法，于是写了并提交，也WA。此时twk和我讨论H，就是个组合数dp，但是组合数是1e8级别的。我发现 h_i 范围是100，可以暴力计算，但是复杂度就是 \mathcal O(Tn^4) 的。于是想到预处理 \prod\limits_{j=l_i}^{l_i+100}j 即可 \mathcal O(1) 计算组合数，总复杂度就降到了 \mathcal O(Tn^3)，队友写了后提交，又WA。此时处于绝望的三线卡题阶段，事已至此，先吃KFC吧。队友继续处理B的精度问题，甚至搬上了python，结果是继续WA。到了三个小时，我们还是四题，看榜，已经100名左右了。

一直卡题是不可能的。队友发现H好像没处理 h_i>h_{i+1} 的情况，改了一个条件直接过了。 我此时也得出了完整的J做法，队友也发现了B的逻辑问题，于是我先来写J。我的做法：先记录amx、amn、bmx、bmn，如果amx<bmx或amn>bmn就不行，直接-1。如果满足，就先把大于bmx的 a_i 先调整到bmx，小于bmn的 a_i 调整到bmn。此时无解的情况只有一种，就是 n=2 并且 a_1=bmx,b_1=bmn,a_2=bmn,b_2=bmx，即最大最小值互换，因为一定有一个最值先调整导致另一个无法调整。因此 n\ge3 时若存在这样一对互换，就可以让剩下的某个 a_i 先调整到bmx或bmn来让所有调整进行下去，然后它再调整到 b_i，就一定有解了。此时多花的代价就是除了这一对互换之外的 \min\{|a_i-bmx|,|a_i-bmn|,|b_i-bmx|,|b_i-bmn|\}\times2。写完代码，在四发罚时后终于通过了J。队友紧接着上机重构B，五发罚时后也在封榜前通过，成为最慢的7题队，排名也来到了rk20。

我接着开了E，不难发现题目条件就是找到 a_{p_1}+a_{p_2}=b_{q_1}+b_{q_2} 的四元组，只需统计所有 a_i+a_j 的出现次数即可。由于值域为2e5，可以转化为多项式乘法，FFT优化即可。但是我已经很久没做过多项式了，只能从带的OI-Wiki资料里找模板照抄。我选了书上最短的递归版fft，写完后样例过不了，调试发现多项式乘法的结果是正确结果的32倍，于是我直接除以32，过了样例，想着反正罚时已经那么多了，直接交一发，结果依旧是WA。此时还剩半个小时，我果断换了一个非递归fft板子来抄，多项式乘法结果终于正确了，但提交后还是WA。此时队友发现 a_i=b_j 的情况是不合法的，需要统计后减去这些贡献。改了之后提交依旧WA。最后五分钟，我发现有个数组多测没清空会出问题，修正之后极限AC来到8题，最刺激的一集。

滚榜，有点担心会被卡在金线外。果不其然是最慢的8题，但是很快的6题就能邀请金，还是多虑了。

从两点半坐到五点半，终于轮到邀请赛金牌上台领奖，我第一个上台，最后一个领，结果发到我的时候，没牌子了，工作人员先给了我一个铜牌来合照。我有点生气，找主办方讨说法，他们说有个队上台了三个人领了三个金牌，到我们这就没了。跟他们掰扯半天，还是只能后面邮寄奖牌。

赛后爆出一点情况。由于牛客代码是公开的，群里发现rk1的E题写了790行，里面有整个带注释的多项式全家桶，这显然不是人类能赛时写出来的。后面了解到是他们热身赛时带U盘拷进去的，主办方没清空机器。似乎因为他们是打星队，没有进行实质性处罚。

upd：取消成绩了

后记

感谢两位学长队友带我夺金。拿到校赛和邀请赛的金牌，作为acm生涯的起点，对我来说已经是不错的结果了。