首页 › 题库 › C/C++编程考级 › 5 数论

C/C++编程六级 题库

共 8 道题 · 按题型筛选,点「查看答案」核对解析
1 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 5 数论
利用欧几里得辗转相除法计算 gcd(48,36),最大公约数结果?( )
A
4
B
6
C
12
D
18
答案与解析
正确答案:C
将两个数中较大者作为被除数,较小者作为除数进行整除运算,得到余数;若余数不为零,则将原除数作为新的被除数,余数作为新的除数继续运算;重复此过程直至余数为零,此时的除数即为两数的最大公约数。每一步运算仅依赖前一步的被除数与除数,运算过程为确定性迭代,无分支或条件判断介入。
题目详情
2 单选题 适中 C/C++编程考级 ·C/C++编程六级 · 5 数论

欧几里得算法(辗转相除法)用于求解?( )

A
两个数的最小公倍数
B
两个数的最大公约数
C
素数判定
D
快速幂运算
答案与解析
正确答案:B
这道题暂未补解析。
题目详情
3 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

多项式相加(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;
}
题目详情
4 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

作品选拔

题目描述

创新大赛组委会收到了 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;
}
题目详情
5 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

金字塔

给定长度为 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;
}
题目详情
6 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

整型关键字的平方探测法散列

本题的任务很简单:将给定的无重复正整数序列插入一个散列表,输出每个输入的数字在表中的位置。所用的散列函数是 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;
}
题目详情
7 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

迷宫路径

题目描述

给定 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;
}
题目详情
8 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 5 数论

散列表平均查找时间

本题目标很简单:首先将一系列各不相同的正整数键值插入一张散列表,随后在表中查找另外给定的一个整数键值系列,输出平均查找时间(确定一个数字在或不在表中所需要比较的次数)。这里用到的哈希函数定义为 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;
}


题目详情