C/C++编程五级 题库
交叉和
有一个 h 行 w 列的网格。从上往下第 i 行、从左往右第 j 列的格子 (i, j) 中写有整数 Ai,j。对于所有格子 (i, j),请计算以下值:与格子 (i, j) 在同一行或同一列的所有格子中写的整数的总和。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:两个整数 h 和 w,表示行数和列数。
接下来有 h 行:每行 w 个整数,表示 aij。
输出格式
输出共 h 行,每行 w 个整数。相邻两个整数之间用单个空格隔开。
输入样例#1
3 3 1 1 1 2 2 2 3 3 3
输出样例#1
8 8 8 10 10 10 12 12 12
输入样例#2
2 10 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4
输出样例#2
44 47 48 46 48 42 41 42 47 43 61 59 62 59 63 67 60 64 63 61
数据范围:
2≤h、w≤2000,1≤ aij ≤ 99。
#include <stdio.h>
int a[2000][2000];
int row_sum[2000] = {0};
int col_sum[2000] = {0};
int main() {
int h, w;
scanf("%d %d", &h, &w);
// 读取网格并计算每行的和
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
scanf("%d", &a[i][j]);
row_sum[i] += a[i][j];
}
}
// 计算每列的和
for (int j = 0; j < w; j++) {
for (int i = 0; i < h; i++) {
col_sum[j] += a[i][j];
}
}
// 计算并输出结果
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
int res = row_sum[i] + col_sum[j] - a[i][j];
printf("%d", res);
if (j != w - 1) {
printf(" ");
}
}
printf("\n");
}
return 0;
}贪吃蛇
你设计一款贪吃蛇的游戏,游戏地图是一个 n×n 的方阵,从左上角(第 1 行第 1列)出发,移动规则如下:
(1)初始方向:向下移动;
(2)移动规则:若前方格子未被访问过,则沿当前方向前进;若前方格子已被访问过,则立即左转(不移动),并重新判断前进条件。
目标:计算到达第 i 行第 j 列所需的步数。
时间限制:1000ms,内存限制:256MB
输入格式
第1行: 一个正整数 N,表示地图大小。
第2行:两个正整数 i、j,表示询问走到当前第 i 行第 j 列。
输出格式
仅一行,表示走到当前位置所需步数。
输入样例#1
6 2 3
输出样例#1
32
输入样例#2
6 6 5
输出样例#2
10
数据范围:
1≤n≤100000,1≤i、j≤n。
#include <stdio.h>
#include <stdlib.h>
int main() {
int n, i, j;
scanf("%d", &n);
scanf("%d %d", &i, &j);
// 计算目标位置所在的圈数k
int d1 = i - 1;
int d2 = n - i;
int d3 = j - 1;
int d4 = n - j;
int min1 = (d1 < d2) ? d1 : d2;
int min2 = (d3 < d4) ? d3 : d4;
int k = (min1 < min2) ? (min1 + 1) : (min2 + 1);
// 计算前k-1圈的累计步数
long long sum_prev = 4LL * (k - 1) * (n - (k - 1));
// 计算当前圈的边长
int len = n - 2 * (k - 1);
long long ans;
// 根据目标位置在当前圈的四条边中的位置计算步数
if (i == k) {
// 上边界
ans = sum_prev + (j - k);
} else if (j == n - k + 1) {
// 右边界
ans = sum_prev + len + (i - k - 1);
} else if (i == n - k + 1) {
// 下边界
ans = sum_prev + 2 * len + (n - k + 1 - j - 1);
} else {
// 左边界
ans = sum_prev + 3 * len + (n - k + 1 - i - 1);
}
printf("%lld\n", ans);
return 0;
}乘积最大
给你两个数 N、K,从 N 个数中选出 K 个使得乘积最大。输出乘积在数学意义上对 109+7 取模的值。
时间限制:1000ms,内存限制:256MB
输入格式
第一行:两个整数 N、K;
第二行:N 个整数 a1、a2、……、an。
输出格式
一个整数表示答案。
输入样例#1
4 2 1 2 -3 -4
输出样例#1
12
输入样例#2
10 10 1000000000 100000000 10000000 1000000 100000 10000 1000 100 10 1
输出样例#2
999983200
数据范围:
1≤K≤N≤2×105,-109≤ai≤109。
#include <stdio.h>
#include <stdlib.h>
// 比较函数,用于qsort从小到大排序
int compare(const void *a, const void *b) {
long long num1 = *(long long *)a;
long long num2 = *(long long *)b;
if (num1 < num2) return -1;
if (num1 > num2) return 1;
return 0;
}
int main() {
int N, K;
scanf("%d %d", &N, &K);
long long *a = (long long *)malloc(N * sizeof(long long));
for (int i = 0; i < N; i++) {
scanf("%lld", &a[i]);
}
// 排序数组
qsort(a, N, sizeof(long long), compare);
const long long MOD = 1e9 + 7;
long long result = 1;
int left = 0;
int right = N - 1;
// 如果K是奇数,先取最大的元素(最右边)
if (K % 2 == 1) {
result = (result * (a[right] % MOD)) % MOD;
right--;
K--;
}
// 剩余K为偶数,每次取一对
while (K > 0) {
// 计算左边一对的乘积
long long left_product = (a[left] * a[left + 1]) % MOD;
// 计算右边一对的乘积
long long right_product = (a[right] * a[right - 1]) % MOD;
// 选择乘积较大的一对
if (left_product > right_product) {
result = (result * left_product) % MOD;
left += 2;
} else {
result = (result * right_product) % MOD;
right -= 2;
}
K -= 2;
}
// 处理结果为负数的情况(确保在0到MOD-1之间)
result = (result + MOD) % MOD;
printf("%lld\n", result);
free(a);
return 0;
}安全地图
在未来的星际探索中,人类发现了一个由 (2n)×(2n) 个星球组成的正方形星域。人类决定在这些星球上建立基地,但需要识别安全星球。规划规则如下:
(1)将整个星域均分为 4 个更小的正方形区域;
(2)左上角区域的所有星球都是安全的(用 "." 表示);
(3)其余三个区域继续递归划分,直到区域只有一个星球;
(4)未被标记为安全的星球存在危险(用 "*" 表示)。
请根据划分规则,输出整个星域的安全地图。
时间限制:1000ms,内存限制:256MB
输入格式
一个整数 n,表示星域大小。
输出格式
输出每个星球的安全性。
输入样例
3
输出样例
.......* ......** .....*.* ....**** ...*...* ..**..** .*.*.*.* ********
数据范围:
1≤n≤12。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char** map;
// 递归函数:划分区域并标记安全星球
// x, y:当前区域左上角坐标
// size:当前区域的大小(size = 2^k)
void divide(int x, int y, int size) {
if (size == 1) {
// 最小区域,若不是左上角子区域(即递归到最底层的非左上角区域),标记为'*'
map[x][y] = '*';
return;
}
int half = size / 2;
// 左上角区域标记为安全
for (int i = x; i < x + half; i++) {
for (int j = y; j < y + half; j++) {
map[i][j] = '.';
}
}
// 递归处理其余三个区域
divide(x, y + half, half); // 右上角
divide(x + half, y, half); // 左下角
divide(x + half, y + half, half); // 右下角
}
int main() {
int n;
scanf("%d", &n);
int size = 1 << n; // 计算2^n
// 初始化地图,分配内存
map = (char**)malloc(size * sizeof(char*));
for (int i = 0; i < size; i++) {
map[i] = (char*)malloc((size + 1) * sizeof(char)); // +1 用于存储字符串结束符
memset(map[i], 0, size + 1);
}
// 从整个区域开始划分
divide(0, 0, size);
// 输出地图
for (int i = 0; i < size; i++) {
printf("%s\n", map[i]);
free(map[i]); // 释放每行内存
}
free(map); // 释放地图指针数组
return 0;
}小白兔拔萝卜
小白兔拔萝卜,但是它的力量有限,太大的萝卜它拔不动。于是它叫来了一群小伙伴……
本题就请你根据小白兔们的力量和拔出这个萝卜需要的力量,告诉小白兔,它最少需要哪些伙伴能拔出这只大萝卜。
时间限制:7000,内存限制:65536
输入描述
输入在第一行里给出两个不超过 1000 的正整数 n 和 T,分别是小白兔的数量和拔出这个萝卜需要的力量。
随后一行给出 n 个不超过 100 的正整数,其中第 i 个数对应编号为 i 的小白兔的力量(i=1, … , n)。
输出描述
如果兔子们有可能拔成功,则首先在第一行输出最少需要多少只兔子才能拔出这只萝卜,然后第二行从小到大输出参与拔萝卜的兔子们的编号。编号间以 1 个空格分隔,行首尾不得有多余空格。
如果所有兔子合力都不能拔出萝卜,则首先在第一行输出 0,随后在第二行中输出:Suan4 le ba, hai2 cha4 X. 其中 X 是小白兔们缺少的力量值。
注意:力量等于 T 是可以拔出萝卜的。 解可能不是唯一的,你只要随便输出一组就可以。
样例输入1
10 100 3 25 4 91 13 81 64 38 49 51
样例输出1
2 2 4
样例输入2
5 50 3 2 8 5 10
样例输出2
0 Suan4 le ba, hai2 cha4 22.
//答案来源于AI
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const int INF = 10000;
int main() {
int n, T;
cin >> n >> T;
vector<int> powers(n);
long long total = 0;
for (int i = 0; i < n; i++) {
cin >> powers[i];
total += powers[i];
}
// 处理总力量不足的情况
if (total < T) {
cout << "0" << endl;
cout << "Suan4 le ba, hai2 cha4 " << T - total << "." << endl;
return 0;
}
// 动态规划数组,dp[j]表示达到力量j所需的最少兔子数
vector<int> dp(T + 1, INF);
// 记录状态转移路径
vector<int> prevState(T + 1, -1);
vector<int> lastId(T + 1, -1);
// 初始状态:0力量需要0只兔子
dp[0] = 0;
// 动态规划过程
for (int i = 0; i < n; i++) {
int w = powers[i];
// 倒序遍历,避免重复计算
for (int j = T; j >= 0; j--) {
if (dp[j] == INF) continue; // 当前状态不可达
int next = j + w;
if (next > T) next = T; // 力量超过T的都视为达到T
// 更新新状态的最小兔子数
if (dp[next] > dp[j] + 1) {
dp[next] = dp[j] + 1;
prevState[next] = j; // 记录前一个状态
lastId[next] = i; // 记录最后加入的兔子索引
}
}
}
// 回溯求解方案
vector<int> selected;
int cur = T;
while (cur > 0) {
selected.push_back(lastId[cur] + 1); // 转换为1-indexed编号
cur = prevState[cur];
}
sort(selected.begin(), selected.end());
// 输出结果
cout << dp[T] << endl;
for (int i = 0; i < selected.size(); i++) {
if (i > 0) cout << " ";
cout << selected[i];
}
cout << endl;
return 0;
}化学反应式
“化学反应式”是用元素符号表示化学反应的一种等式,等式左边给出参与反应的元素,右边给出反应的结果。例如 CH4+2O2= CO2+ 2H2O 的意思是,参与反应的元素是甲烷和氧气,即 CH4和 O2,反应结果产生二氧化碳和水,即 CO2和 H2O。
现给定一些反应元素和结果,请你编写程序推出我们怎样才能得到这些结果。注意每种反应元素只能被用一次。为简单起见,我们将等式右边的所有元素都当成是一个结果。
时间限制:6000,内存限制:65536
输入
每个输入包含一个测试用例。每个测试用例先给出一个整数 N(2 ≤ N ≤ 20),随后给出 N 个不同的反应元素的编号。
第二行给出一个整数 M(1 ≤ M ≤ 10),随后给出 M 个不同的结果编号。所有编号都是一个 2 位数字。
随后给出正整数 K(≤ 50),接下来 K 行,每行给出一个化学反应式,格式为: reactant_1 + reactant_2 + ... + reactant_n -> product 其中所有的反应元素(reactant)编号都是不同的,并且按升序排列。
注意:题目保证以下规则
(1)一套反应元素不会产生多个不同的结果,即诸如 01 + 02 -> 03 且 01 + 02 -> 04 这种情况保证不会出现;
(2)一个反应元素不会同时还是等式右边的结果元素,除非等式左边只有这一个元素。例如 01 -> 01 总是成立的(无论这个等式是否给出),但 01 + 02 -> 01 是不可能的;
(3)对于列出的等式中的每个结果,得到它的反应方法不会超过 5 种。
输出
输出用给定的反应元素产生所有给定结果的化学反应式。注意每种反应元素只能被用一次。 每个反应式占一行,格式与输入格式相同。顺序必须与输入中的结果编号顺序一致。
对顺序产生的每个结果,如果反应方法不唯一,输出反应元素的最小序列 —— 序列 { a1, … , am} 比 { b1, … , bn} 小的意思是:存在 1 ≤ i ≤ min(m, n) 使得 aj= bj对所有 j < i 成立,且有 ai< bi。 题目保证至少存在一个解。
样例输入
8 09 05 03 04 02 01 16 10 3 08 03 04 6 03 + 09 -> 08 02 + 08 -> 04 02 + 04 -> 03 01 + 05 -> 03 01 + 09 + 16 -> 03 02 + 03 + 05 -> 08
样例输出
02 + 03 + 05 -> 08 01 + 09 + 16 -> 03 04 -> 04
//答案来源于AI
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <sstream>
#include <cctype>
using namespace std;
// 去除字符串前后空格
void trim(string &str) {
if (str.empty()) return;
size_t first = str.find_first_not_of(' ');
size_t last = str.find_last_not_of(' ');
if (first == string::npos) {
str = "";
return;
}
str = str.substr(first, (last - first + 1));
}
// 反应式结构体
struct Reaction {
vector<string> reactants; // 反应物列表
string prod; // 产物
string raw; // 原始字符串
Reaction(const string& s) : raw(s) {
size_t pos = s.find(" -> ");
if (pos == string::npos) {
return;
}
string leftStr = s.substr(0, pos);
string rightStr = s.substr(pos + 4);
trim(rightStr);
prod = rightStr;
// 解析反应物
stringstream ss(leftStr);
string token;
while (getline(ss, token, '+')) {
trim(token);
if (!token.empty()) {
reactants.push_back(token);
}
}
}
};
int main() {
int n;
cin >> n;
vector<string> initVec;
set<string> availableSet;
for (int i = 0; i < n; i++) {
string x;
cin >> x;
initVec.push_back(x);
availableSet.insert(x);
}
int m;
cin >> m;
vector<string> targets;
set<string> targetSet;
for (int i = 0; i < m; i++) {
string x;
cin >> x;
targets.push_back(x);
targetSet.insert(x);
}
int k;
cin >> k;
cin.ignore(); // 忽略换行符
map<string, vector<Reaction>> reactionsMap;
for (int i = 0; i < k; i++) {
string s;
getline(cin, s);
Reaction reac(s);
if (targetSet.count(reac.prod)) {
reactionsMap[reac.prod].push_back(reac);
}
}
for (string target : targets) {
if (availableSet.find(target) != availableSet.end()) {
cout << target << " -> " << target << endl;
availableSet.erase(target);
} else {
vector<Reaction>& candidates = reactionsMap[target];
vector<Reaction> validReactions;
for (Reaction& reac : candidates) {
bool valid = true;
for (string r : reac.reactants) {
if (availableSet.find(r) == availableSet.end()) {
valid = false;
break;
}
}
if (valid) {
validReactions.push_back(reac);
}
}
Reaction best = validReactions[0];
for (int i = 1; i < validReactions.size(); i++) {
if (validReactions[i].reactants < best.reactants) {
best = validReactions[i];
}
}
cout << best.raw << endl;
for (string r : best.reactants) {
availableSet.erase(r);
}
}
}
return 0;
}赛场安排
比赛使用 OMS 监考系统,需要将参赛队员安排到系统中的虚拟赛场里,并为每个赛场分配一位监考老师。每位监考老师需要联系自己赛场内队员对应的教练们,以便发放比赛账号。为了尽可能减少教练和监考的沟通负担,我们要求赛场的安排满足以下条件:
- 每位监考老师负责的赛场里,队员人数不得超过赛场规定容量 C;
- 每位教练需要联系的监考人数尽可能少 —— 这里假设每所参赛学校只有一位负责联系的教练,且每个赛场的监考老师都不相同,为此我们设计了多轮次排座算法,按照尚未安排赛场的队员人数从大到小的顺序,每一轮对当前未安排的人数最多的学校进行处理。记当前待处理的学校未安排人数为 n;
- 如果 n ≥ C,则将其中 C 人安排到当前为空的编号最小的赛场,剩下的人继续按人数规模排队,等待下一轮处理;
- 如果 n < C,则寻找剩余空位数大于等于 n 的编号最小的赛场,将队员安排进去;
- 如果 n < C,且找不到任何非空的、剩余空位数大于等于 n 的赛场了,则新开一个赛场,将队员安排进去。
由于近年来参赛人数快速增长,2023年超过了 410 所学校 1.6 万人,所以我们必须写个程序来处理赛场安排问题。
时间限制:6000,内存限制:65536
输入
输入第一行给出两个正整数 N 和 C,分别为参赛学校数量和每个赛场的规定容量,其中 0 < N ≤ 5000,10 ≤ C ≤ 50。
随后 N 行,每行给出一个学校的缩写(为长度不超过 6 的非空小写英文字母串)和该校参赛人数(不超过 500 的正整数),其间以空格分隔。题目保证每所学校只有一条记录。
输出
按照输入的顺序,对每一所参赛高校,在一行中输出学校缩写和该校需要联系的监考人数,其间以 1 空格分隔。 最后在一行中输出系统中应该开设多少个赛场。
样例输入
10 30 zju 30 hdu 93 pku 39 hbu 42 sjtu 21 abdu 10 xjtu 36 nnu 15 hnu 168 hsnu 20
样例输出
zju 1 hdu 4 pku 2 hbu 2 sjtu 1 abdu 1 xjtu 2 nnu 1 hnu 6 hsnu 1 16
//答案来源于AI
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <cctype>
#include <string>
using namespace std;
struct School {
string name;
int total;
int remaining;
int supervisors;
School(string n, int t) : name(n), total(t), remaining(t), supervisors(0) {}
};
int main() {
int N, C;
cin >> N >> C;
vector<School> schools;
for (int i = 0; i < N; i++) {
string name;
int num;
cin >> name >> num;
schools.push_back(School(name, num));
}
auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
if (a.first != b.first)
return a.first < b.first;
else
return a.second > b.second;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
for (int i = 0; i < schools.size(); i++) {
pq.push({schools[i].remaining, i});
}
int totalRooms = 0;
vector<set<int>> buckets(51);
while (!pq.empty()) {
int remaining = pq.top().first;
int idx = pq.top().second;
pq.pop();
if (remaining > schools[idx].remaining) {
continue;
}
if (remaining >= C) {
totalRooms++;
schools[idx].supervisors++;
schools[idx].remaining -= C;
if (schools[idx].remaining > 0) {
pq.push({schools[idx].remaining, idx});
}
} else {
bool found = false;
for (int r = remaining; r <= 50; r++) {
if (!buckets[r].empty()) {
found = true;
int room_id = *buckets[r].begin();
buckets[r].erase(room_id);
int new_r = r - remaining;
if (new_r > 0) {
buckets[new_r].insert(room_id);
}
schools[idx].supervisors++;
break;
}
}
if (!found) {
totalRooms++;
schools[idx].supervisors++;
int new_r = C - remaining;
if (new_r > 0) {
buckets[new_r].insert(totalRooms - 1);
}
}
}
}
for (int i = 0; i < N; i++) {
cout << schools[i].name << " " << schools[i].supervisors << endl;
}
cout << totalRooms << endl;
return 0;
}买还是不买
小红想用自己喜欢的彩色珠子做一条珠串,于是去一家小店买珠子。店里有很多条彩色的珠串,但店主只卖整串,不拆散零售珠子。于是小红为了得到自己喜欢颜色的珠子,就得买很多条现成的珠串,回家拆了自己拼。
由于店里有上百条珠串,小红只好求助于你,请你写个程序,帮她看看是否有可能买到所有她喜欢颜色的珠子,并且使得多余的珠子尽可能少。
为简单起见,我们用数字 0 到 9、以及英文的 26 个字母的大小写来表示珠子的颜色(即珠子最多有 62 种颜色)。
在样例 1 中,买第 2 条和最后两条珠串是最划算的,因为这样只有 3 颗珠子是多余的。
在样例 2 中,把全部三条珠串都买下也不行,因为还少三颗 R 珠。
时间限制:9000,内存限制:65536
输入
输入第一行给出小红想要的珠串。下一行给出正整数 N(≤ 100),随后 N 行,每行给出店里的一条珠串。所有珠串中的珠子不超过 1000 颗。
输出
如果能凑出小红想要的珠串,则在一行中输出 Yes、空格、最少的多余珠子的个数;否则输出 No、空格、凑不出来的珠子的个数。
样例输入1
RYg5 8 gY5Ybf 8R5 12346789 gRg8h 5Y37 pRgYgbR52 8Y 8g
样例输出1
Yes 3
样例输入2
YrRR8RRrY 3 ppRGrrYB225 8ppGrrB25 Zd6KrY
样例输出2
No 3
//答案来源于AI
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>
using namespace std;
const int MAX_COLOR = 62;
int getIndex(char c) {
if (c >= '0' && c <= '9')
return c - '0';
else if (c >= 'A' && c <= 'Z')
return 10 + (c - 'A');
else if (c >= 'a' && c <= 'z')
return 36 + (c - 'a');
return -1;
}
struct Bead {
int len;
vector<int> cnt;
string s;
Bead(string str) : s(str), len(str.size()), cnt(MAX_COLOR, 0) {
for (char c : str) {
int idx = getIndex(c);
if (idx != -1) {
cnt[idx]++;
}
}
}
};
vector<Bead> beads;
vector<int> target(MAX_COLOR, 0);
vector<int> total(MAX_COLOR, 0);
vector<vector<int>> suffix;
int best = INT_MAX;
int total_target = 0;
int N;
void dfs(int idx, vector<int> need, int cur_len) {
if (cur_len >= best) {
return;
}
int sum_need = 0;
bool all_zero = true;
for (int c = 0; c < MAX_COLOR; c++) {
if (need[c] > 0) {
all_zero = false;
sum_need += need[c];
}
}
if (all_zero) {
best = cur_len;
return;
}
if (idx >= N) {
return;
}
for (int c = 0; c < MAX_COLOR; c++) {
if (need[c] > suffix[idx][c]) {
return;
}
}
if (cur_len + sum_need >= best) {
return;
}
dfs(idx + 1, need, cur_len);
bool useful = false;
for (int c = 0; c < MAX_COLOR; c++) {
if (beads[idx].cnt[c] > 0 && need[c] > 0) {
useful = true;
break;
}
}
if (useful) {
vector<int> new_need = need;
for (int c = 0; c < MAX_COLOR; c++) {
if (new_need[c] > 0) {
new_need[c] = max(0, new_need[c] - beads[idx].cnt[c]);
}
}
dfs(idx + 1, new_need, cur_len + beads[idx].len);
}
}
int main() {
string target_str;
getline(cin, target_str);
total_target = target_str.size();
for (char c : target_str) {
int idx = getIndex(c);
if (idx != -1) {
target[idx]++;
}
}
cin >> N;
cin.ignore();
beads.reserve(N);
for (int i = 0; i < N; i++) {
string s;
getline(cin, s);
beads.push_back(Bead(s));
}
for (int i = 0; i < MAX_COLOR; i++) {
total[i] = 0;
}
for (int i = 0; i < N; i++) {
for (int c = 0; c < MAX_COLOR; c++) {
total[c] += beads[i].cnt[c];
}
}
int shortage = 0;
bool overall_meet = true;
for (int c = 0; c < MAX_COLOR; c++) {
if (target[c] > total[c]) {
overall_meet = false;
shortage += (target[c] - total[c]);
}
}
if (!overall_meet) {
cout << "No " << shortage << endl;
return 0;
}
sort(beads.begin(), beads.end(), [](const Bead& a, const Bead& b) {
return a.len < b.len;
});
suffix.resize(N, vector<int>(MAX_COLOR, 0));
for (int c = 0; c < MAX_COLOR; c++) {
suffix[N - 1][c] = beads[N - 1].cnt[c];
}
for (int i = N - 2; i >= 0; i--) {
for (int c = 0; c < MAX_COLOR; c++) {
suffix[i][c] = beads[i].cnt[c] + suffix[i + 1][c];
}
}
best = INT_MAX;
dfs(0, target, 0);
cout << "Yes " << best - total_target << endl;
return 0;
}组合
题目描述
你收集了 n 张卡片,按照收集的时间顺序编号 1 到 n 并依次排列,每张卡片上标有一个数值。现在突发奇想,想知道在这些卡片中,若每次挑选两张卡片,会有多少对不同的组合满足两张卡片的数值和恰好为 0,请你计算出符合条件的卡片组合的数量。
输入格式
· 第一行:单个整数表示 n
· 第二行:n 个整数表示 a1,a2,a3,…,an
输出格式
单个整数:表示有多少对卡片数值和为 0。
输入样例
4 2 -2 2 0
输出样例
2
说明提示
· 30%的数据,1≤n≤1000
· 60% 的数据,1≤n≤20000
· 100% 的数据,1≤n≤300000
· -1,000,000,000≤ai≤1,000,000,000
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> cards(n);
unordered_map<int, int> freq;
for (int i = 0; i < n; ++i) {
cin >> cards[i];
freq[cards[i]]++;
}
long long count = 0;
for (int num : cards) {
int complement = -num;
if (freq.find(complement) != freq.end()) {
if (complement == num) {
count += freq[complement] - 1;
} else {
count += freq[complement];
}
}
}
cout << count / 2 << endl;
return 0;
}选数
题目描述
给定一个正整数 n,从数字 1 到 n 中选择若干个数字(所选集合不能为空),且任意两个被选中的数字在数轴上不能相邻。求符合条件的方案数,结果对 1000000007 取模。
输入格式
第一行:单个整数 n。
输出格式
输出一个整数,表示方案数模 1000000007 的结果。
输入样例
3
输出样例
4
说明提示
· 对于 30% 的数据,n≤20;
· 对于 60% 的数据,n≤10,000;
· 对于 100% 的数据,1≤n≤100,000。
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;
int main() {
int n;
cin >> n;
if (n == 1) {
cout << 1 << endl;
return 0;
}
vector<long long> dp(n + 1);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; ++i) {
dp[i] = (dp[i-1] + dp[i-2] + 1) % MOD;
}
cout << dp[n] << endl;
return 0;
}图书管理
题目描述
图书馆的书籍分类系统使用二进制标签管理,0 代表儿童读物,1 代表青少年书籍。管理员发现当前的书架排列中不允许出现青少年书籍之后连接儿童读物的情况(即 10 子串)。管理员每次可以交换任意两本书的位置。请计算让书架符合规定所需的最少操作次数。
输入格式
由 0 和 1 组成的字符串,表示当前书架排列。
输出格式
一行一个非负整数,即达到目标所需的最少操作次数。
输入样例#1
1100
输出样例#1
2
输入样例#2
00
输出样例#2
0
输入样例#3
10110100
输出样例#3
3
说明提示
对于全部的输入数据,保证 2≤字符串长度≤200000 ,同时 ci必为1 或 0 中的一个。
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
int total0 = 0;
// 统计整个字符串中0的数量
for (char c : s) {
if (c == '0') total0++;
}
int ans = 0;
// 统计前total0个字符中1的数量
for (int i = 0; i < total0; i++) {
if (s[i] == '1') ans++;
}
cout << ans << endl;
return 0;
}街道的中心
题目描述
城市商业街主干道是一条笔直的道路,商业街里有 n 家店铺,现给定 n 个店铺的位置,请在这条道路上找到一个中心点,使得所有店铺到这个中心点的距离之和最小,并输出这个最小值。
输入格式
第一行:单个正整数 n。
第二行:n 个整数表示一个店铺的位置。
输出格式
单个整数:表示商铺到中心点距离之和的最小值。
输入样例
4
-2 0 2 0
输出样例
4
说明提示
数据范围:
· -5000≤xi≤5000
· 对于 30% 的数据,1≤n≤20
· 对于 60% 的数据,1≤n≤2000
· 对于 100% 的数据,1≤n≤100000
样例解释:
最优中心设置在坐标 0 处,总距离为:
∣-2-0∣+∣0-0∣+∣2-0∣+∣0-0∣=2+0+2+0=4
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
int n;
cin >> n;
// 读取店铺位置
int* positions = new int[n];
for (int i = 0; i < n; i++) {
cin >> positions[i];
}
// 排序位置数组
sort(positions, positions + n);
// 计算中位数
int mid = positions[n / 2];
// 计算距离之和
long long total = 0;
for (int i = 0; i < n; i++) {
total += abs(positions[i] - mid);
}
cout << total << endl;
delete[] positions;
return 0;
}结绳
给定一段一段的绳子,你需要把它们串成一条绳。每次串连的时候,是把两段绳子对折,再如下图所示套接在一起。这样得到的绳子又被当成是另一段绳子,可以再次对折去跟另一段绳子串连。每次串连后,原来两段绳子的长度就会减半。

给定 n 段绳子的长度,你需要找出它们能串成的绳子的最大长度。
时间限制:1000
内存限制:65536
输入
每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 n (2 ≤ n ≤ 104);第 2 行给出 n 个正整数,即原始绳段的长度,数字间以空格分隔。所有整数都不超过104。
输出
在一行中输出能够串成的绳子的最大长度。结果向下取整,即取为不超过最大长度的最近整数。
样例输入
8 10 15 12 3 4 13 1 15
样例输出
14
#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 用于greater
using namespace std;
int main() {
int n;
cin >> n;
priority_queue<double, vector<double>, greater<double>> heap;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
heap.push(x);
}
while (heap.size() > 1) {
double x = heap.top();
heap.pop();
double y = heap.top();
heap.pop();
double merged = (x + y) / 2.0;
heap.push(merged);
}
double result = heap.top();
cout << static_cast<int>(result) << endl;
return 0;
}从A到B
我们来做一个数字游戏,通过一系列操作把一个数字 A 变成另一个数字 B。设当前数字是 X,规定每次操作可以从以下 3 种里面选一种进行:
- X = X + 1
- X = X - 1
- X = X × N
你的任务就是求出从 A 变成 B 至少需要多少步。
时间限制:1000
内存限制:65536
输入
每组输入包含多个测试用例。先给出一个整数 K(≤ 10),为测试用例的个数。随后 K 行,每行给出一个测试用例的三个整数:A、B、N,其中 -105 ≤ A, B ≤ 105,1 < N < 10。同行数字间以空格分隔。
输出
对每个测试用例,在一行中输出从 A 变成 B 至少需要多少步。
样例输入
3 3 11 2 -5 -12 3 -2 1000 7
样例输出
3 2 13
提示
样例解释: 第 1 组:(3 × 2 × 2)-1=11 第 2 组:(-5+1) × 3 = -12 第 3 组:(((-2+1+1+1+1+1)×7-1)×7+1+1+1)×7-1 = 1000
#include <iostream>
#include <queue>
#include <unordered_map>
using namespace std;
int solve(long long A, long long B, int N) {
if (A == B) return 0;
queue<pair<long long, int>> q;
unordered_map<long long, int> visited;
q.push({A, 0});
visited[A] = 0;
while (!q.empty()) {
auto [current, steps] = q.front();
q.pop();
if (current == B) {
return steps;
}
vector<long long> next_values = {current + 1, current - 1, current * N};
for (long long next_val : next_values) {
if (next_val == B) {
return steps + 1;
}
if (!visited.count(next_val)) {
visited[next_val] = steps + 1;
q.push({next_val, steps + 1});
}
}
}
return -1; // 理论上不会执行到这里
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int K;
cin >> K;
while (K--) {
long long A, B;
int N;
cin >> A >> B >> N;
cout << solve(A, B, N) << '\n';
}
return 0;
}乘积的最大和
给定两组整数 A 和 B,你可以从 A 中任选一个整数,与 B 中任选的一个整数相乘。注意每个整数至多只能被选中 1 次。将这些乘积加起来,最大值能达到多少?
时间限制:10000
内存限制:65536
输入
输入第一行给出正整数 NA,为 A 组中整数的个数,随后一行给出 A 中的 NA 个整数;然后给出正整数 NB,为 B 组中整数的个数,随后一行给出 B 中的 NB 个整数。数据范围为 1 ≤ NA, NB ≤ 105,最大答案不超过 230。
输出
在一行中输出题面要求的乘积和的最大值。
样例输入
4 1 2 4 -1 4 7 6 -2 -3
样例输出
43
提示
样例解释: 43 = (-1)×(-3)+4×7+2×6
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int na, nb;
vector<int> A_pos, A_neg, B_pos, B_neg;
cin >> na;
for (int i = 0; i < na; ++i) {
int x;
cin >> x;
if (x > 0) {
A_pos.push_back(x);
} else if (x < 0) {
A_neg.push_back(x);
}
}
cin >> nb;
for (int i = 0; i < nb; ++i) {
int x;
cin >> x;
if (x > 0) {
B_pos.push_back(x);
} else if (x < 0) {
B_neg.push_back(x);
}
}
sort(A_pos.rbegin(), A_pos.rend());
sort(A_neg.begin(), A_neg.end());
sort(B_pos.rbegin(), B_pos.rend());
sort(B_neg.begin(), B_neg.end());
int i = 0, j = 0, k = 0, l = 0;
long long sum = 0;
while (true) {
long long pos_prod = 0, neg_prod = 0;
bool pos_valid = false, neg_valid = false;
if (i < A_pos.size() && j < B_pos.size()) {
pos_prod = (long long)A_pos[i] * B_pos[j];
pos_valid = true;
}
if (k < A_neg.size() && l < B_neg.size()) {
neg_prod = (long long)A_neg[k] * B_neg[l];
neg_valid = true;
}
if (!pos_valid && !neg_valid) {
break;
}
if (pos_valid && neg_valid) {
if (pos_prod >= neg_prod) {
sum += pos_prod;
i++;
j++;
} else {
sum += neg_prod;
k++;
l++;
}
} else if (pos_valid) {
sum += pos_prod;
i++;
j++;
} else {
sum += neg_prod;
k++;
l++;
}
}
cout << sum << endl;
return 0;
}收费站在哪里
在一条高速公路上,如果已知 n 座收费站的位置 x1,x2,… ,xn(不妨假设 0=x1 ≤ x2 ≤ … ≤ xn),就很容易算出一共有 n(n-1)/2 个距离的值。而比较困难的问题是,在收集了一大堆过路费发票后,我们筛选出了 n(n-1)/2 个距离的值,现在想知道收费站都分布在哪里?
当然对应一组距离值,可能有多组解,你只要输出任何一个即可。
时间限制:1000
内存限制:65536
输入
输入第一行给出正整数 m(< 50),即距离值的数量。 随后一行给出 m 个距离,均为 int 范围内的正整数。
输出
按坐标值升序列出所有收费站的位置,其中 x1=0。同行数字间以 1 个空格分隔,行首尾不得有多余空格。 注:题目保证所有坐标为 int 范围内的非负整数。
样例输入
10 3 4 6 8 1 3 5 2 4 2
样例输出
0 2 4 5 8
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
vector<int> x;
map<int, int> freq;
int n;
void backtrack() {
if (x.size() == n) {
for (int i = 0; i < n; ++i) {
if (i != 0) cout << " ";
cout << x[i];
}
exit(0);
}
int k = x.size();
map<int, int> current_freq = freq;
for (auto it = current_freq.begin(); it != current_freq.end(); ++it) {
int candidate = it->first;
if (candidate <= x.back()) continue;
map<int, int> temp_freq = current_freq;
bool valid = true;
for (int i = 0; i < k; ++i) {
int d = candidate - x[i];
if (temp_freq[d] <= 0) {
valid = false;
break;
}
temp_freq[d]--;
if (temp_freq[d] == 0) {
temp_freq.erase(d);
}
}
if (valid) {
x.push_back(candidate);
freq = temp_freq;
backtrack();
x.pop_back();
freq = current_freq;
}
}
}
int main() {
int m;
cin >> m;
vector<int> distances(m);
for (int i = 0; i < m; ++i) {
cin >> distances[i];
}
n = (int)((sqrt(8 * m + 1) + 1) / 2);
sort(distances.begin(), distances.end());
for (int d : distances) {
freq[d]++;
}
x.push_back(0);
backtrack();
return 0;
}游船


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); // 加速cin,适配1e5数据
int N, T;
cin >> N >> T;
vector<int> a(N);
for (int i = 0; i < N; ++i)
{
cin >> a[i];
}
sort(a.begin(), a.end());
int l = 0, r = N - 1;
int ans = 0;
while (l <= r)
{
if (a[l] + a[r] <= T)
{
l++;
}
r--;
ans++;
}
cout << ans << endl;
return 0;
}实数验证




#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main()
{
string s;
getline(cin, s);
bool bad1 = false, bad2 = false, bad3 = false, bad4 = false;
// 规则4:只能是 0-9 . + -
for (char ch : s)
{
if (!(isdigit(ch) || ch == '.' || ch == '+' || ch == '-'))
{
bad4 = true;
break;
}
}
// 规则1:+ - 只能在第一个,最多一个
int sign_cnt = 0;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '+' || s[i] == '-')
{
sign_cnt++;
if (i != 0)
{
bad1 = true;
}
}
}
if (sign_cnt > 1) bad1 = true;
// 规则2:小数点最多一个
int dot_cnt = 0;
for (char ch : s)
{
if (ch == '.') dot_cnt++;
}
if (dot_cnt > 1) bad2 = true;
// 规则3:整数、小数部分不能同时为空,至少有一位数字
bool has_digit = false;
for (char ch : s)
{
if (isdigit(ch))
{
has_digit = true;
break;
}
}
if (!has_digit)
{
bad3 = true;
}
else
{
// 有小数点的时候,不能两边都没有数字
if (dot_cnt == 1)
{
int pos = s.find('.');
bool left_has = false, right_has = false;
for (int i = 0; i < pos; i++)
{
if (isdigit(s[i])) left_has = true;
}
for (int i = pos + 1; i < s.size(); i++)
{
if (isdigit(s[i])) right_has = true;
}
if (!left_has && !right_has)
{
bad3 = true;
}
}
}
vector<int> err;
if (bad1) err.push_back(1);
if (bad2) err.push_back(2);
if (bad3) err.push_back(3);
if (bad4) err.push_back(4);
if (err.empty())
{
cout << "Valid\n";
}
else
{
cout << "Invalid\n";
for (int i = 0; i < err.size(); i++)
{
if (i > 0) cout << ' ';
cout << err[i];
}
cout << '\n';
}
return 0;
}