C/C++编程六级 题库
多项式相加(2023.12)
我们经常遇到两多项式相加的情况, 在这里, 我们就需要用程序来模拟实现把两个多项式相加到一起。 首先, 我们会有两个多项式,每个多项式是独立的一行, 每个多项式由系数、 幂数这样的多个整数对来表示。
如多项式 2x20- x17+ 5x9- 7x7+ 16x5+ 10x4 + 22x2- 15
对应的表达式为: 2 20 -1 17 5 9 - 7 7 16 5 10 4 22 2 -15 0。
为了标记每行多项式的结束, 在表达式后面加上了一个幂数为负数的整数对。
同时输入表达式的幂数大小顺序是随机的。我们需要做的就是把所给的两个多项式加起来。
时间限制: 1000
内存限制: 65536
输入
输入包括多行。 第一行整数 n,表示有多少组的多项式需要求和。 (1 <n < 100) 下面为 2n 行整数, 每一行都是一个多项式的表达式。 表示 n组需要相加的多项式。 每行长度小于 300。
输出
输出包括 n 行, 每行为 1 组多项式相加的结果。 在每一行的输出结果中, 多项式的每一项用“[x y]” 形式的字符串表示, x 是该项的系数、 y 是该项的幂数。 要求按照每一项的幂从高到低排列, 即先输出幂数高的项、 再输出幂数低的项。 系数为零的项不要输出。
样例输入
2 -1 17 2 20 5 9 -7 7 10 4 22 2 -15 0 16 5 0 -1 2 19 7 7 3 17 4 4 15 10 -10 5 13 2 -7 0 8 -8 -1 17 2 23 22 2 6 8 -4 7 -18 0 1 5 21 4 0 -1 12 7 -7 5 3 17 23 4 15 10 -10 5 13 5 2 19 9 -7
样例输出
[ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ] [ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]
提示
第一组样例数据的第二行末尾的 8 -8, 因为幂次-8 为负数, 所以这一行数据结束, 8 -8 不要参与计算。
#include <iostream>
#include <map>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
for (int i = 0; i != n; ++i) {
map<int, int> ploy;
int index, value, over = 0;
while (cin >> value >> index) {
if (index < 0)
over++;
else {
pair<map<int, int>::iterator, bool> ret =
ploy.insert(make_pair(index, value));
if (!ret.second)
ret.first->second += value;
}
if (over == 2)
break;
}
for (map<int, int>::reverse_iterator riter = ploy.rbegin();
riter != ploy.rend(); ++riter) {
if (riter->second != 0)
cout << "[ " << riter->second << ' ' << riter->first << " ] ";
}
cout << endl;
}
return 0;
}作品选拔
题目描述
创新大赛组委会收到了 n 件学生参赛作品,每件作品都有对应的综合评审得分,其中第 i 件作品的得分为 ai。
根据赛事章程,组委会需从所有备选作品中选出 m 件作品晋级市级终评。为保障终评作品的整体质量,要求选出的 m 件作品中,至少有 k 件作品的综合得分不低于赛事划定的基准线 x。
请你帮助组委会计算,一共有多少种符合要求的作品遴选方案?由于答案数值可能过大,请输出方案数对998244353取模后的结果。
输入格式
第一行,两个正整数n、m;
第二行,n 个正整数,分别表示 a1、a2、……、an;
第三行,两个正整数 k、x。
输出格式
输出满足条件的方案数对 998244353 取模后的结果。
输入样例#1
3 2
10 20 30
1 20
输出样例#1
3
输入样例#2
4 2
5 10 15 20
1 12
输出样例#2
5
说明提示:
对于50%的数据,1≤n≤20;
对于100%的数据,1≤n≤1000,1≤k≤m≤n,1≤ai、x≤10^9。
限制:
时间限制:1000ms,内存限制:256MiB
#include <iostream>
#include <algorithm>
using namespace std;
const int MOD = 998244353;
const int MAX = 1005;
long long C[MAX][MAX];
// 预处理组合数 C(n, k)
void init() {
C[0][0] = 1;
for (int i = 1; i < MAX; i++) {
C[i][0] = 1;
for (int j = 1; j <= i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
}
int main() {
init();
// 第一步:读 n, m
int n, m;
cin >> n >> m;
// 第二步:读 n 个分数
int a[MAX];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 第三步:读 k, x
int k, x;
cin >> k >> x;
// 统计高分、低分数量
int high = 0, low = 0;
for (int i = 0; i < n; i++) {
if (a[i] >= x) high++;
else low++;
}
// 计算答案
long long ans = 0;
int max_t = min(high, m);
for (int t = k; t <= max_t; t++) {
int need = m - t;
if (need < 0 || need > low) continue;
ans = (ans + C[high][t] * C[low][need]) % MOD;
}
cout << ans << 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;
}整型关键字的平方探测法散列
本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 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;
}迷宫路径
题目描述
给定 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;
}散列表平均查找时间
本题目标很简单:首先将一系列各不相同的正整数键值插入一张散列表,随后在表中查找另外给定的一个整数键值系列,输出平均查找时间(确定一个数字在或不在表中所需要比较的次数)。这里用到的哈希函数定义为 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;
}