NOIP 2024 游记

· · 生活·游记

Day 0 (11.29)

上午复习了三个 tarjan。

下午试机，听洛谷讨论区说 CCF 评测机跑 2 \times 10^3 的 ULL 自然溢出 Floyd 需要 5s，在考场的电脑上试了一下，12s，另外还试了在 qingyu 博客看到的 -fsanitize=address,undefined 和 ulimit -v，本来还想试一下对拍的，但是没打完就回去了。

晚上完全不知道干啥。

Day 1

进考场，和 CSP 一样还是开着 Windows，等极域发了密码我就赶紧重启成 Linux 了。前十分钟先开 VSC 敲了个缺省源。

读 A，发现自己好像不太会，于是边写边想，第 70min 写完，结果调不出来。于是直接重写，第 90min 过大样例。

然后开 B，一眼看出 d_j 不影响答案，也就是如果 j 是 i 下一个赋值的，那么有两种情况。

  1. 从 i 开始的限制最后传到了 j，显然有 v^{j-i} 种方案，其中 \frac{1}{v} 的方案（即 x_{j-1} = a_j 的方案）是合法的。

  2. 从 i 开始的限制最后没传到 j，有 v^{2j-2i}-v^{j-i} 种，全部合法。

将每段的合法方案数相乘，再特殊处理首尾两端，需要注意 c_j 相同的情况。

在草稿纸上写完上面这些直接开写，140min 左右过大样例。

C 题先写了一个 k=1 的 24pts，大概就是在很多个完全子图里任选一条钦定了一端的链，方案数为 \prod\limits_{i=1}^n (deg_i - 1)!，第 174min 写完。

写完 C 的 24pts，决定先看看 D，发现求 LCA 是可重复贡献的，而且满足结合律，用两个 ST 表写了 n, q\le 5000 的部分。回去看 C，观察第九个样例（一条链）发现全是 1，第十个样例（菊花图）的式子也很好推，于是喜提 16pts。

再看看 D，感觉自己的双 ST 也可以做 k=r-l+1，花五分钟改了一下。链的 32pts 脑子过载，一眼没看出来就没想了。时间只剩半小时，开始检查，发现自己 D 没写 freopen，赶紧加上。最后十分钟切回 Windows，等待结束收代码。

此时估分应当为 100+100+40+32=272，但由于我看错了 C 部分分的测试点个数，所以以为自己是 100+100+44+32=276。

比赛结束，然后别的考场十分钟收完，我们考场收了半个小时（？

赛后才发现 D 链的 32pts 非常好拿，不过我也拼了个 32，感觉还行吧。

感受

感觉这场自己打得比较保守，比如最后半小时没去冲链的 32pts。但是再想想，就算写出来也可能忘记 freopen。

另外，-fsanitize=address,undefined 好用！