CSP-S 游记

· · 生活·游记

Day0

“赛前打模拟赛会失去信心怎么办？”

“给别人搬模拟赛，你会获得他们失去的信心。”

Day 1 上午

睡觉。太困了。睡觉。睡不着？

开考前

很快就坐上了学校的大巴，并且于 14 点之前达到考场。

我是 1 楼 101 号教室 1 号座位！不对，这栋楼为什么会有机房？而且怎么在 1 楼？

进考场后发现：这是不是一个会议室啊？里面全是六人桌，正好给 6 个考生。我作为 1 号位，那个显示倒计时和密码的一体机就在我旁边，并且我离教室出口直线距离只有 \le 2 米，并且中间没有障碍。

貌似这个“机房”可以坐下 100 个考生。

开考前 2.0

众所周知 CSP-S 从 14:30 开始，长度为 4 个小时。但是一体机上的倒计时在大约 14:25 的时候突然变成了“正在考试”，下面的倒计时足足有 4 个半钟！后面到了 27 分倒计时就恢复了，但是密码怎么到 30 分才发 /ll。

人杰地灵

做题心态

看到 T1，这不是我们亲爱的 AGC018C 吗？于是我有了以下思路：

先假设每个人都去部门 1，然后再用 a_1 - a_0 或 a_2 - a_0 的代价去调整。

调整过程可以用 priority_queue 维护，并且进行反悔贪心。

然后我忘了 AGC018C 当中是对 a_1 - a_2 排序后，部门 1, 2 选择的是一个前缀和后缀的点，所以我开始瞎蒙。

开两个 priority_queue 分别对 a_1 和 a_2 从大到小维护，如果某个部门大小已经 \ge \frac{n}{2}，那么：

  • 不进行替换，因为当前比已经进入该部门的任意一个都不优。
  • 把原本的一个放到另一个部门，相当于将其弹出然后插到另一个 priority_queue
  • ……

然后我惊恐地发现，这东西怎么一堆 Corner Case 啊？并且对着这个错误做法想了 30 分钟。

然后花了 10 分钟想出正解并写出来。

T2 肯定是先把原图的 MST 建出来，然后边数就是 O(nk) 了。只要枚举 k 中哪些点，就可以 O(2^nnk\log nk) 了。

等等，为什么要 \log？那肯定是对边排序啊！能不能先排完序？

能！这样我们只需要实现一个 k 路归并，复杂度为 O(2^nnk\log k)。

直接 k 路归并还是太慢了，于是我写了一个 n\log k 合并的代码：

void merge(int l, int r)
{
  if (l >= r)
  {
    return;
  }
  int mid = (l + r) >> 1;
  merge(l, mid);
  merge(mid + 1, r);
  inplace_merge(g + (l - 1) * n + 1, g + mid * n + 1, g + r * n + 1);
}

赛后发现大脑宕机了，其实只要初始时把 m + nk 条边一起排序就行了啊！

T3 做的还是比较顺利，很快想到 ACAM 做法。但是 ACAM 不是超纲了吗？无所谓，好写就行。

但是这个 ACAM 有 2.5 \times 10^6 个点，值域还被我搞到了 676。经过计算，2.5 \times 10^6 \times 676 个 int 仅仅需要 6\text{G} 的内存。

于是我发现，我可以用 map 存出边，并且与一般的 ACAM 不同，我只需要维护每个点的 fail 指针（而不需要把不存在的子节点从 fail 指针那里拉过来）。势能分析一下就是对的。

大样例貌似跑的很快，但是显然它没有造满。

T4 不会啊！

回顾一下，发现其实是陷入了这么一个误区：

每个 c 相等的人肯定是等价的，所以可以将他们视作相同的人，最后乘上对应的阶乘即可。

所以，我们尽量一次操作把所有 c 相等的人加进排列。

自然而然就是对每个 c 值进行插板。

这样，也就只能过过 A 性质，拼好分罢了。

其他感受

在离考试结束还有 70 分钟时，我提出要去厕所。但是当时考场里只有一个监考员（本来是有四个的，怎么都走了？），所以显而易见，他拒绝了我的请求。

等到 40 分钟时，考场仍然只有一个监考员。

等到 27 分钟时，别的监考员终于回来了。我又提出要去厕所，结果被他们因“离考试结束只有 30 分钟了”为由，拒绝了。

这件事和我坐在 1 号位共同促成了我是第一个冲出考场的人这个结果。

请考生新建一个以自己名字为题的文本文档，里面包括考号、学校、指导老师、提交的程序等，该文档的格式没有特殊要求。

至少 4 次 CSP 我只写过一次，并且是今年写的。写的内容大小为 0\text{Byte}。

至于为什么，在考试结束前，监考员突然走下了，一个一个地提醒我们，叫我们打开注意事项，指向了这一行字，然后看着我们建完文件之后才走。

我旁边的人可能不太熟悉这个文件格式（不是说没有格式吗），结果被监考员亲切的指导了半天。我还听到了“等会我再过来检查一下”。

今年的 checker.exe 怎么还要选手自己配置？

赛后交流

出考场了，遇到一个学长理论分数比我高 4 分。于是我问道：“你怎么多拿 4 分的？”结果发现，那是另一题挂了……

经过讨论得到，T3 大样例只有 1.4 \times 10^6 个点，相当于造了一半左右的规模。反正我好像在 0.5\text{s} 以下。

这个 T4，原来和 Club of Young Aircraft Builders 这么像！我们年级有 \ge 4 个人在一个月内做过这个题，并且有 0 人通过 T4。然后就被学长骂了一顿。

测评机是 3.7\text{GHz} 的，但是把睿频啥的都关了，是不是会慢啊？

一个大神考委了，只有 2 字头。我考场上没有对拍，所以估计会挂的很多。

“震惊：某学生竟然要在 NOIP 之前退役！”

当然这是假的。