2024-2025 ICPC, NERC 线上赛参赛笔记 最后更新于 2025-05-01 21:52:47

队员是我，wcz 和 gwf。 队伍名是 維多利亞皇家近衛學院附屬高中陌域坍縮部。gwf 起的名。 我跟他们俩不在一块，所以用的QQ群。 一开场各自做了签到，然后开始分工。 我切完签到正在想 B。感觉很困难。别人也把简单题做完之后讨论了一下L，我的式子假了，wcz 写了一个枚举过了。 然后我们交流了一下题目，我开始做 G，gwf 在 B，wcz 在 K。 我对着 G 乱想了一通发现可以通过查前面有 0 的 1 段数和全部的 1 的段数来判断第一个位置是不是 0。 想到就赶紧写，写完发现过不去。吃了无数发罚时后发现是最后还有一个输入没输。 这个时候过了 6 题了，比赛开始了一小时左右。 我跟 gwf 在讨论 B，wcz 在 K。 gwf 一开始想的是一个差分状物，但把两个位置的变化变成了三个位置。感觉这样处理就更麻烦了。 我手玩了几组样例发现可以倒推，从只由某一个值组成的序列倒推出原先的序列。这时的我猜测倒推的开始位置是最小值的位置。 后来发现这个可以二分，于是就开始写。写完一直 WA3，实际上是之前猜的从最小值开始是错的，应该从最可能让每一个位置都合法的位置开始。这个位置不好找，那么可以不找。因为这个贡献是直接作用在下一个负数上的，中间经过的可以不用处理。写完之后又 WA 了一发才过，无敌了。 在我写 B 的时候 wcz 已经把 K 切了，他前面贴边走，最后在一个 $50\times 50$ 的格子 dp，过了这道题。很牛。 因为 wcz 是乱搞大师，所以他接下来一直在冲 M。 我写完 B 的时候 gwf 也会做 D 了，但他还要回宿舍，只剩下了半个小时的时间。 这个时候大约九点十分。 wcz 发了个 M 的代码让我跑，但很快发现这个假了。 我一开始在看 F ，但感觉很困难。 然后看 I ，初步有了一个 $\mathrm{O(\frac{min(n,m)nm}{w})}$ 的想法，但其中的 $\mathrm{O(\frac{n^2m}{w})}$ 我还没想好怎么做。 回头发现已经快十点了。gwf 回宿舍了，把遗产——他的代码和思路发了过来。他的代码基本写好了，但还没调出来。 因为我之前没看过 D，也不知道具体的转移方程和转移式，再加上暂时联系不上其他俩人，所以花了好长时间读代码。 读出来的问题也基本是小错误，比如初始化和加负数的时候用大于等于模数来取模会寄，最后十分钟终于调出来了。很爽。 总共过了⑨题，吃了一堆罚时加上压线交题导致排在同题数的倒数。 再给一些时间或许能把 I 做出来，但我不好说（因为现在还没想出来怎么做）。 感觉很打得很爽。像 K 题这样的是我不擅长的题，却是 wcz 比较擅长的，gwf 也很擅长分析题目性质，最后 30min 写完了一个一点不好写的代码，B 题也想出来了正解。 最后排在了 104。 唯一就是，G 到底应该怎么想到这东西啊。这也太抽象了。