C/C++编程六级 题库
古董
拍卖师准备了 N 件古董进行拍卖。这些古董有以下重要特性:
陈列规则:所有古董按 1、……、N 编号陈列在一条长廊中,每天拍卖师只能从长廊任一端取出一件古董拍卖。
升值效应:古董拍卖顺序直接影响成交价。若第 i 件古董在第 a天拍卖,成交价为 Vi×a(Vi 为初始估价)。
价值分布:第 i 件古董的初始估价 Vi 取决于其陈列位置——从入口端开始,第 i 个展柜内的古董估价为Vi。
拍卖师需要制定最优拍卖顺序,最大化总成交额。请帮助他计算出古董全部售出后的最大收益。
时间限制:1000ms内存限制:256MB
输入格式
第一行:古董数量 N;
接下来 n 行:古董初始估价序列 V1~VN;
输出格式
一行整数,表示最大总收益。
输入样例
5 1 3 1 5 2
输出样例
43
数据范围:
1≤N≤2000,1≤Vi≤1000。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 2005;
int dp[MAXN][MAXN];
int V[MAXN];
int main() {
int N;
cin >> N;
for (int i = 1; i <= N; ++i) {
cin >> V[i];
}
// 初始化长度为1的子序列(只剩一件古董时)
for (int i = 1; i <= N; ++i) {
dp[i][i] = V[i] * N;
}
// 处理长度为l的子序列(l从2到N)
for (int l = 2; l <= N; ++l) {
for (int i = 1; i + l - 1 <= N; ++i) {
int j = i + l - 1; // 子序列的右端点
int k = N - l + 1; // 当前拍卖的天数
// 取左端或右端,选择收益更大的方案
dp[i][j] = max(V[i] * k + dp[i + 1][j], V[j] * k + dp[i][j - 1]);
}
}
cout << dp[1][N] << endl;
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
}
// dp[i][j] 表示从第i件到第j件古董能获得的最大收益
vector<vector<long long>> dp(n, vector<long long>(n, 0));
// 初始化:单件古董在第n天拍卖(最后一天)
for (int i = 0; i < n; i++) {
dp[i][i] = (long long)v[i] * n;
}
// 区间DP:从小区间到大区间
for (int len = 2; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
int day = n - len + 1; // 当前拍卖的天数
// 选择左端古董:v[i] * day + dp[i+1][j]
// 选择右端古董:v[j] * day + dp[i][j-1]
dp[i][j] = max((long long)v[i] * day + dp[i+1][j],
(long long)v[j] * day + dp[i][j-1]);
}
}
cout << dp[0][n-1] << endl;
return 0;
}括号
给定一个整数 n。生成所有长度为 n 的合法括号序列,并按字典序升序输出。合法括号序列定义:
(1)空字符串是合法的;
(2)若字符串 s 合法,则 (+s+) 合法;
(3)若字符串 s 和 t 合法,则 s+t 合法。
时间限制:1000ms内存限制:256MB
输入格式
输入一个整数n。
输出格式
每行输出一个合法括号序列(按字典序升序)。若无解则不输出。
输入样例#1
2
输出样例#1
()
输入样例#2
4
输出样例#2
(()) ()()
输入样例#3
6
输出样例#3
((())) (()()) (())() ()(()) ()()()
数据范围:
1≤N≤20,N 是偶数。
#include <iostream>
#include <vector>
#include <string>
using namespace std;
// 回溯函数:生成所有合法括号序列
// res:存储结果的向量
// path:当前构建的括号序列
// left:已使用的左括号数量
// right:已使用的右括号数量
// n:目标序列长度
void backtrack(vector<string>& res, string& path, int left, int right, int n) {
// 当当前序列长度达到n时,加入结果集
if (path.size() == n) {
res.push_back(path);
return;
}
// 优先添加左括号(保证字典序),左括号数量不超过n/2
if (left < n / 2) {
path.push_back('(');
backtrack(res, path, left + 1, right, n);
path.pop_back(); // 回溯,移除最后添加的左括号
}
// 再添加右括号,右括号数量不能超过左括号数量(保证合法性)
if (right < left) {
path.push_back(')');
backtrack(res, path, left, right + 1, n);
path.pop_back(); // 回溯,移除最后添加的右括号
}
}
int main() {
int n;
cin >> n;
vector<string> result;
string path;
backtrack(result, path, 0, 0, n);
// 输出所有合法序列
for (const string& s : result) {
cout << s << endl;
}
return 0;
}搬运水果
在果园里,n 堆果实排成一个环形,第 i 堆果实的重量为 ai。果农需要将所有果实合并成一堆。合并规则如下:
(1)每次只能合并相邻的两堆,新堆的重量为两堆重量之和;
(2)每次合并消耗的体力等于新堆的重量;
(3)合并后新堆与剩余堆仍保持环形排列。
请设计合并顺序,求出合并全过程消耗的最小总体力与最大总体力。
时间限制:1000ms内存限制:256MB
输入格式
第一行:整数 n,表示果实堆数;
第二行:n 个整数 a1、a2、……、an,表示每堆果实的重量。
输出格式
第一行:最小总体力消耗;
第二行:最大总体力消耗。
输入样例
4 4 5 9 4
输出样例
43 54
数据范围:
1≤n≤100,1≤ai≤1000。
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(2 * n + 1, 0);
vector<int> prefix(2 * n + 1, 0);
// 读取输入并构建环形数组(复制一份接在末尾)
for (int i = 1; i <= n; i++) {
cin >> a[i];
a[i + n] = a[i];
}
// 计算前缀和
for (int i = 1; i <= 2 * n; i++) {
prefix[i] = prefix[i - 1] + a[i];
}
// DP数组初始化
vector<vector<int>> dp_min(2 * n + 1, vector<int>(2 * n + 1, INT_MAX));
vector<vector<int>> dp_max(2 * n + 1, vector<int>(2 * n + 1, 0));
// 初始化单个区间
for (int i = 1; i <= 2 * n; i++) {
dp_min[i][i] = 0;
dp_max[i][i] = 0;
}
// 区间DP计算
for (int len = 2; len <= n; len++) { // 区间长度
for (int l = 1; l <= 2 * n - len + 1; l++) { // 左端点
int r = l + len - 1; // 右端点
for (int k = l; k < r; k++) { // 分割点
int sum = prefix[r] - prefix[l - 1];
dp_min[l][r] = min(dp_min[l][r], dp_min[l][k] + dp_min[k + 1][r] + sum);
dp_max[l][r] = max(dp_max[l][r], dp_max[l][k] + dp_max[k + 1][r] + sum);
}
}
}
// 在环形中找最小值和最大值
int min_cost = INT_MAX;
int max_cost = 0;
for (int i = 1; i <= n; i++) {
min_cost = min(min_cost, dp_min[i][i + n - 1]);
max_cost = max(max_cost, dp_max[i][i + n - 1]);
}
cout << min_cost << endl;
cout << max_cost << endl;
return 0;
}//参考代码2
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
const int INF = INT_MAX / 2; // 避免溢出
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
if (n == 1) { // 只有一堆,无需合并
cout << 0 << endl;
cout << 0 << endl;
return 0;
}
// 将环形转为线性,扩展数组为2n长度
vector<int> b(2 * n);
for (int i = 0; i < 2 * n; ++i) {
b[i] = a[i % n];
}
// 计算前缀和,s[0] = 0, s[i] = b[0] + ... + b[i-1]
vector<int> s(2 * n + 1, 0);
for (int i = 1; i <= 2 * n; ++i) {
s[i] = s[i - 1] + b[i - 1];
}
// 初始化动态规划数组
vector<vector<int>> min_dp(2 * n, vector<int>(2 * n, 0));
vector<vector<int>> max_dp(2 * n, vector<int>(2 * n, 0));
// 填充dp数组,l为合并的堆数(从2到n)
for (int l = 2; l <= n; ++l) { // l表示当前合并的堆数
for (int i = 0; i + l - 1 < 2 * n; ++i) { // i为起始位置
int j = i + l - 1; // j为结束位置
// 初始化当前区间的最小和最大值
min_dp[i][j] = INF;
max_dp[i][j] = 0;
int sum_ij = s[j + 1] - s[i]; // i到j的总重量
// 尝试所有可能的拆分点k
for (int k = i; k < j; ++k) {
// 更新最小值
min_dp[i][j] = min(min_dp[i][j], min_dp[i][k] + min_dp[k + 1][j] + sum_ij);
// 更新最大值
max_dp[i][j] = max(max_dp[i][j], max_dp[i][k] + max_dp[k + 1][j] + sum_ij);
}
}
}
// 寻找环形结构的最小和最大体力消耗(所有可能的起始位置)
int min_total = INF;
int max_total = 0;
for (int i = 0; i < n; ++i) {
min_total = min(min_total, min_dp[i][i + n - 1]);
max_total = max(max_total, max_dp[i][i + n - 1]);
}
cout << min_total << endl;
cout << max_total << endl;
return 0;
}金字塔
给定长度为 n 的字符串 s。从 s 中提取子序列,组成 pyramid 字符串的方法有多少种?答案需对 109+7取模后输出。
时间限制:1000ms内存限制:256MB
输入格式
第一行:一个整数 n;
第二行:一个字符串 s。
输出格式
输出组成 pyramid 的方法数(取模 109+7)。
输入样例#1
5 pxxxx
输出样例#1
0
输入样例#2
10 pyyradmiid
输出样例#2
4
数据范围:
1≤N≤105,s 仅包含小写英文字母。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
const string TARGET = "pyramid";
int main() {
int n;
string s;
cin >> n >> s;
vector<long long> dp(TARGET.length() + 1, 0);
dp[0] = 1; // 空子序列,作为起点
for (int i = 0; i < n; i++) {
char c = s[i];
// 检查当前字符能匹配TARGET中的哪个位置
for (int j = TARGET.length() - 1; j >= 0; j--) {
if (c == TARGET[j]) {
dp[j + 1] = (dp[j + 1] + dp[j]) % MOD;
}
}
}
cout << dp[TARGET.length()] << endl;
return 0;
}链表去重
给定一个带整数键值的链表 L,你需要把其中绝对值重复的键值结点删掉。即对每个键值 K,只有第一个绝对值等于 K 的结点被保留。同时,所有被删除的结点须被保存在另一个链表上。
例如给定 L 为 21→-15→-15→-7→15,你需要输出去重后的链表 21→-15→-7,还有被删除的链表 -15→15。
时间限制:5000,内存限制:65536
输入
输入在第一行给出 L 的第一个结点的地址和一个正整数 N(≤ 105,为结点总数)。一个结点的地址是非负的 5 位整数,空地址 NULL 用 -1 来表示。
随后 N 行,每行按以下格式描述一个结点: 地址 键值 下一个结点 其中 地址 是该结点的地址,键值 是绝对值不超过104的整数,下一个结点 是下个结点的地址。
输出
首先输出去重后的链表,然后输出被删除的链表。每个结点占一行,按输入的格式输出。
样例输入
00100 5 99999 -7 87654 23854 -15 00000 87654 15 -1 00000 -15 99999 00100 21 23854
样例输出
00100 21 23854 23854 -15 99999 99999 -7 -1 00000 -15 87654 87654 15 -1
//该答案由AI生成
#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>
#include <cstdio>
#include <iomanip>
using namespace std;
struct Node {
int address;
int key;
int next;
};
int main() {
int start, n;
cin >> start >> n;
// 用数组存储所有节点,索引为节点地址
vector<Node> nodes(100000);
for (int i = 0; i < n; i++) {
int addr, key, next;
cin >> addr >> key >> next;
nodes[addr] = {addr, key, next};
}
unordered_set<int> seen; // 记录已出现过的绝对值
vector<Node> kept; // 保留链表的节点
vector<Node> removed; // 删除链表的节点
int current = start;
while (current != -1) {
int absKey = abs(nodes[current].key);
if (seen.find(absKey) == seen.end()) {
seen.insert(absKey);
kept.push_back(nodes[current]);
} else {
removed.push_back(nodes[current]);
}
current = nodes[current].next;
}
// 输出保留链表
for (int i = 0; i < kept.size(); i++) {
printf("%05d %d ", kept[i].address, kept[i].key);
if (i < kept.size() - 1) {
printf("%05d\n", kept[i + 1].address);
} else {
printf("-1\n");
}
}
// 输出删除链表
for (int i = 0; i < removed.size(); i++) {
printf("%05d %d ", removed[i].address, removed[i].key);
if (i < removed.size() - 1) {
printf("%05d\n", removed[i + 1].address);
} else {
printf("-1\n");
}
}
return 0;
}简单计算器
本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。计算器由两个堆栈组成,一个堆栈 S1 存放数字,另一个堆栈 S2 存放运算符。
计算器的最下方有一个等号键,每次按下这个键,计算器就执行以下操作:
(1)从 S1 中弹出两个数字,顺序为 n1 和 n2;
(2)从 S2 中弹出一个运算符 op;
(3)执行计算 n2 op n1;
(4)将得到的结果压回 S1。
直到两个堆栈都为空时,计算结束,最后的结果将显示在屏幕上。
时间限制:7000,内存限制:65536
输入
输入首先在第一行给出正整数 N(1 < N ≤ 10^3),为 S1 中数字的个数。
第二行给出 N 个绝对值不超过 100 的整数;
第三行给出 N-1 个运算符 —— 这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。
输出
将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2,将执行计算的最后结果输出。
注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109。
如果执行除法时出现分母为零的非法操作,则在一行中输出:ERROR: X/0,其中 X 是当时的分子。然后结束程序。
样例输入1
5 40 5 8 3 2 / * - +
样例输出1
2
样例输入2
5 2 5 8 4 4 * / - +
样例输出2
ERROR: 5/0
//该答案由AI生成
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main() {
int n;
cin >> n;
stack<int> nums;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
nums.push(num);
}
stack<char> ops;
for (int i = 0; i < n - 1; i++) {
char op;
cin >> op;
ops.push(op);
}
while (!ops.empty()) {
int n1 = nums.top();
nums.pop();
int n2 = nums.top();
nums.pop();
char op = ops.top();
ops.pop();
int result;
if (op == '+') {
result = n2 + n1;
} else if (op == '-') {
result = n2 - n1;
} else if (op == '*') {
result = n2 * n1;
} else if (op == '/') {
if (n1 == 0) {
cout << "ERROR: " << n2 << "/0" << endl;
return 0;
}
result = n2 / n1; // 整数除法
}
nums.push(result);
}
cout << nums.top() << endl;
return 0;
}两头进一头出
某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。现给定入队的序列,请你判断一系列出队序列是否可能。
例如按 1、2、3、4、5 的顺序入队,则 1、3、2、5、4 这样的出队序列是可以得到的,但 5、1、3、2、4 就是不可能得到的。
时间限制:4000,内存限制:65536
输入
输入首先在一行中给出两个正整数 N 和 K(≤ 10),分别是入队元素的个数和待查验的序列个数。
随后一行给出 N 个两两不同的整数组成的入队序列;再跟着 K 行,每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。
输出
对每个需要查验的出队序列,如果是可能的,则在一行中输出 yes,否则输出 no。
样例输入
5 4 10 2 3 4 5 10 3 2 5 4 5 10 3 2 4 2 3 10 4 5 3 5 10 4 2
样例输出
yes no yes no
//该答案由AI生成
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <map>
using namespace std;
bool check(vector<int>& in, vector<int>& out, const map<int, int>& index_map) {
deque<int> deq;
set<int> inDeque;
int n = in.size();
int i0 = 0, j0 = 0;
while (i0 < n) {
if (!deq.empty() && deq.front() == out[i0]) {
int x = deq.front();
deq.pop_front();
inDeque.erase(x);
i0++;
} else {
if (inDeque.find(out[i0]) != inDeque.end()) {
return false;
}
if (j0 >= n) {
return false;
}
auto it = index_map.find(out[i0]);
if (it == index_map.end()) {
return false;
}
int pos = it->second;
if (pos < j0) {
return false;
}
for (int k = j0; k < pos; k++) {
deq.push_back(in[k]);
inDeque.insert(in[k]);
}
deq.push_front(in[pos]);
inDeque.insert(in[pos]);
j0 = pos + 1;
int x = deq.front();
deq.pop_front();
inDeque.erase(x);
i0++;
}
}
return true;
}
int main() {
int N, K;
cin >> N >> K;
vector<int> in(N);
map<int, int> index_map;
for (int i = 0; i < N; i++) {
cin >> in[i];
index_map[in[i]] = i;
}
for (int i = 0; i < K; i++) {
vector<int> out(N);
for (int j = 0; j < N; j++) {
cin >> out[j];
}
if (check(in, out, index_map)) {
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
return 0;
}整型关键字的平方探测法散列
本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 H(key) = key % TSize,其中 TSize 是散列表的表长。要求用平方探测法(只增不减,即H(Key)+i2)解决冲突。
注意散列表的表长最好是个素数。如果输入给定的表长不是素数,你必须将表长重新定义为大于给定表长的最小素数。
时间限制:4000,内存限制:65536
输入
首先第一行给出两个正整数 MSize(≤ 10^4)和 N(≤ MSize),分别对应输入的表长和输入数字的个数。
随后第二行给出 N 个不重复的正整数,数字间以空格分隔。
输出
在一行中按照输入的顺序给出每个数字在散列表中的位置(下标从 0 开始)。如果某个数字无法插入,就在其位置上输出 -。输出间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
4 4 10 6 4 15
样例输出
0 1 4 -
//该答案由AI生成
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isPrime(int num) {
if (num <= 1) return false;
if (num == 2) return true;
if (num % 2 == 0) return false;
for (int i = 3; i <= sqrt(num); i += 2) {
if (num % i == 0) return false;
}
return true;
}
int nextPrime(int n) {
if (n <= 1) return 2;
int prime = n;
bool found = false;
while (!found) {
prime++;
if (isPrime(prime)) found = true;
}
return prime;
}
int main() {
int MSize, N;
cin >> MSize >> N;
int TSize = MSize;
if (!isPrime(TSize)) {
TSize = nextPrime(MSize);
}
vector<int> hashTable(TSize, -1);
vector<string> results;
for (int idx = 0; idx < N; idx++) {
int key;
cin >> key;
bool inserted = false;
for (int i = 0; i < TSize; i++) {
int pos = (key % TSize + i * i) % TSize;
if (hashTable[pos] == -1) {
hashTable[pos] = key;
results.push_back(to_string(pos));
inserted = true;
break;
}
}
if (!inserted) {
results.push_back("-");
}
}
for (int i = 0; i < results.size(); i++) {
if (i > 0) cout << " ";
cout << results[i];
}
cout << endl;
return 0;
}星星的个数
题目描述
你每天都会收集不同数量的星星贴纸。当收集到第 k 天时 (1≤k≤n),他当天获得的贴纸数量是 k 张,而每张贴纸上印着的星星数量等于 k 这个数字的因数个数(比如数字6有4个因数:1,2,3,6,就印4颗星星)。请计算你这 n 天收集到的星星总数。
输入格式
输入一个整数 n。
输出格式
共一行,这 n 天收集到的星星总数。
输入样例#1
4
输出样例#1
23
输入样例#2
100
输出样例#2
26879
输入样例#3
10000000
输出样例#3
838627288460105
说明提示
数据范围
1 ≤ N ≤ 107
样例1说明
1× 1 + 2× 2 + 3× 2 + 4× 3 =23
限制
时间限制:1000ms
内存限制:512MiB
#include<iostream>
using namespace std;
int main()
{
long long n;
cin >> n;
long long sum = 0;
for (int d = 1; d <= n; ++d) {
long long k = n / d;
sum += d * (k + 1) * k / 2;
}
cout << sum << "\n";
return 0;
}数零
题目描述
给定一个整数 n,请统计从 1 开始,到 n 为止的所有整数的十进制表示中,一共出现了多少个 0?
例如 n=100 时,1 到 100 中,只有以下数字出现过 0:
10, 20, 30, 40, 50, 60, 70, 80, 90, 100
所以总计出现 11 次。
输入格式
单个整数:表示 n。
输出格式
单个整数:表示 0 出现的次数。
输入样例
99
输出样例
9
说明提示
对于 30% 的数据,n≤100,000;
对于 60% 的数据,n≤10,000,000;
对于 100% 的数据,1≤n≤1,000,000,000,000。
限制
时间限制:1000ms
内存限制:512MiB
#include<iostream>
int main()
{
long long n;
std::cin >> n;
long long c = 0;
long long p = 1;
long long t = 0;
while (n > 0) {
int d = n % 10;
n /= 10;
if (d > 0) {
c += n * p;
}
else {
c += (n-1) * p;
c += t + 1;
}
t += d * p;
p *= 10;
}
std::cout << c << "\n";
return 0;
}迷宫路径
题目描述
给定 n×m 个方格构成的图,每个格子都有一种地形:
有一些格子是墙,以符号 X 表示,墙不可通行。
有一些格子是空地,以符号 . 表示,空地可以通行。
请统计从左上角的方格出发,有多少种不同的路线可以以最短距离走到右下角。在行走过程中,不能进入地形为墙的方格,保证起点与终点方格地形不是墙。且行走时,只能移动到水平或垂直方向相邻的方格。
由于方案数可能很大,输出模 1,000,000,007 的余数。
输入格式
第一行:单个整数 n 与 m
第二行到第 n+1 行:第i+1 行每行有 m 个整数表示第 i 行的地形
输出格式
单个整数:表示路线方案模 1,000,000,007 的余数。
输入样例
3 3 ... .X. ...
输出样例
2
说明提示
30% 的数据,1≤n,m≤4
60% 的数据,1≤n,m≤10
100% 的数据,1≤n,m≤1000
限制
时间限制:1000ms
内存限制:512MiB
#include<iostream>
char a[1000][1000];
int d[1000][1000];
int w[1000][1000];
int n, m;
int qx[1000*1000];
int qy[1000*1000];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
void bfs(int x, int y) {
qx[0] = x;
qy[0] = y;
d[x][y] = 1;
w[x][y] = 1;
int head = 0;
int tail = 1;
while (head < tail) {
int x = qx[head];
int y = qy[head];
head++;
for (int k = 0; k < 4; ++k) {
int nx = x + dx[k];
int ny = y + dy[k];
if (0 <= nx and nx < n and 0 <= ny and ny < m and a[nx][ny] == '.') {
if (d[nx][ny] == 0) {
d[nx][ny] = d[x][y] + 1;
w[nx][ny] = w[x][y];
qx[tail] = nx;
qy[tail] = ny;
tail++;
}
else if (d[nx][ny] == d[x][y] + 1) {
w[nx][ny] += w[x][y];
w[nx][ny] %= 1000000007;
}
}
}
}
}
int main()
{
std::cin >> n >> m;
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j) {
std::cin >> a[i][j];
}
bfs(0, 0);
std::cout << w[n-1][m-1] << "\n";
return 0;
}表达式的值
题目描述
后缀表达式,它的定义如下:
单个数字如 6,8 等都是后缀表达式;
如果 e1,e2 都是后缀表达式,则 e1 e2 +e1 e2 +、e1 e2 −e1 e2 −、e1 e2 ∗e1 e2 ∗ 都是后缀表达式;
不满足以上两条规则的表达式都不是后缀表达式。
给定一个后缀表达式(保证合法),请计算表达式的值,并输出它模 10007 的余数。
注意,为了方便起见,我们省略了除法,同时也规定在表达式中出现的数字只能由一位数构成。
输入格式
一个字符序列:表示输入的后缀表达式。每个字符间用一个空格分开。保证输入字符只可能出现 0 到 9 及 +,-,* 三种运算符,且构成一个合法的后缀表达式。
输出格式
单个数字:表示表达式的值模 10007 的余数,注意余数必须大于或等于零。
输入样例#1
3 4 +
输出样例#1
7
输入样例#2
2 3 3 + *
输出样例#2
12
输入样例#3
1 2 * 3 + 4 * 5 - 6 + 7 * 8 - 9 +
输出样例#3
148
输入样例#4
1 5 -
输出样例#4
6
说明提示
数据范围
记输入的可见字符数量为 n,
对于 50% 的数据,1≤n≤100;
对于 100% 的数据,1≤n≤100,000。
样例2解释:
2*(3+3)=12
限制
时间限制:1000ms
内存限制:512MiB
#include <iostream>
#include <stack>
using namespace std;
const int mod = 10007;
int main() {
stack<int> s;
char c;
while (cin >> c) {
if (c >= '0' && c <= '9') {
s.push(c - '0');
} else {
int b = s.top(); s.pop();
int a = s.top(); s.pop();
if (c == '+') s.push((a + b) % mod);
else if (c == '-') s.push((a - b + mod) % mod);
else if (c == '*') s.push((a * b) % mod);
}
}
cout << s.top() << endl;
return 0;
}链表元素分类
给定一个单链表,请编写程序将链表元素进行分类排列,使得所有负值元素都排在非负值元素的前面,而 [0, K] 区间内的元素都排在大于 K 的元素前面。但每一类内部元素的顺序是不能改变的。例如:给定链表为 18→7→-4→0→5→-6→10→11→-2,K 为 10,则输出应该为 -4→-6→-2→7→0→5→10→18→11。
时间限制:1000
内存限制:65536
输入
每个输入包含一个测试用例。每个测试用例第 1 行给出:第 1 个结点的地址;结点总个数,即正整数N (≤ 105);以及正整数K (≤ 103)。结点的地址是 5 位非负整数,NULL 地址用 -1 表示。 接下来有 N 行,每行格式为: Address Data Next 其中 `Address` 是结点地址;`Data` 是该结点保存的数据,为 [-105, 105] 区间内的整数;`Next` 是下一结点的地址。题目保证给出的链表不为空。
输出
对每个测试用例,按链表从头到尾的顺序输出重排后的结果链表,其上每个结点占一行,格式与输入相同。
样例输入
00100 9 10 23333 10 27777 00000 0 99999 00100 18 12309 68237 -6 23333 33218 -4 00000 48652 -2 -1 99999 5 68237 27777 11 48652 12309 7 33218
样例输出
33218 -4 68237 68237 -6 48652 48652 -2 12309 12309 7 00000 00000 0 99999 99999 5 23333 23333 10 00100 00100 18 27777 27777 11 -1
//参考程序1
#include <iostream>
#include <vector>
using namespace std;
struct Node {
int addr, data, next;
};
int main() {
int head, n, k;
cin >> head >> n >> k;
vector<Node> nodes(100000);
for (int i = 0; i < n; ++i) {
int addr;
cin >> addr;
cin >> nodes[addr].data >> nodes[addr].next;
nodes[addr].addr = addr;
}
vector<Node> negative, zeroToK, greater;
for (int p = head; p != -1; p = nodes[p].next) {
if (nodes[p].data < 0) negative.push_back(nodes[p]);
else if (nodes[p].data <= k) zeroToK.push_back(nodes[p]);
else greater.push_back(nodes[p]);
}
negative.insert(negative.end(), zeroToK.begin(), zeroToK.end());
negative.insert(negative.end(), greater.begin(), greater.end());
for (int i = 0; i < negative.size(); ++i) {
if (i < negative.size() - 1) negative[i].next = negative[i + 1].addr;
else negative[i].next = -1;
printf("%05d %d ", negative[i].addr, negative[i].data);
if (negative[i].next != -1) printf("%05d\n", negative[i].next);
else printf("-1\n");
}
return 0;
}//参考程序2
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
struct NodeInfo {
string address;
int data;
string next;
};
int main() {
string start_addr;
int N, K;
cin >> start_addr >> N >> K;
unordered_map<string, pair<int, string>> node_map;
for (int i = 0; i < N; ++i) {
string addr, next;
int data;
cin >> addr >> data >> next;
node_map[addr] = {data, next};
}
vector<NodeInfo> nodes_old;
string current = start_addr;
while (current != "-1") {
auto& p = node_map[current];
nodes_old.push_back({current, p.first, p.second});
current = p.second;
}
vector<NodeInfo> group_neg, group_mid, group_big;
for (auto& node : nodes_old) {
if (node.data < 0) {
group_neg.push_back(node);
} else if (node.data <= K) {
group_mid.push_back(node);
} else {
group_big.push_back(node);
}
}
vector<NodeInfo> nodes_new;
nodes_new.insert(nodes_new.end(), group_neg.begin(), group_neg.end());
nodes_new.insert(nodes_new.end(), group_mid.begin(), group_mid.end());
nodes_new.insert(nodes_new.end(), group_big.begin(), group_big.end());
for (int i = 0; i < nodes_new.size(); ++i) {
if (i == nodes_new.size() - 1) {
nodes_new[i].next = "-1";
} else {
nodes_new[i].next = nodes_new[i+1].address;
}
}
for (auto& node : nodes_new) {
cout << node.address << " " << node.data << " " << node.next << endl;
}
return 0;
}出栈序列的合法性
给定一个最大容量为 m 的堆栈,将 n 个数字按 1, 2, 3, ..., n 的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的?例如给定 m=5、n=7,则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 },但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。
时间限制:1000
内存限制:65536
输入
输入第一行给出 3 个不超过 1000 的正整数:m(堆栈最大容量)、n(入栈元素个数)、k(待检查的出栈序列个数)。最后 k 行,每行给出 n 个数字的出栈序列。所有同行数字以空格间隔。
输出
对每一行出栈序列,如果其的确是有可能得到的合法序列,就在一行中输出 `YES`,否则输出 `NO`。
样例输入
5 7 5 1 2 3 4 5 6 7 3 2 1 7 5 6 4 7 6 5 4 3 2 1 5 6 4 3 7 2 1 1 7 6 5 4 3 2
样例输出
YES NO NO YES NO
//参考程序1
#include<bits/stdc++.h>
using namespace std;
int m,n,k;
bool is_possible(int out[])
{
stack<int> s;
int x=1,y=0;
next:
if(y==n)return 1;
while(1)
{
if(s.size()>=m||x>n)return 0;
s.push(x);
x++;
if(s.top()==out[y])break;
}
while(1)
{
if(s.size()==0)break;
if(s.top()==out[y])
{
s.pop();
y++;
}
else break;
}
goto next;
}
int main()
{
cin>>m>>n>>k;
for(int i=0;i<k;i++)
{
int out[n];
for(int j=0;j<n;j++)
cin>>out[j];
if(!is_possible(out))cout<<"NO"<<endl;
else cout<<"YES"<<endl;
}
return 0;
}//参考程序2
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main() {
int m, n, k;
cin >> m >> n >> k;
while (k--) {
vector<int> seq(n);
for (int i = 0; i < n; ++i) {
cin >> seq[i];
}
stack<int> st;
int current_max = 0;
bool valid = true;
for (int v : seq) {
if (v > current_max) {
int needed = v - current_max;
if (st.size() + needed > m) {
valid = false;
break;
}
for (int i = current_max + 1; i <= v; ++i) {
st.push(i);
}
current_max = v;
st.pop(); // 弹出v
} else {
if (st.empty() || st.top() != v) {
valid = false;
break;
} else {
st.pop();
}
}
}
cout << (valid ? "YES" : "NO") << endl;
}
return 0;
}取行李
一般机场里,航班到达后,旅客们会去到达区的行李传送带那里取自己的行李。
现假设有一座特别的机场,每条传送带只有一个取行李的窗口。旅客们必须排好队,逐一到窗口取自己的行李。但是当某人到窗口前,发现行李不是自己的,那人就只好走到队尾去等下一次机会。此时那件行李会一直等在窗口,直到它的主人把它取走。假设每一次认领需要 1 分钟,本题就要求你计算传送带清空需要的时间、以及旅客们的平均等待时间。
例如,假设行李 i 属于旅客 i。行李的到达顺序是 1、2、3,旅客的到达顺序是 2、1、3。则 1 号行李要等 2 分钟才能被主人 1 号旅客取走。这时行李队列中有 2、3,旅客队列中是 3、2。于是 2 号行李还要等 2 分钟才能被 2 号旅客取走,最后 3 号在第 5 分钟取走行李。旅客们的平均等待时间是 (2+4+5)/3 ≈ 3.7。
时间限制:1000
内存限制:65536
输入
输入首先在第一行给出一个正整数 N(≤ 103)。下一行给出 N 个数字,是 [1, N] 区间内整数的一个重排列,表示旅客队列。这里我们假设行李队列是按 1、2、……、N 有序的,并且行李 i 属于旅客 i。一行中数字间以空格分隔。
输出
在一行中输出传送带清空需要的时间、以及旅客们的平均等待时间(输出小数点后 1 位)。数字间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
5 3 5 1 2 4
样例输出
9 6.0
#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;
int main() {
int N;
cin >> N;
vector<int> passengers(N);
for (int i = 0; i < N; ++i) {
cin >> passengers[i];
}
queue<int> q;
for (int p : passengers) {
q.push(p);
}
int current_luggage = 1;
int time = 0;
vector<int> wait_time(N + 1, 0); // 使用1-based索引
while (current_luggage <= N) {
int p = q.front();
q.pop();
if (p == current_luggage) {
time += 1;
wait_time[p] = time;
current_luggage += 1;
} else {
time += 1;
q.push(p);
}
}
int total_time = time;
double sum = 0;
for (int i = 1; i <= N; ++i) {
sum += wait_time[i];
}
double avg = sum / N;
cout << total_time << " " << fixed << setprecision(1) << avg << endl;
return 0;
}散列表平均查找时间
本题目标很简单:首先将一系列各不相同的正整数键值插入一张散列表,随后在表中查找另外给定的一个整数键值系列,输出平均查找时间(确定一个数字在或不在表中所需要比较的次数)。这里用到的哈希函数定义为 H(key) = key % TSize,其中 TSize 是散列表的容量。使用平方探测(仅做正向递增的探测)来解决冲突。
注意散列表的容量最好是一个素数。如果用户给出的容量不是素数,你必须将容量重新定义为比用户给定容量大的一个最小的素数。
时间限制:1000
内存限制:65536
输入
输入第一行给出 3 个正整数:MSize、N、M,分别是用户定义的散列表容量、要插入的键值的数量、以及要查找的键值的数量。这 3 个数都不超过 104。 随后第二行给出 N 个各不相同的正整数键值待插入。第三行给出 M 个正整数键值待查找。同一行中数字间以一个空格分隔,数均不超过 105。
输出
如果某个数无法插入,则在一行中输出 `X cannot be inserted.`,其中 `X` 是那个输入的数字。最后一行输出全部 M 个键值的平均查找时间,精确到小数点后 1 位。
样例输入
4 5 4 10 6 4 15 11 11 4 15 2
样例输出
15 cannot be inserted. 2.8
//参考程序1
#include <iostream>
#include <vector>
#include <iomanip>
// 找到比给定数大的最小素数
int nextPrime(int num) {
if (num <= 2) return 2;
if (num % 2 == 0) num++;
while (true) {
bool isPrime = true;
for (int i = 3; i * i <= num; i += 2) {
if (num % i == 0) {
isPrime = false;
break;
}
}
if (isPrime) break;
num += 2;
}
return num;
}
int main() {
int mSize, n, m;
std::cin >> mSize >> n >> m;
mSize = nextPrime(mSize);
std::vector<int> hashTable(mSize, -1);
// 插入键值
for (int i = 0; i < n; ++i) {
int key;
std::cin >> key;
int hash = key % mSize;
bool inserted = false;
for (int j = 0; j < mSize; ++j) {
int index = (hash + j * j) % mSize;
if (hashTable[index] == -1) {
hashTable[index] = key;
inserted = true;
break;
}
}
if (!inserted) {
std::cout << key << " cannot be inserted." << std::endl;
}
}
// 查找键值
int totalSearchTime = 0;
for (int i = 0; i < m; ++i) {
int key;
std::cin >> key;
int hash = key % mSize;
for (int j = 0; j <= mSize; ++j) {
totalSearchTime++;
int index = (hash + j * j) % mSize;
if (hashTable[index] == key || hashTable[index] == -1) {
break;
}
}
}
// 输出平均查找时间
double averageSearchTime = static_cast<double>(totalSearchTime) / m;
std::cout << std::fixed << std::setprecision(1) << averageSearchTime << std::endl;
return 0;
}//参考程序2
#include <iostream>
#include <vector>
#include <iomanip>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) return false;
}
return true;
}
int getTSize(int m) {
if (isPrime(m)) return m;
int t = m + 1;
while (true) {
if (isPrime(t)) return t;
++t;
}
}
int main() {
int MSize, N, M;
cin >> MSize >> N >> M;
int TSize = getTSize(MSize);
vector<int> hashTable(TSize, -1); // -1表示空位置
// 插入元素到哈希表
vector<bool> insertedKeys(N);
for (int i = 0; i < N; ++i) {
int key;
cin >> key;
int h = key % TSize;
bool inserted = false;
for (int j = 0; j < TSize; ++j) {
int pos = (h + j * j) % TSize;
if (hashTable[pos] == -1) {
hashTable[pos] = key;
inserted = true;
break;
}
}
if (!inserted) {
cout << key << " cannot be inserted." << endl;
}
}
// 计算平均查找时间
double total = 0.0;
for (int i = 0; i < M; ++i) {
int key;
cin >> key;
int h = key % TSize;
int count = 0;
for (int j = 0; j < TSize; ++j) {
++count;
int pos = (h + j * j) % TSize;
if (hashTable[pos] == -1) {
break;
} else if (hashTable[pos] == key) {
break;
}
}
total += count;
}
double avg = total / M;
cout << fixed << setprecision(1) << avg << endl;
return 0;
}