【整活向】让 DeepSeek 考 2024 CSP-S

szh_DNCB · 3月2日

原文网址：在这里

具体内容：

省流

$100+80+0+0 = 180$pts，压线蓝勾。

准备工作

受到 chenzhe 帖子下评论的启发，我用一个新登录的账号测试 DeepSeek-R1 在允许上网 ctj 的情况下的 2024 CSP-S2 成绩。

为了让测试有一定对比性，我的 prompt 与 chenzhe 的一样，是：

你是一位训练有素的算法竞赛选手，请使用 C++ 语言完成这一个算法竞赛题，测试点时间限制 1s，内存限制 512MB。

T1 决斗

先来看决斗。虽然在不 ctj 情况下 DeepSeek 只能获得 60pts 高分，但是如果能够作弊，它的分应该不低吧。

喂进去题目，DeepSeek 先想到了贪心，但是大约 $309$ 秒后，很快又想到了正确思路——二分算法。

DeepSeek 代码如下。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> r(n);
    for (int i = 0; i < n; ++i) {
        cin >> r[i];
    }
    sort(r.begin(), r.end());
    
    int low = 0, high = n;
    int best = 0;
    while (low <= high) {
        int mid = (low + high) / 2;
        bool valid = true;
        for (int i = 0; i < mid; ++i) {
            if (r[i] >= r[n - mid + i]) {
                valid = false;
                break;
            }
        }
        if (valid) {
            best = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    
    cout << (n - best) << endl;
    return 0;
}

输入洛谷，发现获得了 100 分的好成绩！

我的测试信心一下子上来了。继续！

T2 超速检测

这题很明显对 AI 的数学要求较高。而 DeepSeek 自称擅长这个方面，所以测试之前我觉得它至少有 60pts。（可惜的是，在不联网情况下他只有 40）

把题喂给 DeepSeek，然后就加载了很久。。。太火爆了吧。

只有等啊等啊等啊等。

然后他就写啊写啊写啊写。

大约用了 $711$ 秒给出代码。（我也不知道为啥 chenzhe 测的时候只用了 $3$ min）它的代码逻辑是二分判断测速仪是否在超速区间内；同时贪心选择最少的测速仪覆盖所有区间。但是代码还是使用的 double 类型而非两边平方之后再用 int。

代码一共 4.22 KB，如下：

#include <bits/stdc++.h>
using namespace std;

using pdd = pair<double, double>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;

    while (T--) {
        int n, m, L, V;
        cin >> n >> m >> L >> V;

        vector<int> d(n), v(n), a(n);
        for (int i = 0; i < n; ++i) {
            cin >> d[i] >> v[i] >> a[i];
        }

        vector<int> p(m);
        for (int i = 0; i < m; ++i) {
            cin >> p[i];
        }

        sort(p.begin(), p.end());

        int ans1 = 0;
        vector<pdd> intervals;

        for (int i = 0; i < n; ++i) {
            double di = d[i], vi = v[i], ai = a[i];
            double s_total = 0.0;

            if (ai == 0) {
                s_total = L - di;
                if (s_total <= 0) continue;
                if (vi <= V) continue;

                double low = di;
                double high = di + s_total;

                int left = lower_bound(p.begin(), p.end(), low) - p.begin();
                int right = upper_bound(p.begin(), p.end(), high) - p.begin();
                if (left < right) {
                    ans1++;
                    intervals.emplace_back(low, high);
                }
            } else if (ai > 0) {
                s_total = L - di;
                if (s_total <= 0) continue;

                if (V < vi) {
                    double low = di;
                    double high = di + s_total;

                    int left = lower_bound(p.begin(), p.end(), low) - p.begin();
                    int right = upper_bound(p.begin(), p.end(), high) - p.begin();
                    if (left < right) {
                        ans1++;
                        intervals.emplace_back(low, high);
                    }
                } else {
                    double numerator = V * V - vi * vi;
                    double denominator = 2.0 * ai;
                    double s0 = numerator / denominator;
                    double s_start = max(s0, 0.0);

                    if (s_start >= s_total) continue;

                    double low = di + s_start + 1e-9;
                    double high = di + s_total;

                    int left = lower_bound(p.begin(), p.end(), low) - p.begin();
                    int right = upper_bound(p.begin(), p.end(), high) - p.begin();
                    if (left < right) {
                        ans1++;
                        intervals.emplace_back(low, high);
                    }
                }
            } else {
                if (V >= vi) continue;

                double numerator = V * V - vi * vi;
                double denominator = 2.0 * ai;
                double s0 = numerator / denominator;

                double s_max = (vi * vi) / (-2.0 * ai);
                s_total = min(s_max, L - di);
                if (s_total <= 0) continue;

                double s_end = min(s0, s_total);
                if (s_end <= 0) continue;

                double low = di;
                double high = di + s_end - 1e-9;

                int left = lower_bound(p.begin(), p.end(), low) - p.begin();
                int right = upper_bound(p.begin(), p.end(), high) - p.begin();
                if (left < right) {
                    ans1++;
                    intervals.emplace_back(low, high);
                }
            }
        }

        sort(intervals.begin(), intervals.end(), [](const pdd& a, const pdd& b) {
            return a.second < b.second;
        });

        int cnt = 0;
        double last = -1e18;
        for (auto& interval : intervals) {
            double l = interval.first;
            double r = interval.second;
            if (l > last) {
                auto it = upper_bound(p.begin(), p.end(), r);
                if (it == p.begin()) {
                    assert(false);
                }
                --it;
                double point = *it;
                if (point >= l) {
                    last = point;
                    cnt++;
                } else {
                    assert(false);
                }
            }
        }

        int ans2 = m - cnt;
        cout << ans1 << ' ' << ans2 << '\n';
    }

    return 0;
}

上交到洛谷，80 pts（WA on #9,#10）！这个成绩已经优于我的预期了。更何况不带联网只有 40 pts 呢。

下一题！

T3 染色

染色也是偏数学的题目，码量不大。

交给 DeepSeek 处理，这次没有加载太久，很快就开始思考了。

看思考的过程中，我发现这个思考过程其实很不通顺，但是和我思考过程差不多（全是或者、所以一类的词）。

但是我依然不理解，这是什么东西啊喂！

切回正题，DeepSeek 给出了一种贪心思路，但是又被自己证伪；然后它又想到了维护每个颜色的最后出现元素的数值来做 dp，然后又给自己证伪。

最后花费约 $769$ 秒，它终于选择了写法：将相同数值的元素尽可能染成同一颜色，使得每个后续元素都能获得前一个相同数值元素的贡献。

不出所料，代码不长，仅有 558 B。大致是这样的：

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> A(n);
        unordered_map<int, int> cnt;

        for (int i = 0; i < n; ++i) {
            cin >> A[i];
            cnt[A[i]]++;
        }

        long long ans = 0;
        for (auto& [num, count] : cnt) {
            ans += 1LL * (count - 1) * num;
        }

        cout << ans << '\n';
    }

    return 0;
}

可惜的是，这份代码获得 0pts 的高分。这使我对 DeepSeek 声称的 CF 2000 Rating 产生了深深的质疑。

T4 擂台游戏

这个题目我测之前就猜到肯定不能做，看个乐呵吧。

喂进去，然后：

。。。。。。

你真棒。

没办法，只能等亿会儿。

等了将近一个小时发现可以了，但是思考过程太冗长了，所以这里略过。直接看 DeepSeek 经过 $1247$ 秒思考后，最后的思路和代码。

以下是 DeepSeek 的思路：

预处理比赛结构：确定每个选手在每轮比赛中的对手和擂主信息。
动态计算选手条件：对于每个测试数据，动态计算每个选手在每轮比赛中是否满足条件。
快速查询结果：使用前缀和数组和线段树等数据结构，快速查询满足条件的选手编号之和。

代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 5;
const int MAXK = 20;

int n, m, K;
vector<int> a_prime;
vector<int> c;
vector<string> d_str;
int T;

struct Node {
    int k;
    vector<pair<int, int>> rounds; // (R, y)
};
vector<Node> supp_conditions;

vector<int> a;
vector<int> R_max;

vector<vector<int>> sum_original;
vector<ll> sum_supp;

vector<int> log2_table;

void precompute_log2() {
    log2_table.resize(1 << (MAXK + 1));
    for (int i = 0; i <= MAXK; ++i) {
        int start = 1 << i;
        int end = 1 << (i + 1);
        for (int j = start; j < end; ++j) {
            if (j >= log2_table.size()) break;
            log2_table[j] = i;
        }
    }
}

void precompute_supp_conditions(int max_k) {
    supp_conditions.clear();
    int max_size = 1 << max_k;
    supp_conditions.resize(max_size + 1);
    for (int x = 1; x <= max_size; ++x) {
        vector<pair<int, int>> rounds;
        int pos = x;
        for (int R = 1; R <= max_k; ++R) {
            int group_size = 1 << (R);
            int group = (pos - 1) / group_size;
            int start = group * group_size + 1;
            int mid = start + group_size / 2 - 1;
            int g = (pos <= mid) ? (pos - start) / (1 << (R - 1)) : (pos - mid - 1) / (1 << (R - 1));
            char d = d_str[R-1][g];
            int other;
            if (d == '0') {
                if (pos % 2 == 1) other = pos + 1;
                else other = pos - 1;
            } else {
                if (pos % 2 == 1) other = pos + 1;
                else other = pos - 1;
                other = (pos + other) / 2;
                if (pos < other) other = pos * 2 - 1;
                else other = pos * 2;
            }
            int y = (d == '0') ? min(pos, other) : max(pos, other);
            if (y != pos) {
                rounds.emplace_back(R, y);
            }
            pos = (pos + 1) / 2;
        }
        supp_conditions[x].k = max_k;
        supp_conditions[x].rounds = rounds;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precompute_log2();

    cin >> n >> m;
    a_prime.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> a_prime[i];
    }
    c.resize(m);
    for (int i = 0; i < m; ++i) {
        cin >> c[i];
    }
    K = 0;
    while ((1 << K) < n) K++;
    d_str.resize(K);
    for (int R = 0; R < K; ++R) {
        cin >> d_str[R];
    }
    cin >> T;

    precompute_supp_conditions(K);

    while (T--) {
        int X[4];
        for (int j = 0; j < 4; ++j) {
            cin >> X[j];
        }
        a.resize(n + 1);
        for (int i = 1; i <= n; ++i) {
            a[i] = a_prime[i] ^ X[(i-1) % 4];
        }

        R_max.assign(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            int pos = i;
            bool ok = true;
            int current_max = 0;
            for (int R = 1; R <= K; ++R) {
                int group_size = 1 << R;
                int group = (pos - 1) / group_size;
                int start = group * group_size + 1;
                int mid = start + group_size / 2 - 1;
                int g = (pos <= mid) ? (pos - start) / (1 << (R - 1)) : (pos - mid - 1) / (1 << (R - 1));
                char d = d_str[R-1][g];
                int other;
                if (d == '0') {
                    other = (pos % 2 == 1) ? pos + 1 : pos - 1;
                } else {
                    other = (pos % 2 == 1) ? pos + 1 : pos - 1;
                }
                int y = (d == '0') ? min(pos, other) : max(pos, other);
                if (y == pos) {
                    if (a[pos] < R) {
                        ok = false;
                        break;
                    }
                } else {
                    if (y > n || a[y] >= R) {
                        ok = false;
                        break;
                    }
                }
                pos = (pos + 1) / 2;
                current_max = R;
            }
            if (ok) R_max[i] = current_max;
            else R_max[i] = -1;
        }

        vector<vector<ll>> sum_k(K + 2, vector<ll>(n + 1, 0));
        for (int k = 1; k <= K; ++k) {
            ll sum = 0;
            for (int i = 1; i <= n; ++i) {
                if (R_max[i] >= k) {
                    sum += i;
                }
                sum_k[k][i] = sum;
            }
        }

        vector<ll> res(m, 0);
        for (int q = 0; q < m; ++q) {
            int ci = c[q];
            if (ci == 0) {
                res[q] = 0;
                continue;
            }
            int k = log2_table[ci];
            if ((1 << k) < ci) k++;
            int size = 1 << k;
            ll ans = 0;

            if (ci > 0) {
                ans += sum_k[k][min(ci, n)];
            }

            int supp_start = ci + 1;
            int supp_end = size;
            if (supp_start > supp_end) {
                res[q] = ans;
                continue;
            }

            for (int x = supp_start; x <= supp_end; ++x) {
                bool valid = true;
                for (auto& p : supp_conditions[x].rounds) {
                    int R = p.first;
                    int y = p.second;
                    if (y > ci) continue;
                    if (y > n) continue;
                    if (a[y] >= R) {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    ans += x;
                }
            }

            res[q] = ans;
        }

        ll final = 0;
        for (int i = 0; i < m; ++i) {
            final ^= (i + 1) * res[i];
        }
        cout << final << '\n';
    }

    return 0;
}

以下是 DeepSeek 的代码解释：

预处理：计算每个可能的补充选手的路径中的擂主信息。
动态计算：根据每个测试数据中的能力值，动态计算每个选手的最大轮次。
快速查询：使用前缀和数组和遍历处理补充选手的条件，快速得到结果。

然后是提交洛谷。这份长达 5.79 KB 的代码不出意外地获得 0pts 的成绩，并且 WA on #1 - #12，TLE on #13 - #25。

考虑到 DeepSeek 的糟糕表现，本来想让它继续测 NOIp 的心情也一扫而空了。

总结

DeepSeek 在不到一小时的时间里一共获得了 $100 + 80 + 0 + 0 = 180$pts。虽然说并不是很高，但是仍然压线获得 $6$ 级勾子，碾压包括我在内的一众 OIer。

当然，正如 chenzhe 所说，DeepSeek 在解决简单问题和板子题时还是比较稳定的；但是一旦上一点难度（哪怕真的只有一点），其表现就极其不稳定。

恐怕 CF 2000 分的宣传，在我们手上，还真的不那么方便复现（绿题都切不出来）。

当然，DeepSeek 已经比 GPT-4o 前进了一步，也许在未来，会有更加优秀的大语言模型，也许在之后，大语言模型可以达到 $7$ 甚至 $8$ 级勾子，比绝大多数人类更强大，真正达到让 AI 写 AI 的境界。

AI 之路，任重而道远。

szh_DNCB · 3月2日

LateX 挂了。建议到原文观看。

szh_DNCB · 3月2日

szh_DNCB · 3月2日

另外，原文是讨论区没死的时候写的，所以一些链接可能被封了

SwallowedStar · 3月2日

szh_DNCB · 3月2日

🔮 抽取今日运势

【整活向】让 DeepSeek 考 2024 CSP-S

szh_DNCB

具体内容：

省流

准备工作

T1 决斗

T2 超速检测

T3 染色

T4 擂台游戏

总结

szh_DNCB

szh_DNCB

szh_DNCB

SwallowedStar

szh_DNCB

社区导航

帮助中心

相关链接

备案信息