GESP-C++五级 题库
根据下面C++代码的注释,两个横线处应分别填入( )。

有关下面代码正确的是( )。

有关下面C++代码正确的是( )。

下面代码执行后的输出是( D )。

有关下面代码的说法正确的是( )。

基于下面定义的函数,通过判断 isDivisibleBy9(n) == isDigitSumDivisibleBy9(n) 代码可验算如果 一个数能被9整除,则它的各位数字之和能被9整除。

小杨有100元去超市买东西,每个商品有各自的价格,每种商品只能买1个,小杨的目标是买到最多数量的商品。小杨采用的策略是每次挑价格最低的商品买,这体现了分治思想。( )
分治法的核心是:
分解:将问题划分为若干 相互独立且结构相同 的子问题。
解决:递归解决子问题。
合并:将子问题的解合并为原问题的解。
小杨的策略是 每次选当前最便宜的商品,这种策略的本质是贪心算法。
不是分治,因为无问题分解,无子问题合并。
引入分治策略往往可以提升算法效率。一方面,分治策略减少了操作数量;另一方面,分治后有利于系统的并行优化。
分治算法的思想就是把问题划分成子问题,然后继续划分,知道子问题可以直接解决,然后合并子问题得到的结果,推得原问题的答案,分治提高了算法的效率,减少了操作数量。
在进行全国人口普查时,将其分解为对每个省市县乡来进行普查和统计。这是典型的分治策略。
分治策略的基本思想是将一个大问题分解为若干个小问题,然后分别解决这些小问题,最后将它们的解合并起来得到整体的解。在人口普查中,各个地区的普查可以看作是对小问题的解决,最后将各地的数据统计合并,得到全国的人口统计数据
在下面C++代码中,由于删除了变量 ptr ,因此 ptr 所对应的数据也随之删除,故执行下述代码时,将报错。
删除指针ptr并不会删除数据本身,只是释放了指针指向的动态内存
小杨在生日聚会时拿一块H*W的巧克力招待来的K个小朋友,保证每位小朋友至少能获得一块相同大小的巧克力。那么小杨想分出来最大边长的巧克力可以使用二分法。( )
小杨想写一个程序来算出正整数N有多少个因数,经过思考他写出了一个重复没有超过N/2次的循环就能够算出来了。( )(2023年12月C++五级)
数字移动
时间限制:1.0 s
内存限制:512.0 MB
题目描述

输入格式

输出格式
输出一行,代表满足要求的 的最小值。
输入样例
输出样例
数据范围

#include <iostream>
using namespace std;
const int N = 100010;
int a[N];
int b[N];
int pos;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int left = 1, right = 1e6, ans = 1e6;
while (left <= right) {
int mid = (left + right) / 2;
bool possible = true;
pos = 0;
for (int i = 0; i < n; i++) {
if (a[i] > mid) {
b[pos++] = a[i];
}
}
for (int i = 0; i < pos; i += 2) {
if (b[i] != b[i + 1]) {
possible = false;
break;
}
}
if (possible) {
ans = mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
cout << ans << endl;
return 0;
}数字选取


#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1e5 + 5;
int n, p[N], cnt, minp[N];
bool np[N], used[N];
int main() {
scanf("%d", &n);
// 欧拉筛,同时求最小质因子minp
for (int i = 2; i <= n; i++) {
if (!np[i]) {
p[++cnt] = i;
minp[i] = i;
}
for (int j = 1; j <= cnt && 1LL * i * p[j] <= n; j++) {
np[i * p[j]] = true;
minp[i * p[j]] = p[j];
if (i % p[j] == 0) break;
}
}
int k = n / 2;
int res = 0;
for (int i = k + 1; i <= n; i++) {
int prime = minp[i];
if (!used[prime]) {
used[prime] = true;
res++;
}
}
res += 1; // 选数字1
printf("%d\n", res);
return 0;
}有趣的数字和


#include <algorithm>
#include <cstdio>
#include <utility>
using namespace std;
int L, R;
long long ans;
pair<int, long long> cal2(int n, int p) {
if (n == 0) {
return {1 - p, 0};
}
if (n == 1) {
return {1, p};
}
return {(n + 1) / 2, 1LL * n * (n + 1) / 4};
}
pair<int, long long> cal(int n, int p) {
if (n <= 1) {
return cal2(n, p);
}
long long x = 1LL << (31 - __builtin_clz(n)); // ≤n的最大2的幂
auto left_part = cal2(x - 1, p);
auto right_part = cal(n - x, 1 - p);
return {
left_part.first + right_part.first,
left_part.second + right_part.second + x * right_part.first
};
}
int main() {
scanf("%d%d", &L, &R);
ans += cal(R, 1).second;
ans -= cal(L - 1, 1).second;
printf("%lld\n", ans);
return 0;
}
