测试数据生成代码（不是题解）
原题链接：82058.班长的职责 plus
2025-10-17 13:28:47
发布于：广东
2阅读
0回复
0点赞
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <climits>
#include <map>
#include <set>
using namespace std;
// 配置参数结构体，可手动修改
struct Config {
int n; // 学生人数
int m; // 组数
int x; // 初始班干部数量
int t; // 操作次数
bool has_empty_group; // 是否有空组
bool repeat_cadet; // 是否有重复班干部
bool large_range_op; // 是否有大范围操作
};
// 学生结构体
struct Student {
int score; // 个人分数
int group; // 所属组
int cadet_count; // 班干部职位数量
};
// 生成随机数（min到max之间，包含边界）
int rand_int(int min, int max) {
return min + rand() % (max - min + 1);
}
// 检查集合中是否包含元素
bool contains(const set<int>& s, int val) {
return s.find(val) != s.end();
}
// 检查映射中是否包含元素
bool contains(const map<int, int>& m, int key) {
return m.find(key) != m.end();
}
// 根据配置生成测试数据并计算答案
void generate_and_solve(const Config& cfg) {
srand(time(0)); // 随机种子
// 从配置读取参数
int n = cfg.n;
int m = cfg.m;
int x = cfg.x;
int t = cfg.t;
bool has_empty_group = cfg.has_empty_group;
bool repeat_cadet = cfg.repeat_cadet;
bool large_range_op = cfg.large_range_op;
// 参数合法性检查与调整
if (n < 1) n = 1;
if (m < 1) m = 1;
if (x < 0) x = 0;
if (x > n) x = n; // 班干部不能多于学生数
if (t < 1) t = 1;
if (has_empty_group && m < 2) has_empty_group = false; // 至少2组才能有空组
// 初始化学生
vector<Student> students(n + 1); // 1-based索引
for (int i = 1; i <= n; ++i) {
students[i].score = 0;
students[i].group = 0;
students[i].cadet_count = 0;
}
// 初始化分组
vector<vector<int> > groups(m + 1); // 每组成员列表
vector<int> group_size(m + 1, 0);
int remaining = n;
// 分配学生到组（处理空组情况）
for (int i = 1; i <= m; ++i) {
if (has_empty_group && i == m && remaining > 0) {
// 最后一组设为空组
continue;
}
if (remaining <= 0) break;
int sz = (i == m) ? remaining : rand_int(1, min(remaining, 5));
group_size[i] = sz;
remaining -= sz;
set<int> added;
for (int j = 0; j < sz; ++j) {
int id;
do {
id = rand_int(1, n);
} while (contains(added, id) || students[id].group != 0);
added.insert(id);
students[id].group = i;
groups[i].push_back(id);
}
}
// 初始化班干部（处理重复情况）
vector<int> cadets;
map<int, int> cadet_map;
for (int i = 0; i < x; ++i) {
int id;
if (repeat_cadet && i > 0 && rand() % 2 == 0) {
// 重复之前的班干部
id = cadets[rand_int(0, i - 1)];
} else {
do {
id = rand_int(1, n);
} while (!repeat_cadet && contains(cadet_map, id));
}
cadets.push_back(id);
cadet_map[id]++;
students[id].cadet_count++;
}
// 计算初始组总分（成员分 + 3*班干部数）
vector<int> group_total(m + 1, 0);
for (int i = 1; i <= m; ++i) {
int sum = 0;
for (size_t j = 0; j < groups[i].size(); ++j) {
int id = groups[i][j];
sum += students[id].score; // 初始分为0
sum += 3 * students[id].cadet_count;
}
group_total[i] = sum;
}
// 生成操作
vector<string> operations;
for (int i = 0; i < t; ++i) {
int op;
// 操作类型概率分布
if (large_range_op && i == 0) {
op = rand_int(1, 2); // 第一操作设为大范围加减分
} else {
op = rand_int(1, 5);
}
string op_str;
if (op == 1) {
// 1 x y k：加分
int x_op = rand_int(1, n);
int y_op = rand_int(x_op, n);
if (large_range_op) y_op = n; // 大范围操作
int k = rand_int(1, 10);
stringstream ss;
ss << "1 " << x_op << " " << y_op << " " << k;
op_str = ss.str();
// 执行操作
for (int id = x_op; id <= y_op; ++id) {
int g = students[id].group;
if (g == 0) continue; // 不在任何组
group_total[g] += k;
students[id].score += k;
}
} else if (op == 2) {
// 2 x y k：扣分
int x_op = rand_int(1, n);
int y_op = rand_int(x_op, n);
if (large_range_op) y_op = n; // 大范围操作
int k = rand_int(1, 5);
stringstream ss;
ss << "2 " << x_op << " " << y_op << " " << k;
op_str = ss.str();
// 执行操作
for (int id = x_op; id <= y_op; ++id) {
int g = students[id].group;
if (g == 0) continue;
int deduct = k + (students[id].cadet_count > 0 ? 2 : 0);
group_total[g] -= deduct;
students[id].score -= deduct;
}
} else if (op == 3) {
// 3 x y：换组
int x_op = rand_int(1, n);
int y_op = rand_int(1, m);
while (students[x_op].group == y_op) { // 确保换不同组
y_op = rand_int(1, m);
}
stringstream ss;
ss << "3 " << x_op << " " << y_op;
op_str = ss.str();
// 执行操作
int old_g = students[x_op].group;
if (old_g != 0) {
// 从旧组移除
group_total[old_g] -= students[x_op].score;
group_total[old_g] -= 3 * students[x_op].cadet_count;
}
// 添加到新组
students[x_op].group = y_op;
group_total[y_op] += students[x_op].score;
group_total[y_op] += 3 * students[x_op].cadet_count;
} else if (op == 4) {
// 4 y：调整班干部
int y_op = rand_int(1, n);
stringstream ss;
ss << "4 " << y_op;
op_str = ss.str();
// 找分数最低的有效班干部
int min_score = INT_MAX;
int min_id = -1;
for (int id = 1; id <= n; ++id) {
if (students[id].cadet_count > 0 && students[id].score < min_score) {
min_score = students[id].score;
min_id = id;
}
}
if (min_id != -1) {
// 移除一个职位
students[min_id].cadet_count--;
group_total[students[min_id].group] -= 3;
}
// 添加新职位
students[y_op].cadet_count++;
group_total[students[y_op].group] += 3;
} else if (op == 5) {
// 5：查询
op_str = "5";
}
operations.push_back(op_str);
}
// 输出测试数据
cout << n << " " << m << " " << x << " " << t << "\n";
for (int i = 1; i <= m; ++i) {
cout << group_size[i];
for (size_t j = 0; j < groups[i].size(); ++j) {
cout << " " << groups[i][j];
}
cout << "\n";
}
for (size_t i = 0; i < cadets.size(); ++i) {
cout << cadets[i];
if (i != cadets.size() - 1) cout << " ";
}
cout << "\n";
for (size_t i = 0; i < operations.size(); ++i) {
cout << operations[i] << "\n";
}
// 重新计算所有操作的结果（确保正确性）
vector<Student> reset_students(n + 1);
for (int i = 1; i <= n; ++i) {
reset_students[i].score = 0;
reset_students[i].group = 0;
reset_students[i].cadet_count = 0;
}
vector<vector<int> > reset_groups(m + 1);
vector<int> reset_group_size(m + 1, 0);
vector<int> reset_group_total(m + 1, 0);
map<int, int> reset_cadet_map;
// 重新初始化分组
remaining = n;
for (int i = 1; i <= m; ++i) {
reset_group_size[i] = group_size[i];
for (size_t j = 0; j < groups[i].size(); ++j) {
int id = groups[i][j];
reset_students[id].group = i;
reset_groups[i].push_back(id);
}
}
// 重新初始化班干部
for (size_t i = 0; i < cadets.size(); ++i) {
int id = cadets[i];
reset_cadet_map[id]++;
reset_students[id].cadet_count++;
}
// 重新计算初始组总分
for (int i = 1; i <= m; ++i) {
int sum = 0;
for (size_t j = 0; j < reset_groups[i].size(); ++j) {
int id = reset_groups[i][j];
sum += 3 * reset_students[id].cadet_count;
}
reset_group_total[i] = sum;
}
// 重新执行所有操作
vector<pair<int, int> > query_results;
for (size_t idx = 0; idx < operations.size(); ++idx) {
const string& op_str = operations[idx];
istringstream iss(op_str);
int op;
iss >> op;
if (op == 1) {
int x_op, y_op, k;
iss >> x_op >> y_op >> k;
for (int id = x_op; id <= y_op; ++id) {
int g = reset_students[id].group;
if (g == 0) continue;
reset_group_total[g] += k;
reset_students[id].score += k;
}
} else if (op == 2) {
int x_op, y_op, k;
iss >> x_op >> y_op >> k;
for (int id = x_op; id <= y_op; ++id) {
int g = reset_students[id].group;
if (g == 0) continue;
int deduct = k + (reset_students[id].cadet_count > 0 ? 2 : 0);
reset_group_total[g] -= deduct;
reset_students[id].score -= deduct;
}
} else if (op == 3) {
int x_op, y_op;
iss >> x_op >> y_op;
int old_g = reset_students[x_op].group;
if (old_g != 0) {
reset_group_total[old_g] -= reset_students[x_op].score;
reset_group_total[old_g] -= 3 * reset_students[x_op].cadet_count;
}
reset_students[x_op].group = y_op;
reset_group_total[y_op] += reset_students[x_op].score;
reset_group_total[y_op] += 3 * reset_students[x_op].cadet_count;
} else if (op == 4) {
int y_op;
iss >> y_op;
int min_score = INT_MAX;
int min_id = -1;
for (int id = 1; id <= n; ++id) {
if (reset_students[id].cadet_count > 0 && reset_students[id].score < min_score) {
min_score = reset_students[id].score;
min_id = id;
}
}
if (min_id != -1) {
reset_students[min_id].cadet_count--;
reset_group_total[reset_students[min_id].group] -= 3;
}
reset_students[y_op].cadet_count++;
reset_group_total[reset_students[y_op].group] += 3;
} else if (op == 5) {
int max_val = INT_MIN, max_idx = -1;
int min_val = INT_MAX, min_idx = -1;
for (int i = 1; i <= m; ++i) {
if (reset_group_total[i] > max_val) {
max_val = reset_group_total[i];
max_idx = i;
}
if (reset_group_total[i] < min_val) {
min_val = reset_group_total[i];
min_idx = i;
}
}
query_results.push_back(make_pair(max_idx, max_val));
query_results.push_back(make_pair(min_idx, min_val));
}
}
// 输出正确结果
// cout << "\n【正确输出】\n";
freopen("正确输出","w",stdout);
for (size_t i = 0; i < query_results.size(); ++i) {
cout << query_results[i].first << " " << query_results[i].second << "\n";
}
}
int main() {
// 配置参数 - 在这里修改参数
// Config cfg = {
// 5, // n: 学生人数
// 3, // m: 组数
// 2, // x: 初始班干部数量
// 8, // t: 操作次数
// false, // has_empty_group: 是否有空组
// true, // repeat_cadet: 是否有重复班干部
// true // large_range_op: 是否有大范围操作
// };
freopen("测试样例.in","w",stdout);
Config cfg;
cin>>cfg.n>>cfg.m>>cfg.x>>cfg.t>>cfg.has_empty_group>>cfg.repeat_cadet>>cfg.large_range_op;
// 生成并求解
generate_and_solve(cfg);
return 0;
}
``` 这个是来自作者的神秘的测试数据生成代码
这里空空如也
有帮助，赞一个