CSP2022 游记

· · 生活·游记

\text{Day -?}

暑假集训了 2^{114514} 天。

好在我没有暑假作业（新初一の快乐）。

\text{Day 0.2}

早上 5 点起床和学校一起去杭师大，早饭吃了玉米。

在车上不像初赛，人多，而且很早，现在全车人都很寂静。

来的路上和 WYZ 聊了会天，我们一致不希望考表达式。后来发现他睡了，我也睡了。

\text{Day 0.3}

上午考 J 组。带了一瓶维他命水和一堆零食进考场，维他命水不断掺水后发现一点也不甜而且超级酸，不敢继续掺水了。

先看到文件名，一眼看到 pow，以为是压轴题，想了一下有关幂的各种公式，发现自己什么都不会，感觉很慌。之后看到 expr 反而没有想象中的无措。

密码发了，先看了眼题目。T2 看到式子好像很难，发现自己只会 \mathcal{O}(Tn^2) 做法；T3 看到超长的题目没有看，跳过了；T4 一看好像是 dp，但是不会。最后决定 1->2->4->3 顺序开题。

T1 很快写好了。在脑子里回忆无数遍模拟赛炸 T1，又检查了无数边，觉得可以了。

T2 推了很久公式，推出了 p=n-ed-q+2，验证 pq=n 即可。我认为这个可以二分求，但是没想到二分差值。发现 f(x)=x(n-x) 是单峰函数，就开始写三分。由于我以前从来没有学过三分，就想象了一下单峰函数的样子，写出了如下的代码：

while (T --) {
    cin >> n >> e >> d;
    ll m = n - e * d - 2;
    ll l = 1, r = m, flag = true;
    while (l <= r) {
        ll mid = (l + r) / 2;
        ll sum = solve(mid);
        if (sum == n) {
            ll a = mid, b = n - e * d + 2 - mid;
            if (a > b) swap(a, b);
            cout << a << ' ' << b << '\n', flag = false;
            break;
        }
        if (sum < n) {
            if (solve(mid + 1) > sum) l = mid + 1;
            else r = mid - 1;
        }
        if (sum > n) {
            if (solve(mid - 1) < sum) r = mid - 1;
            else l = mid + 1;
        }
    }
    if (flag) puts("NO");
}

写完一看，大小样例全过，十分高兴，开 T4 去了。

T4 看完想到 dp：设 f_{u,k} 为点列最后点为 u，并且添加了 k 个点的最长上升点列。我发现直接 dp 的话需要排序消除后效性，但是害怕排序写错，于是写了记忆化搜索。写完经过调试通过了所有样例。

最后开 T3，经过两个小时的鏖战，我发现我的模拟能力极差，连基础的 \mathcal{O}(n^2) 做法都写不出来。最后，时间只剩下最后一小时，我删掉了 T3 所有的调试语句，准备听天由命。

在交卷前，我对拍了一下 T2，发现有问题。并且成功地发现了是 m 的范围太小。可是，我没有发现我将 n-e\times d+2 写成了 n-e\times d-2，而是经过调试后，将 m 改为 2\times(n-e\times d-2)，通过了一部分 Hack。这时候，仍然有数据在 Hack。可是，由于我以为 m 是 n-e\times d-2，我认为这些数据不合法，并屏蔽了它们。

尽管这个程序错误，在官方数据得到了 0 分，但是它至少在民间数据可以获得 70 分，让我做一个入门一等梦，哪怕是短暂的，虚假的。但是，在交卷前，我却没有发现我对拍时留下的调试语句，没有删除……

哪怕是短暂的梦，也碎了。

最终分数 100+0+15+100=215，留下了遗憾。

\text{Day 0.5}

中午和 wyz、shm、gzh 吃了 KFC（教练请的），好吃qwq

下午的 S 组，我认为切一道题就能稳二等。

\text{Day 0.7}

下午考 S 组。密码给错属实好笑。

打开 pdf，我快速地浏览了一遍题目。T1 发现只会 \mathcal{O}(n^4) 的做法，我觉得这是一道思维题，就暂时没想；T2 看到“最优策略”，以为是博弈论，仔细读题后发现不是，但是我不会；T3 看完题面，毫无思路；T4 看完后，我只会暴力的树形 dp。抉择了一下后，我认为 T4 正解对于我是不可能的，所以先写 T4 的暴力，决定 4->1->2->3 顺序开题。

T4，我设 f_{u} 为走了 1\to u 结点，询问 u\to v 答案即为 f_{u}+f_{v}-f_{\text{lca}(u,v)}-f_{fa(\text{lca}(u,v))}。我幼稚地以为这样可以通过 k\leq3 的数据，但是我没有思考，这样不仅不能通过会走出链的 k=3，连 k=2 都无法通过。但是我测试了大样例，我没有 fc，而是通过肉眼判断，以为我简单地获得了 42pts。

开 T1，我认为这题与 dp 脱不了干系。

我写麻了，以后再写。