GESP-C++五级 题库
假设我们有两个数 a=38和b=14,它们对模 同余,即 a=b(mod m)。以下哪个值不可能是 m?
有如下函数 fun ,则 fun(20, 12) 的返回值为( )。
函数为辗转相除求两数的最大公约数,结果为4,如果没有看出函数作用,也可以手动模拟递归过程。
现在有 n 个人要过河,每只船最多载2人,船的承重为100kg。下列代码中,数组 weight 中保存有 n 个人的体重(单位为kg),已经按从小到大排好序,代码输出过河所需要的船的数目,采用的思想为( )。
重量已经按照从小到大排序了,然后双指针处理,双指针的过程为最轻的人和最重的人尝试能否在同一个船上,如果可以,那么他们在同一个船上,否则,当前最重的人不能和其他人在一个船上,得单独一条船。采用的是贪心的思想。
下面C++代码用于将输入金额换成最少币种组合方案,其实现算法是( )。
贪心算法:贪心算法是一种在每一步选择中都采取当前状态下最优(最有利)的选择,以期望最终能够达到全局最优解。在这段代码中,每次循环都选择当前面值最大的硬币进行尽可能多的使用,从而达到最少硬币数量的组合方案。
算法实现分析:
数组coins 存储了面值从大到小的硬币面额{100, 50, 20, 10, 5, 2, 1}。
函数find_coins() 中使用了一个循环遍历所有硬币面额。在每次循环中,计算当前金额money 可以使用的当前面额硬币数量,并更新剩余金额money。
循环结束后,coins_used 数组存储了每种面额硬币的使用数量,以达到组合最少硬币数量的目的。
选择最优:由于每次都选择当前最大面额的硬币,贪心算法能够在保证每次选择最优的情况下,快速得到全局最优解,即使用最少数量的硬币来组合金额。
根据代码实现方式和贪心算法的特性,这段C++代码确实属于贪心算法。
下面的C++代码用于输出每个数对应的质因数列表,输出形如: {5: [5], 6: [2, 3], 7: [7], 8: [2, 2, 2]} 。( )
奖品兑换
时间限制:1 s,内存限制:512 MB
【问题描述】
班主任给上课专心听讲、认真完成作业的同学们分别发放了若干张课堂优秀券和作业优秀券。同学们可以使用这两种券找班主任兑换奖品。
具体来说,可以使用 a 张课堂优秀券和 b 张作业优秀券兑换一份奖品,或者使用 b 张课堂优秀券和 a 张作业优秀券兑换一份奖品。
现在小 A 有 n 张课堂优秀券和 m 张作业优秀券,他最多能兑换多少份奖品呢?
【输入描述】
第一行,两个正整数 n、m,分别表示小 A 持有的课堂优秀券和作业优秀券的数量。
第二行,两个正整数 a、b,表示兑换一份奖品所需的两种券的数量。
【输出描述】
输出共一行,一个整数,表示最多能兑换的奖品份数。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%测试点,保证 1 <= a、b <= 100,1 <= n、m <= 500。
对于所有测试点,保证 1 <= a、b <= 10^4,1 <= n、m <= 10^9。
#include <iostream>
using namespace std;
int n, m, a, b;
int l, r;
int check(int v) {
long long x, y, t;
x = 1ll * v * a;
y = 1ll * v * b;
if (y > m) {
t = (y - m + (b - a) - 1) / (b - a);
y -= t * (b - a);
x += t * (b - a);
}
return x <= n && y <= m;
}
int main() {
cin >> n >> m >> a >> b;
if (n > m)
swap(n, m);
if (a > b)
swap(a, b);
if (a == b) {
cout << n / a << endl;
return 0;
}
l = 0;
r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (check(mid))
l = mid;
else
r = mid - 1;
}
cout << r << endl;
return 0;
}平均分配
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有 2n 件物品,小 B 和小 C 想从小 A 手上买走这些物品。对于第 i 件物品,小 B 会以 bi 的价格购买,而小 C 会以 ci 的价格购买。
为了平均分配这 2n 件物品,小 A 决定小 B 和小 C 各自只能买走恰好 n 件物品。你能帮小 A 求出他卖出这 2n 件物品所能获得的最大收入吗?
【输入描述】
第一行,一个正整数 n。
第二行, 2n 个整数 b1、b2、……、b(2n)。
第三行, 2n 个整数 c1、c2、……、c(2n)。
【输出描述】
一行,一个整数,表示答案。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=8。
对于另外 20% 的测试点,保证 0<=bi<=1,0<=ci<=1 。
对于所有测试点,保证 0<=n<=10^5,0<=bi<=10^9 ,0<=ci<=10^9 。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n;
long long b[N], c[N], d[N];
long long ans;
int main() {
scanf("%d", &n);
assert(1 <= n && n <= 1e5);
for (int i = 1; i <= 2 * n; i++)
scanf("%lld", &b[i]), assert(0 <= b[i] && b[i] <= 1e9);
for (int i = 1; i <= 2 * n; i++)
scanf("%lld", &c[i]), assert(0 <= c[i] && c[i] <= 1e9);
for (int i = 1; i <= 2 * n; i++) {
ans += b[i];
d[i] = c[i] - b[i];
}
sort(d + 1, d + 2 * n + 1);
for (int i = n + 1; i <= 2 * n; i++)
ans += d[i];
printf("%lld\n", ans);
return 0;
}小杨的幸运数
时间限制:1.0 s
内存限制:128.0 MB
问题描述
小杨认为,所有大于等于 的完全平方数都是他的超级幸运数。
小杨还认为,所有超级幸运数的倍数都是他的幸运数。自然地,小杨的所有超级幸运数也都是幸运数。
对于一个非幸运数,小杨规定,可以将它一直+1,直到它变成一个幸运数。我们把这个过程叫做幸运化。例如,如果a=4,那么4是最小的幸运数,而1不是,但我们可以连续对1做3次+1操作,使其变为4,所以我们可以说,1幸运化后的结果是4。
现在,小杨给出N个数,请你首先判断它们是不是幸运数;接着,对于非幸运数,请你将它们幸运化。
输入描述
第一行 2 个正整数a,N。
接下来N行,每行一个正整数x,表示需要判断(幸运化)的数。
输出描述
输出N行,对于每个给定的x,如果它是幸运数,请输出 lucky ,否则请输出将其幸运化后的结果。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
1虽然是完全平方数,但它小于a,因此它并不是超级幸运数,也不是幸运数。将其进行3次+1操作后,最终得到幸运数 。
4是幸运数,因此直接输出 lucky 。
5不是幸运数,将其进行3次+1操作后,最终得到幸运数8。
9是幸运数,因此直接输出 lucky 。
样例输入 2
样例输出 2
数据规模
对于30%的测试点,保证a,x≤100,N≤100。
对于60%的测试点,保证a,x≤106。
对于所有测试点,保证a≤1000001;保证N≤2×105;保证1≤x≤1000001。
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <string>
using namespace std;
const int N = 1001 * 1001;
const double eps = 1e-8;
bool is_lucky[N + 5];
int next_lucky[N + 5];
void init() {}
int main() {
int a, T;
scanf("%d%d", &a, &T);
for (int i = 1; i <= N; i++) {
int t = int(sqrt(i) + eps);
if (i >= a && t * t == i)
is_lucky[i] = 1;
if (!is_lucky[i])
continue;
for (int j = i + i; j <= N; j += i)
is_lucky[j] = 1;
}
for (int i = N; i; i--)
next_lucky[i] = is_lucky[i] ? i : next_lucky[i + 1];
while (T--) {
int x;
scanf("%d", &x);
if (is_lucky[x])
cout << "lucky" << endl;
else
cout << next_lucky[x] << endl;
}
return 0;
}烹饪问题
时间限制:1.0 s
内存限制:128.0 MB
问题描述
有N种食材,编号从0至N-1,其中第 种食材的美味度为 。
不同食材之间的组合可能产生奇妙的化学反应。具体来说,如果两种食材的美味度分别为x和y,那么它们的契合度为x and y。
其中,and运算为按位与运算,需要先将两个运算数转换为二进制,然后在高位补足0,再逐位进行与运算。例如,12与6的二进制表示分别为 1100 和 0110 ,将它们逐位进行与运算,得到 0100 ,转换为十进制得到4,因此。在 C++ 或 Python 中,可以直接使用 & 运算符表示与运算。
现在,请你找到契合度最高的两种食材,并输出它们的契合度。
输入描述
第一行一个整数N,表示食材的种数。
接下来一行N个用空格隔开的整数,依次为a0,…,aN-1,表示各种食材的美味度。
输出描述
输出一行一个整数,表示最高的契合度。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例解释 1
可以编号为1,2的食材之间的契合度为2 and 3=2,是所有食材两两之间最高的契合度。
样例输入 2
样例输出 2
样例解释 1
可以编号为3,4的食材之间的契合度为10 and 13=8,是所有食材两两之间最高的契合度。
数据规模
对于40%的测试点,保证N≤1000;
对于所有测试点,保证N≤106,0≤ai≤2147483647。
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
using namespace std;
const int MAX_N = int(1e6) + 100;
int a[MAX_N];
int sort(int l, int r, int k) {
while (l <= r) {
while ((l <= r) && (a[l] >> k & 1))
l++;
while ((l <= r) && (!(a[r] >> k & 1)))
r--;
if (l <= r)
swap(a[l++], a[r--]);
}
return r;
}
int main() {
int n, j, ans = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 31; i >= 0; i--)
if ((j = sort(1, n, i)) >= 2) {
ans = ans | 1 << i;
n = j;
}
printf("%d\n", ans);
return 0;
}