当前位置：首页 > ai >正文

2024年CSP-S认证 CCF信息学奥赛C++ 中小学提高组第一轮真题讲解完善程序题解析

ai 2025/8/25 5:56:00

2024 CCF认证第一轮（CSP-S）真题

三、完善程序题

第一题

合并序列。有两个长度为N的单调不降序列A和B，序列的每个元素都是小于10^9的非负整数。在A和B中各取一个数相加可以得到N^2个和，求其中第k小的和。上述参数满足N≤10^5和1≤K≤N^2。

#include <iostream>
using namespace std;const int maxn = 100005;int n;
long long k;
int a[maxn], b[maxn];int *upper_bound(int *a, int *an, int ai) {int l = 0, r = ( ① );while (l < r) {int mid = (l + r) >> 1;if (②) {r = mid;}else {l = mid + 1;}}return ( ③ );
}long long get_rank(int sum) {long long rank = 0;for (int i = 0; i < n; i++) {rank += upper_bound(b, b + n, sum - a[i]) - b;}return rank;
}int solve() {int l = 0, r =（ ④ ）;while (l < r) {int mid = ((long long)l + r) >> 1;if  ( ⑤ ） {l = mid + 1;}else {r = mid;}}return l;
}int main() {cin >> n >> k;for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++)cin >> b[i];cout << solve() << endl;return 0;
}

程序分析：此程序考查的点为二分知识，solve和upper_bound都是二分，结合get_rank中对upper_bound的调用，可以确定upper_bound的参数意义。

upper_bound函数：a是数组的开始地址，an是数组的结束地址，ai是要找的目标数字，返回值是找到的地址。所以这个函数实验的功能应该是用于在指定范围内查找大于目标值的第一个元素。

get_rank函数：是solve的二分里面check函数，参数sum，返回rank，实验的功能就是返回一个和的排名。for循环中是遍历a数组，在a数组中选出元素a[i]，而后看一下在b中有多少个元素与a[i]相加的结果都是小于等于sum的。所以get_rank求的是小于等于sum的数对的个数。

solve函数：是用二分查找求满足条件的最小值，题目要求的是第k小的和，在和小于等于mid的数对的个数为k个的前提下，当mid不断减小直到最小时，mid就是第k小的数对的和；所以条件就是get_rank(mid)>=k的时候，mid的最小值；而if条件是反面所以get_rank(mid)<k

单选题

①处应该填

A. an-a
B. an-a-1
C. ai
D. ai+1

答案：A

答案分析：从程序分析中可以得知此处应该是A

②处应该填

A. a[mid]>ai
B. a[mid]≥ai
C. a[mid]<ai
D. a[mid]≤ai

答案：A

答案分析：从程序分析中可以得知此处应该是A

③处应该填

A. a+l
B. a+l+1
C. a+1-1
D. an-1

答案：A

答案分析：从程序分析中可以得知此处应该是A

④处应该填

A. a[n-1]+b[n-1]
B. a[n]+b[n]
C. 2*maxn
D. maxn

答案：A

答案分析：从程序分析中可以得知此处应该是A

⑤处应该填

A. get_rank(mid)<k
B. get_rank(mid)≤k
C. get_rank(mid)>k
D. get_rank(mid)≥k

答案：A

答案分析：从程序分析中可以得知此处应该是A

第二题

次短路。已知有一个n个点m条边的有向图G，并且给定图中的两个点s和t，求次短路(长度严格大于最短路的最短路径)。如果不存在，输出一行“-1”。如果存在，输出两行，第一行表示次短路经的长度，第二行表示次短路的一个方案。

#include <cstdio>
#include <queue>
#include <utility>
#include <cstring>
using namespace std;const int maxn = 2e5 + 10, maxm = 1e6 + 10, inf = 522133279;int n, m, s, t;
int head[maxn], nxt[maxm], to[maxm], w[maxm], tot = 1;
int dis[maxn << 1], *dis2;
int pre[maxn << 1], *pre2;
bool vis[maxn << 1];void add(int a, int b, int c) {++tot;nxt[tot] = head[a];to[tot] = b;w[tot] = c;head[a] = tot;
}bool upd(int a, int b, int d, priority_queue<pair<int, int> > &q) {if (d >= dis[b])return false;if (b < n)  ( ① );q.push( ② );dis[b] = d;pre[b] = a;return true;
}void solve() {priority_queue<pair<int, int> >q;q.push(make_pair(0, s));memset(dis,  ( ③ ), sizeof(dis));memset(pre, -1, sizeof(pre));dis2 = dis + n;pre2 = pre + n;dis[s] = 0;while (!q.empty()) {int aa = q.top().second;q.pop();if (vis[aa])continue;vis[aa] = true;int a = aa % n;for (int e = head[a]; e; e = nxt[e]) {int b = to[e], c = w[e];if (aa < n) {if (!upd(a, b, dis[a] + c, q))( ④ );}else {upd(n + a, n + b, dis2[a] + c, q);}}}
}void out(int a) {if (a != s) {if (a < n)out(pre[a]);elseout( ⑤ );}printf("%d%c", a % n + 1, " \n"[a == n + t]);
}int main() {scanf("%d%d%d%d", &n, &m,&s,&t);s--, t--;for (int i = 0; i < m; i++) {int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a - 1, b - 1, c);}solve();if (dis2[t] == inf)puts("-1");else {printf("%d\n", dis2[t]);out(n + t);}return 0;
}

程序分析：此程序主要考查的知识点是图论、邻接表及最短路径相关知识，add是邻接表保存边，顶点编号从0开始，dis和pre数组开了两倍大小，dis2和pre2用的是dis和pre数组的空间，dis2[x]=dis[x+n]，pre2[x]=pre[x+n]。out是递归输出次短路。具体算法，还是dijkstra，除了要更新最短路，也要更新次短路。upd函数把两种更新合在一起写了。

Dijkstra算法是一种用于在加权图中找到单源最短路径的经典算法，该算法适用于边权值为非负的图，能够高效计算从起点到图中所有其他节点的最短路径。Dijkstra算法采用贪心策略，通过逐步扩展已知最短路径的节点集合来求解。算法维护两个集合：已确定最短路径的节点集合和未确定最短路径的节点集合。每次从未确定的集合中选择距离起点最近的节点，更新其邻居节点的距离值。

38.A，b<n，说明当前的upd更新的是最短路，且当前这条路比原先的最短路更好，所以要用原来的最短。

39.A，从make_pair(0,s)可以看到，second是节点编号，first是距离，priority_queue默认是大顶堆，所以要取负号(距离小的取负后变大，排在前面)

40.B，最后判断无解是dis2[t]==inf，inf是十进制的522133279，换算成十六进制是0x1F1F1F1F

41.A，aa<n，所以a=aa，dis[a]是最短路，upd(a,b,dis[a]+c,q)返回false，说明dis[a]+czb，所以要去更新一下次短路，b+n的位置存的是dis2[b]

42.A，次短路的上一跳存在pre2[a%n]里面，也可以写成pre[a]

单选题

①处应该填

A. udp(pre[b],n+b,dis[b],q)

B. upd(a,n+b,d,q)

C. upd(pre[b],b, dis[b].q)

D. upd(a,b,d,q)

答案：A

答案分析：从程序分析中可以得知此处应该是A

②处应该填

A. make_pair(-d,b)

B. make_pair(d,b)

C. make_pair(b,d)

D. make_pair(-b,d)