测试了一下 deekseek-R1 的算法竞赛能力(关闭了联网搜索),让我有点失望。
根据 GitHub 上的页面:GitHub - deepseek-ai/DeepSeek-R1,deepseek-R1 的算法竞赛能力(Codeforces Rating)与 OpenAI-o1 的能力应该是不相上下的。具体而言,deepseek-R1 的 CF Rating 为 2029,稍低于 OpenAI-o1 的 2061。
于是我想着,让 Deepseek R1 来做去年 CSP-S 和 NOIP 的题,看看能打到多少分。在这里我是用的是 Deekseek 官网网页版的 R1,思考的 prompt 为:你是一位训练有素的算法竞赛选手,请使用 C++语言完成这一个算法竞赛题,测试点时间限制 1s,内存限制 512MB。 测试的试题以及评测来自于洛谷。CSP-S 2024 的第一题是决斗,这道题的难度是【普及-】,在 Codeforces 上预期也就是个 Div.2 B 难度的试题:
[CSP-S 2024] 决斗 - 洛谷deepseek-R1 在这个题上思考了 883 秒,然后生成了这个代码:- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- int n;
- cin >> n;
- vector<int> r(n);
- for (int i = 0; i < n; ++i) {
- cin >> r[i];
- }
- sort(r.begin(), r.end());
- int count = 0;
- int i = n - 1, j = i - 1;
- while (i >= 0 && j >= 0) {
- if (r[i] > r[j]) {
- count++;
- i--;
- j--;
- } else {
- j--;
- }
- if (j < 0) {
- i--;
- if (i >= 0) j = i - 1;
- }
- }
- cout << (n - count) << endl;
- return 0;
- }
复制代码 告知只能获得 40 分,要求重新检查后,又思考了 710 秒,生成了这个代码(这两份代码有什么区别?),也是只有 40 分:- #include <iostream>
- #include <vector>
- #include <algorithm>
- using namespace std;
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- int n;
- cin >> n;
- vector<int> r(n);
- for (int i = 0; i < n; ++i) {
- cin >> r[i];
- }
- sort(r.begin(), r.end());
- int count = 0;
- int i = n - 1, j = i - 1;
- while (i >= 0 && j >= 0) {
- if (r[i] > r[j]) {
- count++;
- i--;
- j--;
- } else {
- j--;
- }
- if (j < 0) {
- i--;
- if (i >= 0) j = i - 1;
- }
- }
- cout << (n - count) << endl;
- return 0;
- }
复制代码 (2025.1.28 13:28 更新:我后来又测了 2 次决斗,每次 deepseek R1 均思考了 10 分钟或者以上,最后在第 4 次尝试中 deepseek R1 通过了本题,总耗时超过 40 分钟)
接着,我测试了第二题【超速检测】,题目的难度是【普及+/提高】,题目结合了数学、二分以及贪心,是经典的算法模型的叠加,难度预期是 CF 的 Div.2C-D 之间。
[CSP-S 2024] 超速检测这个题由于不算很新的模型,在预期中 AI 应当能够用更少的时间思考得出结果。实践中 Deepseek R1 只思考了 186 秒,就写出了这个代码,获得了 60 分,可能是在一些细节处理上存在问题:- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <cmath>
- using namespace std;
- typedef pair<int, int> pii;
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- int T;
- cin >> T;
- while (T--) {
- int n, m, L, V;
- cin >> n >> m >> L >> V;
- vector<int> p(m);
- vector<pair<int, int>> intervals;
- vector<int> d(n), v(n), a(n);
- for (int i = 0; i < n; ++i) {
- cin >> d[i] >> v[i] >> a[i];
- }
- for (int j = 0; j < m; ++j) {
- cin >> p[j];
- }
- int ans1 = 0;
- for (int i = 0; i < n; ++i) {
- int di = d[i], vi = v[i], ai = a[i];
- double S_i;
- if (ai >= 0) {
- S_i = L - di;
- if (S_i < 0) S_i = 0;
- } else {
- double s0_stop = (vi * 1.0 * vi) / (2.0 * (-ai));
- double max_s = L - di;
- S_i = min(s0_stop, max_s);
- if (S_i < 0) S_i = 0;
- }
- if (S_i <= 0) continue;
- bool valid = false;
- double l, r;
- bool left_closed, right_closed;
- if (ai == 0) {
- if (vi > V) {
- valid = true;
- left_closed = true;
- right_closed = true;
- l = di;
- r = L;
- } else {
- valid = false;
- }
- } else if (ai > 0) {
- if (vi >= V) {
- valid = true;
- left_closed = true;
- right_closed = true;
- l = di;
- r = di + S_i;
- } else {
- double s0 = (V*1.0*V - vi*vi) / (2.0 * ai);
- if (s0 > S_i) {
- valid = false;
- } else {
- valid = true;
- left_closed = false;
- right_closed = true;
- l = di + s0;
- r = di + S_i;
- }
- }
- } else {
- if (vi <= V) {
- valid = false;
- } else {
- double s0_speed = (V*1.0*V - vi*vi) / (2.0 * ai);
- double s0_stop = (vi*1.0 * vi) / (2.0 * (-ai));
- double max_s = L - di;
- double actual_s = min(s0_stop, max_s);
- double actual_s_speed = min(s0_speed, actual_s);
- if (actual_s_speed <= 0) {
- valid = false;
- } else {
- valid = true;
- left_closed = true;
- right_closed = false;
- l = di;
- r = di + actual_s_speed;
- }
- }
- }
- if (!valid) continue;
- vector<int>::iterator start_it, end_it;
- if (left_closed) {
- start_it = lower_bound(p.begin(), p.end(), l);
- } else {
- start_it = upper_bound(p.begin(), p.end(), l);
- }
- if (right_closed) {
- end_it = upper_bound(p.begin(), p.end(), r);
- } else {
- end_it = lower_bound(p.begin(), p.end(), r);
- }
- int start_idx = start_it - p.begin();
- int end_idx = (end_it - p.begin()) - 1;
- if (start_idx <= end_idx) {
- ans1++;
- intervals.emplace_back(start_idx, end_idx);
- }
- }
- int ans2 = 0;
- if (!intervals.empty()) {
- sort(intervals.begin(), intervals.end(), [](const pii& a, const pii& b) {
- return a.second < b.second;
- });
- int last = -1;
- int count = 0;
- for (const auto& interval : intervals) {
- int s = interval.first;
- int e = interval.second;
- if (s > last) {
- count++;
- last = e;
- }
- }
- ans2 = m - count;
- } else {
- ans2 = m;
- }
- cout << ans1 << &#39; &#39; << ans2 << &#39;\n&#39;;
- }
- return 0;
- }
复制代码 超速检测这一题我没有给予更多的测试(其中一个原因是现在 Deepseek R1 太卡)。后面两个题难度更高,我也不再进行测试。很明显,Deepseek R1 在 CSP-S 2024 中表现得很惨淡,前两个题没有一个能一次通过,甚至在非常简单的决斗一题中表现特别不理想。这个水平不像是具有 CF Rating 2000 的选手。
随后我测试了 NOIP 2024。NOIP 2024 的难度是更高的,但是 Openai-o1 的表现还算不错,我还是对 Deepseek 的表现比较期待。结果实际上的表现很不尽如人意。
NOIP 2024 的第一题是编辑字符串。这一道题目是贪心题,不算太好想,代码编写有一定细节难度,有一些省一水平选手在这个题上也翻了车,难度对标 CF 的 Div.2 D-E:
[NOIP2024] 编辑字符串Deepseek R1 首先思考了 292 秒,生成了如下代码,这份代码取得了 0 分:- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- void preprocess(const string &s, const string &t, vector<int> &count0, vector<int> &count1) {
- int n = s.size();
- int current_start = -1;
- int cnt0 = 0, cnt1 = 0;
- for (int i = 0; i < n; ++i) {
- if (t[i] == &#39;1&#39;) {
- if (current_start == -1) {
- current_start = i;
- cnt0 = 0;
- cnt1 = 0;
- }
- if (s[i] == &#39;0&#39;) cnt0++;
- else cnt1++;
- } else {
- if (current_start != -1) {
- for (int j = current_start; j < i; ++j) {
- count0[j] = cnt0;
- count1[j] = cnt1;
- }
- current_start = -1;
- }
- }
- }
- if (current_start != -1) {
- for (int j = current_start; j < n; ++j) {
- count0[j] = cnt0;
- count1[j] = cnt1;
- }
- }
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(0);
- int T;
- cin >> T;
- while (T--) {
- int n;
- cin >> n;
- string s1, s2, t1, t2;
- cin >> s1 >> s2 >> t1 >> t2;
- vector<int> c1_0(n, 0), c1_1(n, 0);
- preprocess(s1, t1, c1_0, c1_1);
- vector<int> c2_0(n, 0), c2_1(n, 0);
- preprocess(s2, t2, c2_0, c2_1);
- int ans = 0;
- for (int i = 0; i < n; ++i) {
- bool a_fixed = (t1[i] == &#39;0&#39;);
- bool b_fixed = (t2[i] == &#39;0&#39;);
- if (a_fixed && b_fixed) {
- if (s1[i] == s2[i]) ans++;
- } else if (a_fixed) {
- char c = s1[i];
- if (c == &#39;0&#39; && c2_0[i] > 0) ans++;
- else if (c == &#39;1&#39; && c2_1[i] > 0) ans++;
- } else if (b_fixed) {
- char c = s2[i];
- if (c == &#39;0&#39; && c1_0[i] > 0) ans++;
- else if (c == &#39;1&#39; && c1_1[i] > 0) ans++;
- } else {
- if ((c1_0[i] > 0 && c2_0[i] > 0) || (c1_1[i] > 0 && c2_1[i] > 0)) {
- ans++;
- }
- }
- }
- cout << ans << &#39;\n&#39;;
- }
- return 0;
- }
复制代码 它总结了自己的做法如下:方法思路
预处理块结构:将每个字符串分割成由不可交换字符分隔的可交换块,并统计每个块中的 0 和 1 的数量。
判断每个位置的可匹配性:根据每个位置的可交换性,判断是否可以通过调整使得该位置的字符相同。
具体步骤如下:
预处理块结构:遍历每个字符串的可交换标记,确定每个块的范围及其字符统计信息。
逐个位置判断:根据每个位置的可交换性和对应块的字符统计信息,判断该位置是否可以调整为相同字符。 然后,告知了它大样例中满足字符串长度不超过 10 的前两组数据,然后 R1 连续思考了 30 分钟直接被掐断。本题不再继续进行测试。
接着是第二题遗失的赋值:
[NOIP2024] 遗失的赋值这是一道组合计数题,需要选手熟练地运用乘法原理这个基础的组合计数模型完成该题,难度对标 CF 的 Div.2D。这一题 OpenAI-o1 可以通过,而 Deepseek R1 经过了 552 秒的思考生成了这个代码,获得了 35 分。它有意识地去拆了贡献去计算答案,但是很遗憾思考流程貌似是有问题的。- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int MOD = 1e9 + 7;
- ll pow_mod(ll a, ll b) {
- ll res = 1;
- a %= MOD;
- while (b > 0) {
- if (b % 2 == 1) res = (res * a) % MOD;
- a = (a * a) % MOD;
- b /= 2;
- }
- return res;
- }
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
-
- int T;
- cin >> T;
- while (T--) {
- int n, m, v;
- cin >> n >> m >> v;
- unordered_map<int, int> fixed;
- bool conflict = false;
- for (int i = 0; i < m; ++i) {
- int c, d;
- cin >> c >> d;
- if (fixed.count(c)) {
- if (fixed[c] != d) conflict = true;
- } else {
- fixed[c] = d;
- }
- }
- if (conflict) {
- cout << 0 << &#39;\n&#39;;
- continue;
- }
- vector<int> sorted_c;
- for (auto& p : fixed) sorted_c.push_back(p.first);
- sort(sorted_c.begin(), sorted_c.end());
- int cnt = 0;
- for (int i = 1; i < sorted_c.size(); ++i) {
- if (sorted_c[i] == sorted_c[i-1] + 1) cnt++;
- }
- ll k = (1 + (ll)v * (v - 1)) % MOD;
- ll term1 = pow_mod(k, cnt);
- ll exponent = n - 1 - cnt;
- ll v_sq = ((ll)v % MOD) * (v % MOD) % MOD;
- ll term2 = pow_mod(v_sq, exponent);
- ll ans = (term1 * term2) % MOD;
- cout << ans << &#39;\n&#39;;
- }
-
- return 0;
- }
复制代码 Openai-o1 通过本题的代码:- #include <bits/stdc++.h>
- using namespace std;
- const int MOD = 1000000007;
- long long qpow(long long base, long long exp) {
- long long res = 1 % MOD;
- long long cur = base % MOD;
- while (exp > 0) {
- if (exp & 1) res = (res * cur) % MOD;
- cur = (cur * cur) % MOD;
- exp >>= 1;
- }
- return res;
- }
- int main(){
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
-
- int T; cin >> T;
- while(T--){
- long long n,v;
- int m;
- cin >> n >> m >> v;
- map<long long, long long> fixedVars;
- bool conflict = false;
- vector<long long> vars; vars.reserve(m);
- for(int i=0;i<m;i++){
- long long c,d;cin>>c>>d;
- auto it = fixedVars.find(c);
- if(it!=fixedVars.end()){
- if(it->second!=d) conflict=true;
- } else {
- fixedVars[c]=d;
- vars.push_back(c);
- }
- }
-
- if(conflict){
- cout<<0<<&#34;\n&#34;;
- continue;
- }
-
- sort(vars.begin(), vars.end());
-
- // 加虚拟端点
- // c_0=0, c_{m+1}=n+1
- vector<long long> c;
- c.push_back(0);
- for (auto x: vars) c.push_back(x);
- c.push_back(n+1);
-
- long long ans = 1;
- long long v2 = (v%MOD)*(v%MOD)%MOD;
-
- for (int i=0; i<(int)c.size()-1; i++){
- long long left = c[i], right = c[i+1];
- long long L = right - left;
- // 判断端点固定情况
- bool left_fixed = (left!=0 && left!=n+1 && fixedVars.count(left));
- bool right_fixed = (right!=0 && right!=n+1 && fixedVars.count(right));
-
- long long seg_ans = 1;
- if (left_fixed && right_fixed) {
- // 双端固定
- // k = c_{j+1}-c_j(即L)
- long long k = L;
- if (k <= 0) {
- // 不可能k<=0,因为c_{j+1}>c_j
- // 但若刚好相邻 c_{j+1}=c_j+1 则k=1,一条边
- // 若 c_{j+1}=c_j+2 则 k=2 两条边,...
- // 此处k必然>=1
- seg_ans = 1;
- } else {
- // (v^2)^k
- long long part1 = qpow(v2, k);
- // (v-1)*v^{k-1}
- if (k==1) {
- // 特殊:v^{0}=1
- long long part2 = ((v-1)%MOD+MOD)%MOD;
- seg_ans = (part1 - part2) % MOD;
- } else {
- long long part2 = ((v-1)%MOD)*qpow(v, k-1)%MOD;
- seg_ans = (part1 - part2) % MOD;
- }
- if(seg_ans<0) seg_ans+=MOD;
- }
- } else {
- // 至少一端不固定
- // k = L - 1
- // 若 L=1,即相差1,比如(0,1)无边 k=0
- // 若 L=2,比如(0,3),中间有1,2两个变量,则有1条边 k=1
- long long k = L - 1;
- if (k>0) {
- seg_ans = qpow(v2, k);
- } else {
- // k<=0,没有边
- seg_ans = 1;
- }
- }
-
- ans = (ans * seg_ans) % MOD;
- }
-
- cout << ans % MOD << &#34;\n&#34;;
- }
-
- return 0;
- }
复制代码 NOIP 2024 后两个题难度更高,也不再进行测试。但是就目前来看,不管是 CSP-S 还是 NOIP,deepseek R1 的得分表现看起来只有省三等奖-二等奖的水平,在算法竞赛方面不具有竞争性,很难说具有【CF Rating 2000 左右的算法竞赛能力】。
最后我测了一道 12 月洛谷月赛的题,这是一道构造题,难度相当于 CF 的 Div.2C:
「Cfz Round 5」Mata rainenDeepseek R1 在经过长达 1566 秒的思考(可能是使用高峰期,输出效率明显慢了很多,就当它慢了 67%,那也是 500 秒的思考),给出了一个依赖于度数的错误构造方式:- #include <bits/stdc++.h>
- using namespace std;
- int main() {
- ios::sync_with_stdio(false);
- cin.tie(nullptr);
- int n, m;
- cin >> n >> m;
- vector<int> cnt(n + 1);
- for (int i = 0; i < m; ++i) {
- int s, t;
- cin >> s >> t;
- cnt[s]++;
- cnt[t]++;
- }
- vector<int> odd_nodes;
- for (int i = 1; i <= n; ++i) {
- if (cnt[i] % 2 != 0) {
- odd_nodes.push_back(i);
- }
- }
- int k = odd_nodes.size();
- if (k % 2 != 0 || k < 2) {
- cout << &#34;No\n&#34;;
- return 0;
- }
- int c = -1;
- for (int i = 1; i <= n; ++i) {
- if (cnt[i] % 2 == 0) {
- c = i;
- break;
- }
- }
- if (c == -1) {
- cout << &#34;No\n&#34;;
- return 0;
- }
- vector<int> other_nodes;
- for (int i = 1; i <= n; ++i) {
- if (i != c && cnt[i] % 2 == 0) {
- other_nodes.push_back(i);
- }
- }
- if (other_nodes.empty() && k >= 2) {
- cout << &#34;No\n&#34;;
- return 0;
- }
- vector<pair<int, int>> edges;
- int m_node = (other_nodes.empty() ? c : other_nodes[0]);
- int pairs = k / 2;
- for (int i = 0; i < pairs - 1; ++i) {
- int s = odd_nodes[2 * i];
- int t = odd_nodes[2 * i + 1];
- edges.emplace_back(s, c);
- edges.emplace_back(t, c);
- }
- int remaining = k - 2 * (pairs - 1);
- if (remaining == 2) {
- int s = odd_nodes[k - 2];
- int t = odd_nodes[k - 1];
- edges.emplace_back(s, c);
- if (!other_nodes.empty()) {
- edges.emplace_back(c, m_node);
- edges.emplace_back(m_node, t);
- } else {
- edges.emplace_back(c, t);
- }
- }
- set<int> used;
- for (auto &p : edges) {
- used.insert(p.first);
- used.insert(p.second);
- }
- for (int i = 1; i <= n; ++i) {
- if (used.count(i)) continue;
- if (edges.empty()) {
- edges.emplace_back(i, c);
- } else {
- edges.emplace_back(i, edges.back().first);
- }
- }
- if (edges.size() != n - 1) {
- cout << &#34;No\n&#34;;
- return 0;
- }
- cout << &#34;Yes\n&#34;;
- for (auto &p : edges) {
- cout << p.first << &#39; &#39; << p.second << &#39;\n&#39;;
- }
- return 0;
- }
复制代码 这个构造也是完全错误的。综合上面的一些实践,我认为虽然 Deepseek R1 具有很强的文字工作能力,但是在编程特别是算法竞赛能力表现很不理想,也欢迎各位继续提供一些案例,来证明/证伪 Deepseek R1 具有相当于 CF 紫名的水平。 |
|