SCCPC2025 游记

· · 生活·游记

书接上回，停课的最后一周居然有惊喜，可以外出游玩打比赛。不过这次比赛似乎与高考时间重了，不知道有没有人放弃高考来打 SCCPC，那可太有生活了。

Day 0

今天高考开始了，学校里除了我们信竞就没有其他人了，感觉我们信竞就像打仗时殿后的队伍一样，颇有种英雄的感觉。

上午一直在做网络流建模的题目，感觉网络流的紫题太简单，黑题又太难，就没有难度适中的题目吗？

后面就出发去乐山了，话说高速路上乐山方向的出口怎么这么不明显，直接就错过了，害得我又多走了 \infty 分钟。后面听说 xjy 他们也错过了那个路口，真是太有默契了。

到乐山就开始吃吃吃，这钵钵鸡确实比学校里的正宗多了，特别豪赤，感觉学校里的那一个顶多算红油拌野鸡，不过总觉得味道还是有点不够，可能是口味太重了。

下午有试机赛。这还是我第一次参加这种有试机赛的比赛，不过确实试机赛很有必要，光是配置 VSCode 就花了 20 多分钟（大雾，甚至还没有配置好，遂红温，直接不用 VSCode 了，小熊猫启动！

光速过掉了前两题，然后 xjy 说第 6 题就是个板子。于是就把电脑然给了他，我和 yt 都去想自己的题目了。话说这个第 3 题感觉有 10000 种方法，我怎么一种也想不出来。突然 xjy 跟我说把第 5 题写完了，但是不知道怎么写挂了，我一看，奶奶的，谁家好人子序列写 SAM 啊？于是先放掉了，这时 yt 又说他第 5 题有思路了，于是又把电脑交给他，我继续想第 3 题，终于想出来了，这道题只需要把所有数字拉出来放到一个序列上，再给每个数的颜色设置成它的行号，每个数向比它小的且和它颜色不一样的数连边，最后倍增优化一下不断往前跳就行了。这时 xjy 也想出了第 4 题的网络流写法。结果 yt 一直霸占着机子改第 5 题，但是直到最后也没改出来。这真是一种奇妙的体验，一道题自己已经想出来了，但就是没法写 qwq。

感觉我们大家都很唐，明天不要再这么唐了。

晚上去吃跷脚牛肉，感觉触发了第三次世界大战一样，大家都疯叉叉抢肉吃，甚至脑花刚下了 5 分钟就有人准备要吃？？？？结果抢的太激烈了，我直接一伸手抢到炭火盆上了，于是直接强制退出竞争，拿冷水冲去了。话说火锅的毛肚，牛肉不都是放在冰上的吗，怎么会放在炭火盆上呢？干脆直接吃烧烤算了。

晚上玩了一会 Switch 就去睡觉了，话说为什么这次大家都这么早就去睡觉了，可能是爸爸妈妈都在吧。

Day 1

比赛日，rp++。

开题，发现 I 题似乎是一个广义 SAM 的题目，刚想找 xjy 看一看这道题目，忽然发现这道题目已经有人过了，再一看发现数据范围小的可怜，直接暴力就做完了，被诈骗了，赶紧敲了个字符串哈希就过了，听说很多人哈希都被卡了，还好我用的是 5201314 为基数，没有被卡 ^w^。

后来 yt 又过了两道签，然后 xjy 说第一题是个最小乘积模型的板子就去敲去了（感觉莫名很熟悉，不过这 xjy 没有读错题了），同时 yt 又会做 J 题了，开局很好。

这时 yt 说 G 是一道数学题，我可以做一下。于是我就开始看 G 题了，这 G 题一看就很不好做，拆了半天斯特林数拆不动了，细看一下才发现这不就是个范德蒙德矩阵吗？这个东西 zhr 寒假才给我讲过，但我基本上把它忘了，我只记得它的行列式比较特殊，而行列式再加上代数余子式就可以求逆了，但我把代数余子式求逆的方法也忘了，难绷。于是把 yt 叫了过来一起推范德蒙德矩阵的逆。这一推就是两个小时，算错了 \frac 10 次，终于推出了式子。感觉和容斥非常像，就是加上每一个数，减去任意两个数的乘积，加上任意三个数的乘积……

我突然想到，四川省集第 1 天第 3 题，我也推出了类似的式子，当时不会做，后来 yt 跟我说这相当于是至少一个事件发生的情况数，那么把每个时间都不发生的情况数算出来，再用总情况数减去就可以了。但是这道题目的容斥系数不是 +1 和 -1，于是我又让生成函数大神 yt 严谨论证了一遍，中间 yt 告诉我生成函数的 x^i 有些情况下可以带值！！！！太神秘了。不过最终推出来的式子和我一开始想的一样。但是现在这个式子还是 O(n)，后面 xjy 又发现可以先用分治求出多项式，再用多点求值就可以做完了。不过时间确实不够了，遗憾离场。不过还好，过了 6 道题，rk 46，守银了，没有成为蓝铜。

后面听评讲，发现 G 有简单做法，直接求范德蒙德矩阵的行列式即可。我发现我既知道范德蒙德矩阵，有知道行列式，就是没有想到把它们结合起来，看起来数学还是太菜了，还得更加努力啊。

总结

感觉高中生打 ACM 总是 \mathrm{Cu} 和 \mathrm{Ag}，希望下次能 \mathrm{Cu + Ag} \xlongequal[\Delta]{\text{催化剂}} \mathrm{Au + Cg}（Cg 是个什么东西） 吧！