记录第一次ICPC网络预选赛

· · 生活·游记

回顾

进入大学一年，从程序设计基础课开始，一直在学习编程算法。怀着一些兴趣，在暑假我加入了 ICPC 校队。经过一假期的训练，能力有着明显的提升。因此我主动联络了两位同学，准备参加 ICPC 网络预选赛。根据三个人的微信头像，取名为河边喝水的三只猫。

两位队友都有着各自的特点，zmx 同学非常冷静，善于解决一些数学问题；msc 同学参加过 CSP-S 竞赛，获得过一等奖的好成绩，对复杂的问题能进行拆解。感谢我的两位队友，陪我参加比赛，包容我犯下的低级错误，和我不厌其烦的解释算法。

比赛

在比赛之前，我们三个人只合练过两次，默契程度不高，甚至用不惯对方的键盘。但是好在我们对题目有一定的理解，每个人能形成互补，因此陌生并没有很大的阻碍我们交流讨论。

在这场比赛过程中，可以说是最艰难的一次。在面对开始的签到题 C，我很快的想到了二分答案的做法，但是由于对容斥原理理解的太差，完全不能进行下面的操作。zmx 先交了一次，使用的方法具体我忘记了，但是 WA 了。因此第一题的进展非常不顺利。我开始混乱的思考，面对机房里面紧张的氛围，msc 在解决 E 时遇到了数学上面的障碍，也开始紧张起来。整个团队的节奏完全被打乱。

因此我觉得先试一下我的方法，我先写了一版二分答案，但是由于在容斥原理的限制不足，WA 了。不过 zmx 很快提出了解决方案，虽然存疑，但是我直觉上是完全正确的，因此交了一道题，顺利 AC，缓解了诡异的氛围。

发现榜上D题做出的准确率较高，因此我们转换到D题。由于之前做过类似的题目，很自然想到了贡献值的方法，但是本题因为复杂度关系无法通过，因此又陷入困境。但是接下来发生了神奇的事情，我和 zmx 同时观察发现了此题和二项式定理的关系，于是两个人先计算数学表达式，得到的结果一样，我果断开始上机。很快写了一发，WA 了。

我开始陷入焦躁的状态，因为完全不知道哪里出现了问题。但是这时 msc 几乎完成了 E 题，因此他先上机写题，我开始 debug。在他遇到瓶颈期的时候，我突然意识到是对一个数字除 2 再取模，会影响答案。因此想到了费马小定理的解法。正巧他继续思考，我修改代码，最后 AC。

这时 msc 几乎完善了题目的思路，剩余 80 分钟，我们集中攻克 E 题。途中需要写矩阵加速，虽然最近没写，但是假期集训我随手写了两个矩阵加速的题目，让我接手矩阵加速部分的函数。配合过后，样例正确，但是测评是 WA。此时没有机会检查思路，我们选择相信 msc，开始检查数据范围的问题，改了两次还是 WA，最后发现，是我的矩阵快速幂里面，对单位矩阵初始化的时候存在数据溢出的问题，修改之后，惊喜的发现 AC。

反思

本次比赛，我虽然有一些贡献，但是对细节的考虑、数据范围的限制，严重影响团队的罚时，在此我付主要责任。希望下次能精简代码，完善细节，别再因此拖累团队。本次成绩对于我们三个来说已经比较满意，祝愿我的 ACM 之旅顺利进行，希望和两位队友有更多的合作，再次感谢我的两位队友。谨以此文，纪念这次经历。