前言

赛氪组织的编程赛，其实蛮多的，而 全国大学生算法设计与编程挑战赛 属于其中的翘楚。

前些年，不仅参加人数众多（好几千），而且知乎上有不少参赛人员的高质量题解，也有官方视频真题讲解。

虽然有吐槽，比如个别题数据有问题，查重查到同一个人的同一题的两次提交，但是仍属于可控，可容忍的问题，整体趋势是好的。

可惜，出道即巅峰，尤其是 AI 时代:

$$不作弊意味着拿不到奖$$

所以这篇总结，不单纯是解题报告，更是 祭奠。

---

赛时

开场 10 分钟，就有队伍过了 7 题

开场 半小时后，就有队伍 无伤 AK

开场 1 小时后，前排基本都 AK 了

总共 500+个队伍。

最终的过题情况

绿色是我个人过的题，主要看 解决/提交 这一栏。理论上最多 166 人 AK。为啥我说理论呢？是因为官方把排行榜封榜（隐藏）了。

个人不屑用 AI 作弊，限于水平，只做了 8 题。按以往的比赛来衡量，8 题是一个非常不错的成绩，现如今只能拿空气奖玩玩。

其实不光赛氪的线上赛，其他比赛，如计挑/传智杯，也是一样的肆无忌惮，AI 时代，一方面人人都是算法天才，另一方面也悄无声息判了古法编程的死亡。

---

赛后

官方公示的获奖名单，果然没查

就这样吧

---

题解

整体题目出得还可以，比往届要简单一些。

题目	知识点	Deepseek评估(按CF基准)
A. 定时转运	同余, DP优化模拟	1900
B. 异侧	二分图判定	1300
C. 平方和的波动	分组背包 + bitset 优化	1500
D. 三元组	哈希模乘	1750
E. 时空覆盖器	二维滑动窗口/扫描线 + 线段树	1900
F. 集合异或	思维题	800
G. 骰子示数	签到题	800
H. 好友链追踪器	简单模拟/图论题	1400
I. 数组划分优化	分段 DP + 单调栈 + 线段树优化	2100
J. 排列循环移位计数	第一类斯特林数	2100

单纯地挑几道题讲讲

A. 定时转运

这题单纯模拟会超时，需要找寻里面的规律。

可以用打表法观察，以及把玩小数据，可以感觉到周期 $C_i$密切相关。

而关键点$0\le C_i\le 8$，正是此题的突破口。

可以把 $lcm(1,2,...,8)=840$ 作为一个大周期 T。

那么
$$w_i(x)=(c_i-x\%c_i)\%c_i,表示等待时间$$

$$F_i(x)=w_i(x)+d_i+F_{i+1}((x+w_i(x)+d_i)\%840),0\le i\le n,0\le x\le 840$$

可以逆序递推，初始化所有 $F_i(x)$

这题属于 同余最小路问题

#include <bits/stdc++.h>

using namespace std;

struct S {
    int c, d;
    S() {}
    S(int c, int d)
        : c(c), d(d) {}
};

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main() {

    int n, a, b;
    cin >> n >> a >> b;

    vector<S> ss(n - 1);
    for (int i =  0; i < n - 1; i++) {
        cin >> ss[i].c >> ss[i].d;
    }
    int N = 840;
    vector<vector<int64_t>> dp(n - 1, vector<int64_t>(N + 1, 0));

    for (int j = 0; j < N; j++) {
        int c = ss[n - 2].c;
        int x = (c - j % c) % c;
        dp[n - 2][j] = x + ss[n - 2].d + b;
    }

    for (int i = n - 3; i >= 0; i--) {
        int c = ss[i].c;
        for (int j = 0; j < N; j++) {
            int d = (c - j % c) % c;
            int x = (j + d + ss[i].d) % N;
            dp[i][j] = d + ss[i].d + dp[i + 1][x];
        }
    }

    int q;
    cin >> q;
    while (q-- > 0) {
        int64_t x;
        cin >> x;
        int d = (x + a) % N;
        int64_t ans = x + a + dp[0][d];
        cout << ans << "\n";
    }

    return 0;
}

赛时，走过一些弯路，觉得这题还是有一定难度。

---

B. 异侧

这题很典，属于种类并查集。

#include <bits/stdc++.h>

using namespace std;

struct Dsu {
    int n;
    vector<int> arr;
    Dsu(int n)
        : n(n), arr(n, -1) {}
    int find(int u) {
        if (arr[u] == -1) return u;
        return arr[u] = find(arr[u]);
    }

    void unite(int u, int v) {
        int fa = find(u), fb = find(v);
        if (fa != fb) {
            arr[fa] = fb;
        }
    }
};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    vector<int> arr(m), brr(m);
    for (int &x: arr) cin >> x;
    for (int &x: brr) cin >> x;

    // dsu 即可
    Dsu dsu(n * 2 + 1);
    for (int i = 0; i < m; i++) {
        int a = arr[i], b = brr[i];
        dsu.unite(a, b + n);
        dsu.unite(b, a + n);
    }

    bool ok = true;
    for (int i = 1; i <= n; i++) {
        if (dsu.find(i) == dsu.find(i + n)) {
            ok = false;
            break;
        }
    }

    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}

---

C. 平方和的波动

数据范围
$1\le n\le 100,1\le a_i\le b_i\le 100$

单纯的分组背包，其时间复杂度为$O(n\ast 10^8)=O(10^{10})$, 显然要 TLE。

但是这题可以基于 bitset 优化， 则时间复杂度为 $O(10^{10}/w),w=32/64$

#include <bits/stdc++.h>

using namespace std;

const int N = 1000001;

int main() {
    int n;
    cin >> n;

    vector<int> arr(n), brr(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i] >> brr[i];
    }
    
    bitset<N> dp;
    dp.set(0, 1);
    for (int i = 0; i < n; i++) {
        bitset<N> dp2;
        for (int j = arr[i]; j <= brr[i]; j++) {
            dp2 |= (dp << (j * j));
        }
        dp = dp2;
    }

    int ans = 0;
    for (int i = 0; i < N; i++) {
        if (dp[i]) ans++;
    }
    cout << ans << "\n";

    return 0;
}

I. 数组划分优化

这题是划分型 DP，但是感觉被我$O(n^2\ast m)$冲过去了。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t-- > 0) {
        int n, k, m;
        cin >> n >> k >> m;

        vector<int64_t> arr(n);
        for (int64_t &x: arr) cin >> x;

        int64_t inf = (int64_t)1e18;
        vector<vector<int64_t>> dp(m, vector<int64_t>(n, inf));

        int64_t min_v = inf, max_v = -inf;
        for (int i = 0; i < n; i++) {
            min_v = min(min_v, arr[i]);
            max_v = max(max_v, arr[i]);
            if (i >= k - 1) {
                dp[0][i] = max_v - min_v;
            }
        }

        for (int a = 0; a < m - 1; a++) {
            for (int i = 0; i < n; i++) {
                if (dp[a][i] == inf) continue;
                int64_t min_v = inf;
                int64_t max_v = -inf;
                for (int j = i + 1; j < n; j++) {
                    min_v = min(min_v, arr[j]);
                    max_v = max(max_v, arr[j]);
                    if (j - i >= k) {
                        dp[a + 1][j] = min(dp[a + 1][j], dp[a][i] + max_v - min_v);
                    }
                }
            }
        }

        int64_t ans = dp[0][n - 1];
        for (int i = 1; i < m; i++) {
            ans = min(ans, dp[i][n - 1]);
        }
        cout << ans << "\n";
    }

    return 0;
}

J. 排列循环移位计数

仅保留题目描述

---

写在最后