SYSUCPC 2024, Final 游记

· · 生活·游记

SYSUCPC 2024, Final，全称 Sun Yat-sen University Collegiate Programming Contest 2024, Final，即中山大学程序设计竞赛决赛。

名字怎么那么正式……

高中连打星都没有，是非正式选手。

队伍阵容：

最后还是 2021cyq 和 qczrz6v4nhp6u 把我带飞了。

Day1

注：Day1 指 2024 年 12 月 22 日，即比赛进行当日。

坐大巴去中大。

带了词典和若干其他纸质资料进去，结果除了词典什么也没用。（允许带纸质资料，试题为英文，三人共用一台电脑，考试开始时每人下发一份纸质题面）

由于我写代码没有另外两名队友快，于是 2021cyq 坐电脑位，我负责看题。

省流：比赛时间线如下。（可直接跳转至成绩截图处）

上午 9:00，比赛开始。

首先映入眼帘的是 A 题，名叫 Anniversary Celebration 的那道题目，尽管标题里就有一个不认识的单词（anniversary n.周年纪念日），但是我还是顶着巨大的压力决定继续看下去！

发现题面中基本没有更多生词，我又变得更加自信起来了，于是我很快看完了题，并发现了关键结论：每个字符串 SYSU 中有两个字符 S，但是只有一个字符 Y 和一个字符 U。

有了这强有力的结论，我转而看向题目的要求：有 x 个印有 S 的气球，y 个印有 Y 的气球以及 z 个印有 U 的气球，问最多能组成多少个印有 SYSU 的装饰物。有了结论，那么问题就应该迎刃而解了，终于，在与 A 题鏖战了 30 秒后，终于得出问题的答案就是一个简洁的数学式子：\min(\left\lfloor\frac x2\right\rfloor,y,z)。

我赶快把这个重要结论告诉坐在电脑机位上学习 Visual Studio Code 使用方式的 2021cyq，他表示马上就写，于是我们队就这样在约 3 分钟的时候通过了我们队的第一题：A 题。

而后我们转观排行榜，发现排行榜上居然找不到我们的队伍！

最后我们发现，其实我们是高贵的非正式选手，不愿在排行榜上露面。

无论如何，比赛还是要继续打的。（更何况每过一题就有志愿者来给你插一个对应颜色的气球）

于是我顺着顺序看到了 B 题，那超现实的题记以及题面插图的写意色彩都让我对这题产生了敬畏之感，最后我还是选择了跳过这过于厚重的 B 题，转向 C 题。

看到 C 题，经过仔细阅读题面，我立刻得到了一个可行做法：\underset{\texttt{set}}{\text{平衡树}}，但 2021cyq 让我去看 E，于是我又仔细研读 E 的题面。

发现 E 题属于博弈论，而且还是反常的非公平组合游戏，再结合排行榜上超高的通过率，我发现了关键结论：Alice 在第一步就把 0 取完，而 1 还有剩余的情况下，Alice 可以保证必胜。

有了这强有力的结论，我转而看向题目的要求：Alice 和 Bob 轮流操作，不能操作的人赢，求出在两人都以最优策略决策最后的赢家。有了结论，那么问题就应该迎刃而解了，终于，在与 E 题鏖战了 200 秒后，终于得出问题的答案就是一个简洁的充要条件：答案为 Alice 当且仅当字符串的最左端和最右端不全是 0。

我赶快把这个重要结论告诉坐在电脑机位上看榜的 2021cyq，他表示马上就写，于是我们队就这样在约 15 分钟的时候通过了我们队的第二题：E 题。

我于是让 2021cyq 去写 C，然后看榜发现 D 题过得比较多，但是我刚想去看 D，此时 qczrz6v4nhp6u 突然问我 K 题怎么做，并讲给了我题目大意。

在我想题的功夫，2021cyq 突然发现 \texttt{set} 根本不支持查排名，于是嫌手打平衡树麻烦就把 C 搁置了，然后开始摆烂。

我仔细思考，发现了关键结论：可以枚举差值再利用容斥原理计算方案数。

有了这强有力的结论，我转而看向题目的要求：求所有 n^m 个值域为 1\sim n 的整数且长为 m 的数列的极差的平方和。有了结论，那么问题就应该迎刃而解了，终于，在与 K 题鏖战了 100 秒后，终于得出问题的答案就是一个容易计算的数学式子：\sum_{i=1}^{n-1}i^2(n-i)((i+1)^m-2i^m+(i-1)^m)。

我赶快把这个重要结论告诉坐在座位上破防的 qczrz6v4nhp6u，他表示马上就写，然后把 2021cyq 从电脑机位撵了下来，于是我们队就这样在约 33 分钟的时候通过了我们队的第三题：K 题。

然后 qczrz6v4nhp6u 去看 G 题了。

另一边，当 qczrz6v4nhp6u 开始写 K 题的时候，我继续看 D 题。

发现 D 题背景与图论关联比较强，但是好像实际上和图论没什么关系，通过观察题目的要求，我发现了关键结论：对于单个答案的求解可以将那个节点定为根，并使用树形 DP 在线性时间内解决。

有了这强有力的结论，我转而看向题目的要求：对每个节点分别求解答案。有了结论，那么问题就应该迎刃而解了，终于，在与 D 题鏖战了 500 秒后，终于得出问题的答案：换根 DP。

2021cyq 告诉我让我写，于是我马上去写。

我很快就写完了，但是过不了样例，此时 qczrz6v4nhp6u 似乎对 G 题很有见解，说是分块，于是他将电脑位抢了过来，然后开始写 G 题，我本想将 D 题代码打印而后眼查错误，可惜打印功能用不了，志愿者称“这是一个普遍问题，目前正在尝试修复”，此时比赛已开始 60 分钟。我没有办法，于是把代码分屏，我在电脑旁边观察代码的错误。

我不久就发现了代码中的一个错误，将其修正后还是过不了样例。又过了一会儿，我实在看不出错误了，于是抢过 qczrz6v4nhp6u 的电脑位，开始调样例。

qczrz6v4nhp6u 就开始了对 L 题的思考。

熟悉完 Visual Studio Code 的调试方式，又调了一会儿，突然听到 qczrz6v4nhp6u 声称已经会了 L 题，但是 2021cyq 将我的电脑位抢了过来准备写 L 题。

我没有事情做，于是又仔细地思考了 L 题。

我听 qczrz6v4nhp6u 说 L 题需要拆分质因数，然后对每个质数单独处理，我却发现似乎不是很有必要。经过仔细观察，我发现了关键结论：可以先将每一列填满，然后再判无解，最后再在主对角线以及主对角线的延伸的位置填上每一行的需求的数。

有了这强有力的结论，我转而看向题目的要求：已知 n\times m 矩阵每行的 \text{lcm} 以及每列的 \gcd，求一个合法的矩阵或判断无解。有了结论，那么问题就应该迎刃而解了，终于，在与 L 题鏖战了 300 秒后，终于得出问题的答案：将 n=1 和 m=1 特判过后直接执行结论就一定正确。

我赶快把这个重要结论告诉坐在电脑机位上筛质数的 2021cyq，他表示马上就写，于是我们队就这样在约 91 分钟的时候通过了我们队的第四题：L 题。

当然，在 2021cyq 写的过程中，我也在一直看我的 D 题，但是一直看不出有什么错误。

在 2021cyq 通过 L 题过后，qczrz6v4nhp6u 又夺过电脑继续写 G 题，2021cyq 则是开了 F 题。

又过了几分钟，我终于发现了 D 题代码中的小错误，于是我抢过电脑位，将其修改，再测样例发现过了，于是我们队就这样在约 100 分钟的时候通过了我们队的第五题：D 题。

然后 qczrz6v4nhp6u 又夺过电脑继续写 G 题，我加入了 2021cyq 看 F 题，结果 2021cyq 说还没看懂题意，我只好自己看题。

发现是字符串题，而且似乎由三个部分拼接而成，第一部分是求解出现次数最多的非空子序列，第二部分是将第一部分的所有答案按一定方式输入文本框并求解最小操作步数，第三部分是每次修改一个字符，然后求解第二部分的答案，将这个抽象的题意告诉了 2021cyq，于是我们一起想这道题。

不久，我发现了关键结论：第一部分的答案一定是若干个互不相同的出现次数最多的字符拼接而成，因为字符集 \Sigma=26，所以这一部分是容易的。

有了这强有力的结论，我转而看向题目的要求：支持 10^5 次修改，每次求出第二部分的答案。有了结论，那么问题就应该迎刃而解了，终于，在与 F 题鏖战了 600 秒后，终于得出问题的答案：第二部分的答案就是每个首字母最长答案串的长度总和的三倍再减去最长答案串的长度，第三部分是用来诈骗的，每次修改暴力 O(\Sigma^2) 求答案即可。

我赶快把这个重要结论告诉坐在座位上的 2021cyq，他表示马上就写，然后将 qczrz6v4nhp6u 从电脑机位上赶了下来，于是我们队就这样在约 132 分钟的时候通过了我们队的第六题：F 题。

2021cyq 写完 F 题以后，qczrz6v4nhp6u 又夺过电脑位写 G 题，我则是开始回顾我们队做过哪些题，哪些题在任务列表中，哪些题没看过，以及气球的分发情况，然后开了 J 题并发现了初步结论。

过了一段时间，qczrz6v4nhp6u 表示 G 题写完了，然后交上去，领取了一发 WA。qczrz6v4nhp6u 在自称为“甲级战犯”的同时开始给 G 题挂拍。

又过了一段时间，我突然发现 C 题的一个关键结论：不用写平衡树，只需在 0 号队伍每次切题前后暴力统计排名即可。

我赶快把这个重要结论告诉坐在座位上的 2021cyq，他表示马上就写，然后将 qczrz6v4nhp6u 从电脑机位上赶了下来，于是我们队就这样在约 178 分钟的时候通过了我们队的第七题：C 题。

在 2021cyq 写 C 题的时候，我又瞄准了排行榜上通过数最多的 J 题，有了初步结论作为铺垫，又经过长时间的思考尝试，我发现了关键结论：如果从高位到低位贪心地决策，那就比较可做。

有了这强有力的结论，我转而看向题目的要求：有若干个数，可以进行若干次给某个数减一的操作，在每个数都不小于给定下界的前提下最大化最后结果的或和。有了结论，那么问题就应该迎刃而解了，终于，在与 J 题鏖战了 1800 秒后，终于得出问题的答案：按位贪心，如果这位下界为 1，则填 1，如果还有这一位的“票”，则兑换为所有低位的“票”各一张，如果这位下界为 0，如果最大值这一位为 1，则这一位填 1，然后将最大值的更低位的 1 全部转化为对应位的“票”，然后将最大值删除，如果还有这一位的票或者这一位为 1 的数就兑换为所有低位的“票”各一张，如果没有这一位为 1 的数，如果有这一位的“票”就耗费一张并将这一位填上 1，如果还有这一位的“票”就兑换为所有低位的“票”各一张，如果也没有这一位的“票”，这一位就填 0。

正在我快想完的时候，2021cyq 把 C 切了，G 题也拍出来了，qczrz6v4nhp6u 又拿到电脑位，调 G 题，花几分钟调完再交一发，领取了一发 TL，最后发现块长没调回来，于是把块长改过来再交，于是我们队就这样在约 184 分钟的时候通过了我们队的第八题：G 题。

这时 2021cyq 和 qczrz6v4nhp6u 一起研究 I 题，我又到电脑位上写 J，于是我们队就这样在约 199 分钟的时候通过了我们队的第九题：J 题。

这时我们三个人一起研究 I 题，过了一段时间，qczrz6v4nhp6u 发现可以根号分治，于是让 2021cyq 写。

我又浏览了剩下的题，感觉 H 题最有可能可做，于是去做 H 题。

发现数据范围极小（1\le n,m\le11），于是考虑状态压缩，通过仔细观察，我发现了关键结论：钥匙的状态唯一确定了我能到达的节点集合，每个漏斗都是互不区分的。

有了这强有力的结论，我转而看向题目的要求：有一个起点，n 个漏斗，m 个门以及若干条双向边连成简单连通图，求 m^n 种钥匙放置方案（钥匙放在漏斗中）中使得可以获得所有钥匙的方案数。有了结论，那么问题就应该迎刃而解了，终于，在与 H 题鏖战了 300 秒后，终于得出问题的答案：设计状压 DP，求解当前钥匙的获得情况为 S，检查过的漏斗数为 x 的方案数，只要每次钦定检查的漏斗为可以到达的没检查过的编号最小的漏斗即可说明转移的正确性。

下午 1:00，封榜。

此时午餐（麦当劳）刚好送到了，于是我和 qczrz6v4nhp6u 开始吃午餐。

吃完午餐，继续看 B，发现不会，看 M，发现也不会。

此时 2021cyq 正在与 I 题展开殊死搏斗，而且刚刚喜提一发 TL，我决定等他打完再打 H，于是一直想 B，结果到最后也不会。

最后在 qczrz6v4nhp6u 的指责下，2021cyq 发现写出了若干相当愚钝的错误，并且复杂度也是假的，最后在下午 1:25 让出电脑，与 qczrz6v4nhp6u 一起商量对策，于是我坐到电脑位上打 H。打完发现过不了样例，2021cyq 表示他要把 I 先做完，于是 2021cyq 又把我赶下了电脑位，于是我们队就这样在约 288 分钟的时候通过了我们队的第十题：I 题。

压力给到我，我还有 12 分钟调 H。

花了几分钟，发现转移的或写成了与，改完就过了样例，于是我们队就这样在约 293 分钟的时候通过了我们队的第十一题：H 题。

最后几分钟在摆烂。

下午 2:00，比赛结束。

上面是后来取得的成绩截图，当时榜上并没有我们队，深绿色也不代表全场首杀，而是代表在非正式队伍中首杀。（非正式队伍只有纪中的其中八个队，纪中另外三个比较强的队则是领到了正式队伍）

然后在再次领取午餐（有一个机房的午餐多出来了，可以免费拿）以后就前往报告厅参加活动。

首先是题目讲解，发现 B 题只是一个普通的计数题，设状态后维护前缀和与二阶前缀和就可做，而 M 题是一道神秘的人类智慧构造题。另外，还有 G 题标算是 O(n\log^2n) 的拆位加线段树，但我们用了 O(n\sqrt{n\log n}) 的分块，更劣。还有，H 题标算是 O(m2^{n+m}) 的，但是我写的是 O(n3^m) 的，更优。

然后是某基金会成立仪式，包括唱国歌，唱校歌（中大校歌怎么可能会唱），以及若干领导讲话的环节，比较无趣。

而后是 ACM 优秀选手讲话，大概讲了一些有趣的个人经历，比上一个环节有趣。

最后是滚榜以及各种奖项颁发，虽然榜上无名，但还是感觉比较有趣，成绩最后也达到了金牌线（金牌线：8题，用时823）。

此时已经超过下午 5:00 了。

坐大巴离开中大。

有趣的事：

失误之处：

排行榜：