CSP-S 2023 游记

蒟蒻的第一次 CSP & 第一篇游记。

同时应该也是最后一次 CSP。

第一轮

Day 998244350

下载准考证。

Day 0 (2023.9.16)

和学校请了一天的假，成功错过三门考试。血赚.jpg

上午看了看 CSP 初赛复习，写了喵了个喵，但没调完。

在谷上看到 CSP-J 出锅，希望 CSP-S 无锅。

Day 499122177

来到考点。比我校大多了.jpg

居然还有喷泉，大受震撼。

还有 30 min 开考，到楼下的运动区转转，做了几个引体向上，感觉自己好废。/kel

被各种器材震撼。

考前去了次厕所，只有 \(1/5\) 的锁是好的，且天花板坏了一块。我校是 \(1/4\)，赢。

开考。

试卷是装订成册的，是我没见过世面了。

30 min 切了前面的 15 题。

阅读程序第二题感觉好鬼畜，\(O(n \log \log n)\) 一看就感觉很对。

考场思路：

首先发现其他部分都是 \(O(n)\) 的。

for (int i = 2; i * i <= n; i++) {
    if (p[i]) {
        vector<int> d;
        for (int k = i; k <= n; k *= i)
            d.push_back(k);
        reverse(d.begin(), d.end());
        for (int k : d) {
            for (int j = k; j <= n; j += k) {
                if (p[j]) {
                    p[j] = false;
                    f[j] = i;
                    g[j] = k;
                }
            }
        }
    }
}

内层分析出来是 \(O(\dfrac{n}{i})\) 的，而外层总共只会跑 \(O(\dfrac{\sqrt n}{\log n})\) 次，内层把 \(n\) 提出来就是一个像调和级数的东西，外层放成 \(O(\sqrt n)\)，扔进调和级数就是 \(O(\sqrt n \log n)\)。

然后这只蒟蒻就忘了乘回 \(n\)，认为总时间 \(O(n)\)。

阅读第三题 \(O(n \log (nA))\) 痛失 3 pts。

最后一题不会，只能看出是个左闭右开的东西。后来听 U 群说是猫树分治。/jk

发现谷上有答案，期望得分 87 pts，实际 87 pts。

注意：由于不想被开盒，上面的成绩均四舍六入后异或了一个值。