CCPC 网络预选赛 游记

· · 生活·游记

最后一场了。

出发前当你一遍又一遍的摸着包里的身份证和学生卡的时候，你的脑海里浮现的是怎样的画面？

不管怎么说，打完这一场，再下一场就要到 11 月了。全心投入这一场吧！

正片 比赛日

第三回坐在熟悉的位置上，第三回打开熟悉的电脑，第三回用远没有鼠标好用的触摸板登录考试系统（没办法，谁让我的鼠标是蓝牙鼠标呢）。

比赛开始。用队长机看题。不一会儿看到 E 题：BO n 赛制，作为 MWC 观赛者我可太熟了啊！用 m - n 就可以算出败者拿的小分数量，然后若有一方的小分数量超过这个值，那么胜者就已经确定了。上机写了一发，8 min 的时候交了，一遍过了。看来今天开局不错。

然后两个队友去看 A 题，我去看 G 题。首先 x = y 的情况特判一下，然后把出现次数超过 \sqrt{n} 的数单拎出来，考虑处理这些数与其它数之间的贡献——这部分是 O(n \sqrt{n}) 的，在询问时，若其中一个数出现次数是超过 \sqrt{n} 的，直接 O(1) 输出，否则 O(\sqrt{n}) 的现场算一下。

“那你要不写一下？”real_man 听了做法，觉得很有道理。

“数据结构你能写清楚吗？”_Vector_ 提了一嘴。

好有道理啊，我想。于是我把这题交给了 real_man，自己看 C 去了。

稍微想了一下，发现 C 类似最小生成树，不需要管顺序的问题。但怎么在带模的基于点权的“完全”图中求最小生成树呢？我百思不得其解。我又不会了。

跟 _Vector 说了一下我的想法。“这不就是那个 B 开头的最小生成树吗？”于是开始到处找板子。

什么？最小生成树算法还有 B 开头的？好的又触及我知识盲区了。那这题又跟我无关了。那我能干什么？

“你要不去看看 A 题？”

A 题看起来很复杂，好像要对于每个点处理不同面积的正方形有几种。我想了一下没思路，于是问了一下队友他们之前的思路。

“我们之前想的是每个顶点会把网格这样划分为 4 个区域……”

“不对啊正方形不是可以斜着放吗？”“哦，那好像之前想错了。”

看来我必须独自完成这道题了。

55min，G 过了。队友通过打表找出了 K 的规律，在 1 h 7 min 的时候过了。

这个 A 是不是可以递推呢？感觉像一个 O(nm^2) 的东西。先把每一行第一列点的答案暴力求出来，然后向右递推，每次递推的时候会增加左边界在第一列的正方形，减少右边界在最后一列的正方形，通过某种方式枚举这些正方形（其实就是枚举边界上的点分别作为对角点和相邻点看这个正方形合不合法），再拿个 map 什么的维护一下，可以做到 O(nm^2 \log nm^2)？但感觉过不去。

“那你用桶记一下就行了嘛，它最大不会超过 3 \times 10^5。”real_man 说。

对啊！那这样总复杂度就是 O(nm^2) 的，那这个做法简直是真理啊！

唯一的问题是……那这个题怎么这么多队伍过了？

于是我开始写了。然而我式子没推完，写的非常慢。后来我干脆下机位推式子了。

现在的情况是：A 在推式子，C realman 在现学模板，D 据 _Vector 说是会了但是要写又臭又长的 3 个哈希，F 在打表观察 SG 函数。贷款 4 题，这下真是对上队名“六兆年零一夜的 ACM”了。

式子推出来了。我又上机编写。没过样例。打印，换 real_man 写 C。

2 h 45min，C 过了。我带着刚刚找到的问题修改 A，终于把样例一过了。然后是样例二……不是这啥呀？

对着样例输入手玩了一下感觉自己程序没问题，于是又看了看样例输出，我好像突然明白了为什么这么多队伍通过了这题。

无法识别的语言随着一声敲击桌面的巨响弥漫在机房里。

“怎么了？”_Vector_ 问道。

“我**的读错题了！这“ 不同的面积为正的整点正方形”指的是“不同的正方形”而不是“面积不同的正方形”！”

“*那他给这个面积为正干什么啊？？”real_man 回应道。

于是就像被敲诈了一样的我几乎破防的修改着我的代码，让它符合题目原先的要求。终于通过样例后，3 h 15 min，提交，TLE 了。

从机位上下来，我几乎是瘫坐在座位上。

“我在想，能不能卡常把它卡过去……”

“还是重构吧，”_Vector_ 说，“3 \times 10^5 的 n \sqrt{n} 还是太大了。”

为什么出题人要这样出题？这 O(n \sqrt{n}) 形式下的题目这么优美，凭什么这题不是这么出的？我几乎有些控制不住自己的情绪了。

好在 _Vector_ 在我前面写 A 的时候肉眼瞪出了 F 的 SG 函数的循环节（甚至是个混循环），于是 F 开始写了。然而 3 h 45 min 的时候交了一发，也挂了。改了个小错误紧接着又交了一发，又挂了。

唉，还是看回 A 吧。

如果枚举每个可能的正方形的对称中心，那么它一定在整点上，或者某个小正方形的中心。于是，我可以把横纵坐标都乘以 2 之后枚举这个对称中心。每个对称中心会对一个与坐标轴平行的正方形内的所有点产生 1 的贡献，因此可以二位差分维护。

看了看榜单，有一种欠了很多债而又还不上的感觉。

“别看榜单了，赶紧想想 A 怎么做吧。”_Vector_ 在一旁提醒。

“哦，我应该已经会了。”

“那你先上来写。”

写的时候二维差分还写错了一次。改掉之后样例过了。

于是，在 4 h 13 min，也就是封榜后，我终于过了今天的签到题，全场通过队伍数量第三多的题目。

哦今天 pta 不知道在干什么 4h 没封榜。看来比赛系统比我更神人。

“我这个 D 肯定是写不完了，我们就 all in F 吧。”_Vector_ 提出了最后的计划。

反复检查后，终于发现，问题的根源出在题目最开始给出的线段是可能相交的。“这博弈论已经够难了，还要再搞一个根本没有关联的另一个恶心人的东西，这就是典型的烂题……算了不说怎么出题了。”_Vector_ 说。

我并没有想到什么好的做法，不过 realman 和 _Vector 在一通讨论之后搞出了一个数据结构做法。然而到了最后一刻还是没有通过样例。

还是交了一发，不出意外的没有通过。

比赛结束了。我趴在了桌子上。

校内排在第 5 名，总排 291。

“怎么都过 D 了。”_Vector_ 说。

感觉是 A 的问题。要是我 A 题目没看错的话，估计 D F 都做出来了。怎么会把优势场打成这个样子呢？

“总结教训，”_Vector_ 一遍整理着东西，“这场没关系，只要区域赛不要再像今天这样就可以了。”

“起码有比赛打了。”real_man 说。

那天下雨，我没有带伞。我们三个撑着一把伞，在食堂分别。

赛后相关

第二天……

2023 ICPC 区域赛济南站，重现赛。

这 G 题怎么这么难啊？这翻转操作好神秘啊，居然还要对 998244353 取模？算了交给队友。

“这题应该是一个 2-sat……”

啊这还能 2-sat？见鬼了。不管了反正队友会了我就做自己的题吧。

重现赛结束后……

看眼题解吧。

什么叫第一列和最后一列都有 1？

等等我看眼题面。

怎么是反转？？我怎么又读错题了？？

诶服了还好今天这题不是我做的。

周四……

群聊“六兆年零一夜的 ACM”聊天记录

lizihan250: 能不能有空把 A 题代码发我一份/mg

lizihan250：想按我读错的题意祸害高中同学（

real_man：/dx

hwp：/dx

周四晚上，周五凌晨……

晚安喵~

（猫猫在床上打滚……）

不对。

济南那个题是不是“翻转”也能做。

假定每行多的那个字符是 A，少的是 B。

那么有一行选完 A 作为 1 后每行只有至多一种可能的选法。

而且 |A| = |B| 要是有解则最多只有两行，且剩下每一行都有 |B| = 0。

所以 |A| = |B| 多于两行的直接无解。

等于两行的判断剩下的行是否全部 |B| = 0。

否则计算每行 B 的前缀以及后缀与（有重的打个标记）。

然后枚举哪一行取 A。

时间复杂度 O(nm)。

怎么又造题了？？？

周五……

A 题卡常真卡过了。

我尝试把函数里的所有东西全部放到主函数里写，不使用额外的变量，没想到程序只用了 600+ms 就跑过了。

校队群里问了一下，结果好几个队伍写的都是 O(nm^2) 的。

shwstone：“穿越到出题组身上把你们都卡爆”

必须支持！

怎么可以只卡我一个别人都不卡呢？

尾声

网络赛阶段结束了。

网络赛的发挥没有对选站造成太大的影响，ICPC 选到了武汉沈阳两站，CCPC 选到了郑州。

接下来是一段比赛真空期，我们 11 月再见。