2026 CSP寄

· · 生活·游记

CSP-J

本来想着玩玩吧，不要过度用脑，下午发挥。然而我并没有 AK。

T1

什么玩意。

T2

一开始想着不会直接暴力建字符串吧，然后看完数据范围花费 5 秒想出双指针。

T3

一开始想着枚举二进制位直接填答案，然后把这个过程想成 O(n) 了，卡了好久，写了个随机化，把样例都过了，后来通过往里塞 m-1 个 2^{30} 轻松把随机化卡到输出 0。后来突然想到枚举二进制的过程是 O(\log n) 的，时间复杂度应为 O(n \log n)。卡了。

T4

毁了。

QAQ，算了我不管 J 组。

CSP-S

T1

一开始写了个二分，二分最后的数，最后一个大样例没过。卡了好久，后来想到，或许我需要二分答案，然后二分最后的数？时间复杂度 O(n \log V \log n)，算一下发现约等于 5 \times 10^8，过不去。后来想到了这样一个结论：最后的数一定是其中一个 a_i。

如果最后一个数可以是 a_i+k,k>0，那么这些数全部减 k 同样可以满足，而且花费更少。

然后我们在二分最终的数的时候就可以从 O(\log V) 优化到 O(\log n)，O(n \log^2 n) 约等于 2 \times 10^8，可以过。然而并没有写对。

后来突然想到了可以直接二分答案，检查连续的区间，时间复杂度 O(n \log n)，遂 AC。

T2

什么玩意啊，我读了 30 分钟才读明白，感觉最近专注力特别差，脑子也是浆糊一般，赛时感觉还有些困，完蛋。一开始想着会不会是货车运输。发现这是不好画图和建图的，但还是硬着头皮画了一下，发现无法跑最小生成树，每一条边都可能有用，缩点吧。。。难处理得没法说。开 T3。

T3

很容易想到直接 O(n^2) 暴力建边，接下来枚举起点，跑个 bfs 求一下最短路和方案数即可。于是有了这个代码：

void solve() {
    in >> n >> d;
    for (int i = 1; i <= n; i++) in >> x[i], e[i].clear();
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (x[j] - x[i] <= d) e[i].push_back(j), e[j].push_back(i);
            else break;
    int ans = 0;
    for (int s = 1; s <= n; s++) {
        for (int i = 1; i <= n; i++) f[i] = 0, dis[i] = 1e9;
        dis[s] = 0, f[s] = 1, q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : e[u])
                if (dis[u] + 1 < dis[v]) dis[v] = dis[u] + 1, q.push(v), f[v] = f[u];
                else if (dis[u] + 1 == dis[v]) f[v] += f[u];
        }
        for (int i = 1; i <= n; i++) ans += f[i] == 2;
    }
    out << ans / 2 << '\n';
}

跑样例3的时候有点慢，当时认为这是 O(n^2) 的，40 分，还不错。下一题。

T4

什么玩意啊，怼着题面看了 10 分钟终于看懂在干啥了，除了 2^n 纯暴力没想到任何东西，15 分，有点拉，先不管，重新看 T3，还是没头绪。于是重返 T2。

回补 T2

我明白了，对于一条线，我们在线上切换不计代价，所以我们完全可以跑任意两条线间的最短路，Floyd 即可，O(n^3)。我一开始还还不确定这对不对，模拟了一下样例发现这是对的。然后这题打了不久就过了。

评价：真难调，真雷霆。

回补 T3

我突然发现 bfs 的时间复杂度其实是 O(n+m) 的，在本题中也就是 O(n^2)，时间复杂度应为 O(n^3)！！！坏了，又损失了 16 分，我通过造了一个 n=d=5000,x_i=i 的数据把我的代码卡飞。后来突然想到，其实距离当前点越近越不可能被更新，所以我们可以从后往前扫描，扫描到 dis_u+1 > dis_v 的直接 break，直接二分最后一个满足 x_v-x_u \le d 位置，这样的时间复杂度是 O(n^2 \log n) 的。然后可以发现，这个二分可以预处理一下，把时间优化到 O(n^2)。打完了，终于得到了真正的 40 分代码。

void solve() {
    in >> n >> d;
    for (int i = 1; i <= n; i++) in >> x[i];
    for (int i = 1; i <= n; i++) {
        pos[i] = i;
        for (int j = i + 1; j <= n; j++)
            if (x[j] - x[i] <= d) pos[i] = j;
            else break;
    }
    int ans = 0;
    for (int s = 1; s <= n; s++) {
        for (int i = s + 1; i <= n; i++) f[i] = 0, dis[i] = 1e9;
        dis[s] = 0, f[s] = 1, q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v = pos[u]; v > u; v--)
                if (dis[u] + 1 > dis[v]) break;
                else if (dis[u] + 1 < dis[v]) dis[v] = dis[u] + 1, q.push(v), f[v] = f[u];
                else if (dis[u] + 1 == dis[v]) f[v] += f[u];
        }
        for (int i = s + 1; i <= n; i++) ans += f[i] == 2;
    }
    out << ans << '\n';
}

T4

或许我们可以进行这样的一个树形 DP。f_{i,j,k,0/1,dis} 表示当前在第 i 个点，选出了 j (j \le 2) 个联通块，还可以再选 k 个点，i 是否在当前的第 j 个联通块里，子树内最远与联通块的距离。这个 DP 值本身表示 i 到最近的联通块的距离。这样的时空复杂度为 O(n^2k)，可以拿到 35 分，但是我赛时觉得这太难写了所以打了暴力。然而打炸了，题目说不超过 2 个联通块，我写的是必须有 2 个联通块。然而这居然把样例都过了。气死我了，样例还能再水一点吗。

预估分数

S：本来是 255 的，最后一题暴力写错了，所以现在是 240 了。

J：358

感觉还不错，要是 S 组的 T4 暴力没写错就真的满意了。