GESP-C++五级 题库
质数的判定和筛法的目的并不相同,质数判定旨在判断特定的正整数是否为质数,而质数筛法意在筛选出范围内的所有质数。
有一个存储了n个整数的线性表,分别用数组和单链表两种方式实现。在已知下标(或结点指针)的前提 下,数组的随机访问是O(1) , 而在链表中已知某结点的指针时,在该结点之后插入一个新结点的操作也是O(1)。
若数组 a 已按升序排列,则下面代码可以正确实现 “在 a 中查找第一个大于等于 x 的元素的位置”。
int lowerBound(vector<int>& a, int x){
int l=0, r=a.size();
while(l < r) {
int mid = (l + r) / 2;
if( a[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}快速排序只要每次都选取中间元素作为枢轴,就一定是稳定排序。
在一个数组中,如果两个元素 a[i] 和 a[j] 满足 i < j 且 a[i] > a[j] ,则 a[i] 和 a[j] 是一个逆 序对。
下面代码可以正确统计数组 a 区间 [l,r] 内的逆序对总数。
long long cnt=0;
void merge_count(vector<int>& a, int l, int m, int r){
int i = l, j = m + 1;
while(i <= m && j <= r) {
if(a[i] <= a[j]) i++;
else {
cnt += (m - i + 1);
j++;
}
}
}根据唯⼀分解定理,如果⼤于1的整数不能被任何不超其平⽅根的质数整除,那么n 必定是质数。
![]()
bool check(int n, int a[], int k, int dist) {
int cnt = 1;
int last = a[0];
for (int i = 1; i < n; i++) {
if (a[i] - last >= dist) {
cnt++;
last = a[i];
}
}
return cnt >= k;
}
int solve(int n, int a[], int k) {
std::sort(a, a + n);
int l = 0;
int r = a[n - 1] - a[0];
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(n, a, k, mid))
l = mid;
else
r = mid - 1;
}
return l;
}
int main() {
int a[] = {1, 2, 8, 4, 9};
int n = 5;
int k = 3;
std::cout << solve(n, a, k) << std::endl;
return 0;
}若一个问题满足最优子结构性质,则一定可以用贪心算法得到最优解。
线性筛相比埃氏筛的核心改进在于:埃氏筛中一个合数可能被多个质数重复标记,线性筛通过"每个合数只 被其最大质因子筛去"的策略,保证每个合数恰好被标记一次,从而实现 O(n)的时间复杂度。
任何递归程序都可以改写为等价的非递归程序,但改写后的非递归程序一定需要显式地使用栈来模拟递归 调用过程。
数字移动
时间限制: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;
}相等序列
时间限制: 1.0 s
内存限制:512.0 MB
题目描述
小 A 有一个包含 N 个正整数的序列A = {A1 , A2 , · · ,AN} 。小 A 每次可以花费 1 个金币执行以下任意一种操作:
选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai * P ,P 为任意质数;
选择序列中一个正整数 Ai ( 1 ≤ i ≤ N) ,将 Ai 变为 Ai /P ,P 为任意质数,要求Ai能被p整除。
小 A 想请你帮他计算出令序列中所有整数都相同 ,最少需要花费多少金币。
输入格式
第一行一个正整数N ,含义如题面所⽰ 。
第二行包含 N 个正整数 A1 , A2 , · … ,AN ,代表序列 A。
输出格式
输出一行 ,代表最少需要花费的金币数量。
输入样例
输出样例
数据范围
对于60%的测试点 ,保证 1 ≤ N, Ai ≤ 100 。
对于所有测试点 ,保证 1 ≤ N, Ai ≤ 105 。
#include <iostream>
using namespace std;
const int N = 100010;
int num[N][20];
int n, a[N];
void calc_prime_factor(int x)
{
for (int i = 2; i * i <= x; i++)
{
if (x % i == 0)
{
int cnt = 0;
while (x % i == 0)
{
x /= i;
cnt++;
}
num[i][cnt]++;
}
}
if (x > 1)
{
num[x][1]++;
}
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
calc_prime_factor(a[i]);
}
long long ans = 0;
for (int i = 2; i < 100001; i++)
{
int pos = 0;
for (int j = 0; j < 20; j++)
{
pos += num[i][j];
}
num[i][0] = n - pos;
int median_exponent = 0;
pos = 0;
for (int j = 0; j < 20; j++)
{
pos += num[i][j];
if (pos * 2 >= n)
{
median_exponent = j;
break;
}
}
for (int j = 0; j < 20; j++)
{
ans += num[i][j] * abs(j - median_exponent);
}
}
printf("%lld\n", ans);
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;
}奖品兑换
时间限制: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;
}