让问小白的 DeepSeek V3/R1 打今年的 S，能拉爆我吗？
::::info[AI 使用说明]{open} 本文所有的代码均为 AI 生成。 ::::
本人今年打炸了，
问题：
用 C++ 做这道信息学竞赛题目，评测环境为 C++14 O2，不加文件读写：[洛谷题面，复制 markdown]开深度思考，关联网搜索。评测语言为 C++14 O2。
尽可能让其完整思考即不会主动跳过思考，但要是死循环那就不算我的了。
T1（社团招新，club）
思考过程死循环了一直 and and and，遂跳过。
code：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct Member {
int a, b, c;
};
long long solve_case(int n, vector<Member>& members) {
int max_per_dept = n / 2;
long long res = 0;
// Consider all possible combinations of two departments that can have up to max_per_dept members.
// There are 3 cases: (1,2), (1,3), (2,3)
for (int dept1 = 1; dept1 <= 3; ++dept1) {
for (int dept2 = dept1 + 1; dept2 <= 3; ++dept2) {
long long total = 0;
vector<int> diff1, diff2, diff3;
for (auto& m : members) {
int best = max({m.a, m.b, m.c});
if (best == m.a && dept1 == 1 || best == m.b && dept1 == 2 || best == m.c && dept1 == 3) {
total += best;
} else if (best == m.a && dept2 == 1 || best == m.b && dept2 == 2 || best == m.c && dept2 == 3) {
total += best;
} else {
// Member is not in dept1 or dept2, so they must choose their best remaining option (dept3)
int third_dept = 6 - dept1 - dept2;
int val = (third_dept == 1) ? m.a : (third_dept == 2) ? m.b : m.c;
total += val;
}
}
// Now, we need to check if the counts of dept1 and dept2 members do not exceed max_per_dept.
// To model this, we may need to move some members from dept1 or dept2 to the third department, selecting those with minimal (a[i][dept1] - a[i][third_dept]) differences.
vector<int> dept1_members, dept2_members;
for (auto& m : members) {
int best = max({m.a, m.b, m.c});
int chosen_dept = -1;
if (best == m.a) chosen_dept = 1;
else if (best == m.b) chosen_dept = 2;
else if (best == m.c) chosen_dept = 3;
if (chosen_dept == dept1) {
int third_dept = 6 - dept1 - dept2;
int val_dept = (dept1 == 1) ? m.a : (dept1 == 2) ? m.b : m.c;
int val_third = (third_dept == 1) ? m.a : (third_dept == 2) ? m.b : m.c;
dept1_members.push_back(val_dept - val_third);
} else if (chosen_dept == dept2) {
int third_dept = 6 - dept1 - dept2;
int val_dept = (dept2 == 1) ? m.a : (dept2 == 2) ? m.b : m.c;
int val_third = (third_dept == 1) ? m.a : (third_dept == 2) ? m.b : m.c;
dept2_members.push_back(val_dept - val_third);
}
}
int cnt1 = dept1_members.size();
int cnt2 = dept2_members.size();
sort(dept1_members.begin(), dept1_members.end());
sort(dept2_members.begin(), dept2_members.end());
// Compute the minimal loss if we need to move some members from dept1 or dept2.
long long current_total = total;
int moves1 = max(0, cnt1 - max_per_dept);
int moves2 = max(0, cnt2 - max_per_dept);
if (moves1 + moves2 <= (n - cnt1 - cnt2)) {
// We can balance by moving moves1 from dept1 and moves2 from dept2.
long long loss = 0;
for (int i = 0; i < moves1; ++i) {
loss += dept1_members[i];
}
for (int i = 0; i < moves2; ++i) {
loss += dept2_members[i];
}
current_total -= loss;
res = max(res, current_total);
} else {
// We can have up to moves = (moves1 + moves2 - available), but the condition in the problem ensures that it's possible to have at most two departments at max_per_dept.
// So adjust cnt1 to exactly max_per_dept, and the rest to the third or cnt2 to max_per_dept.
// Find the minimal loss to ensure that cnt1 <= max_per_dept and cnt2 <= max_per_dept.
int possible_moves1 = min(moves1, cnt1);
int required_moves1 = cnt1 - max_per_dept;
if (required_moves1 >= 0) {
long long loss1 = 0;
for (int i = 0; i < required_moves1; ++i) {
loss1 += dept1_members[i];
}
int remaining_moves = max(0, cnt2 - (max_per_dept));
long long loss2 = 0;
if (remaining_moves > 0) {
for (int i = 0; i < remaining_moves; ++i) {
loss2 += dept2_members[i];
}
}
current_total -= (loss1 + loss2);
res = max(res, current_total);
}
}
}
}
// Also consider the case where only one department reaches max_per_dept, and the others are below.
for (int dept = 1; dept <= 3; ++dept) {
long long total = 0;
vector<int> diff_list;
for (auto& m : members) {
// Select between the other two departments.
int other1 = (dept % 3) + 1;
int other2 = ((dept + 1) % 3) + 1;
if (other2 == dept) other2 = other1;
int val_dept = (dept == 1) ? m.a : (dept == 2) ? m.b : m.c;
int val_other1 = (other1 == 1) ? m.a : (other1 == 2) ? m.b : m.c;
int val_other2 = (other2 == 1) ? m.a : (other2 == 2) ? m.b : m.c;
int best = max(val_other1, val_other2);
total += best;
if (best == val_dept) {
diff_list.push_back(val_dept - min(val_other1, val_other2));
}
}
sort(diff_list.begin(), diff_list.end());
int cnt = diff_list.size();
if (cnt > max_per_dept) {
long long loss = 0;
for (int i = 0; i < cnt - max_per_dept; ++i) {
loss += diff_list[i];
}
total -= loss;
}
res = max(res, total);
}
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<Member> members(n);
for (int i = 0; i < n; ++i) {
cin >> members[i].a >> members[i].b >> members[i].c;
}
cout << solve_case(n, members) << '\n';
}
return 0;
}评测记录，居然获得了高达
T2（道路修复，road）
code：
#include <iostream>
#include <vector>
#include <algorithm>
#include <cctype>
#include <climits>
#include <cmath>
using namespace std;
typedef long long LL;
struct Edge {
LL w;
int type;
int u, v;
Edge() {}
Edge(LL w, int type, int u, int v) : w(w), type(type), u(u), v(v) {}
bool operator<(const Edge& other) const {
return w < other.w;
}
};
struct DSU {
vector<int> parent;
vector<int> rank;
DSU(int n) {
parent.resize(n);
rank.resize(n, 0);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
bool unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return false;
if (rank[x] < rank[y]) {
parent[x] = y;
} else if (rank[x] > rank[y]) {
parent[y] = x;
} else {
parent[y] = x;
rank[x]++;
}
return true;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
vector<Edge> all_edges;
for (int i = 0; i < m; i++) {
int u, v;
LL w;
cin >> u >> v >> w;
u--; v--;
all_edges.push_back(Edge(w, -1, u, v));
}
vector<LL> town_costs(k, 0);
for (int j = 0; j < k; j++) {
cin >> town_costs[j];
for (int i = 0; i < n; i++) {
LL a;
cin >> a;
all_edges.push_back(Edge(a, j, i, n + j));
}
}
sort(all_edges.begin(), all_edges.end());
int total_edges = all_edges.size();
LL ans = (LL)1e18;
DSU dsu0(n);
LL mst0 = 0;
int count0 = 0;
for (int i = 0; i < total_edges; i++) {
if (count0 == n - 1) break;
const Edge& e = all_edges[i];
if (e.type != -1) continue;
if (dsu0.unite(e.u, e.v)) {
mst0 += e.w;
count0++;
}
}
if (count0 == n - 1) {
ans = min(ans, mst0);
}
for (int S = 1; S < (1 << k); S++) {
LL cost_s = 0;
int cnt_towns = __builtin_popcount(S);
for (int j = 0; j < k; j++) {
if (S & (1 << j)) {
cost_s += town_costs[j];
}
}
DSU dsu(n + k);
int count_edges = 0;
LL mst_val = 0;
int total_nodes = n + cnt_towns;
int required_edges = total_nodes - 1;
for (int i = 0; i < total_edges; i++) {
if (count_edges >= required_edges) break;
const Edge& e = all_edges[i];
if (e.type == -1) {
if (dsu.unite(e.u, e.v)) {
mst_val += e.w;
count_edges++;
}
} else {
int j = e.type;
if (S & (1 << j)) {
if (dsu.unite(e.u, e.v)) {
mst_val += e.w;
count_edges++;
}
}
}
}
if (count_edges == required_edges) {
ans = min(ans, mst_val + cost_s);
}
}
cout << ans << endl;
return 0;
}评测记录，居然获得了高达
T3（谐音替换，replace）
好像没有循环上但一直在无规则重复 and for the 三词，遂也跳过。
code：
#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, q;
cin >> n >> q;
unordered_map<string, vector<string>> replaceMap;
for (int i = 0; i < n; ++i) {
string s1, s2;
cin >> s1 >> s2;
replaceMap[s1].push_back(s2);
}
while (q--) {
string t1, t2;
cin >> t1 >> t2;
if (t1.size() != t2.size()) {
cout << 0 << '\n';
continue;
}
int len = t1.size();
int count = 0;
// Check for the entire string replacement
if (replaceMap.count(t1)) {
for (const string& s : replaceMap[t1]) {
if (s == t2) {
count++;
}
}
}
// Check for all possible substring replacements
for (int l = 1; l <= len; ++l) {
for (int i = 0; i <= len - l; ++i) {
int j = i + l;
string sub1 = t1.substr(i, l);
string sub2 = t2.substr(i, l);
if (sub1 == sub2) continue;
if (replaceMap.count(sub1)) {
for (const string& s : replaceMap[sub1]) {
if (s == sub2) {
// Construct the new string after replacement
string newStr = t1.substr(0, i) + sub2 + t1.substr(j);
if (newStr == t2) {
count++;
}
}
}
}
}
}
cout << count << '\n';
}
return 0;
}评测记录，好吧获得了
T4（员工招聘，employ）
code：
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int MOD = 998244353;
const int MAXN = 505;
int n, m;
char s[MAXN];
int c[MAXN];
int dp[MAXN][MAXN][MAXN];
int cnt1[MAXN][MAXN], cnt2[MAXN][MAXN];
int freq[MAXN][MAXN];
int main() {
cin >> n >> m;
cin >> (s + 1);
for (int i = 1; i <= n; i++) {
cin >> c[i];
}
for (int i = 0; i <= n; i++) {
for (int val = 0; val <= n; val++) {
freq[i][val] = 0;
}
}
for (int val = 0; val <= n; val++) {
int count_val = 0;
for (int i = 1; i <= n; i++) {
if (c[i] == val) {
count_val++;
}
}
freq[0][val] = count_val;
}
for (int i = 0; i < n; i++) {
for (int val = 0; val <= n; val++) {
freq[i+1][val] = freq[i][val];
}
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
cnt1[i][j] = 0;
cnt2[i][j] = 0;
for (int val = 0; val <= j; val++) {
cnt1[i][j] += freq[i][val];
}
cnt2[i][j] = (n - i) - cnt1[i][j];
}
}
memset(dp, 0, sizeof(dp));
dp[0][0][0] = 1;
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= i - j; k++) {
if (!dp[i][j][k]) continue;
int count1 = cnt1[i][j];
int count2 = cnt2[i][j];
dp[i+1][j+1][k] = (dp[i+1][j+1][k] + 1LL * dp[i][j][k] * count1 % MOD) % MOD;
if (count2) {
if (s[i+1] == '1') {
dp[i+1][j][k+1] = (dp[i+1][j][k+1] + 1LL * dp[i][j][k] * count2 % MOD) % MOD;
} else {
dp[i+1][j+1][k] = (dp[i+1][j+1][k] + 1LL * dp[i][j][k] * count2 % MOD) % MOD;
}
}
}
}
}
int ans = 0;
for (int j = 0; j <= n; j++) {
for (int k = m; k <= n; k++) {
ans = (ans + dp[n][j][k]) % MOD;
}
}
cout << ans << endl;
return 0;
}评测记录，获得了高达