2024-2025 ICPC, NERC 线上赛参赛笔记

· · 生活·游记

队员是我,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 到底应该怎么想到这东西啊。这也太抽象了。