2024年CCF非专业级别软件能力认证第一轮CSP_S/提高级
2024
第一轮
2025-06-17 16:06:49
52次
一、单选题
二、判断题
三、组合题
合并序列。有两个长度为N的单调不降序列A和B，序列的每个元素都是小于109的非负整数。在A和B中各取一个数相加可以得到N2个和，求其中第k小的和。上述参数满足N≤105和1≤K≤N2。
#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;
} (1)．②处应填（）
| A． a[mid]>ai |
B． a[mid]≥ai |
| C． a[mid]<ai |
D． a[mid]≤ai |
④处应填（）
| A． a[n-1]+b[n-1] |
B． a[n]+b[n] |
| C． 2*maxn |
D． maxn37. |
①处应填（）
| A． an-a |
B． an-a-1 |
| C． ai |
D． ai+1 |
③处应填（）
| A． a+l |
B． a+l+1 |
| C． a+l-1 |
D． an-l |
处应填（）
| A． get_rank(mid)<k |
B． get_rank(mid)≤k |
| C． get_rank(mid)>k |
D． get_rank(mid)≥k |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1000000 + 5;
const int P1 = 998244353, P2 = 1000000007;
const int B1 = 2, B2 = 31;
const int K1 = 0, K2 = 13;
typedef long long ll;
int n;
bool p[maxn];
int p1[maxn], p2[maxn];
struct H {
int h1, h2, l;
H(bool b = false) {
h1 = b + K1;
h2 = b + K2;
l = 1;
}
H operator + (const H &h)const {
H hh;
hh.l = l + h.l;
hh.h1 = (1ll * h1 * p1[h.l] + h.h1) % P1;
hh.h2 = (1ll * h2 * p2[h.l] + h.h2) % P2;
return hh;
}
bool operator == (const H &h)const {
return l == h.l && h1 == h.h1 && h2 == h.h2;
}
bool operator < (const H &h)const {
if (l != h.l) return l < h.l;
else if (h1 != h.h1) return h1 < h.h1;
else return h2 < h.h2;
}
} h[maxn];
void init() {
memset(p, 1, sizeof(p));
p[0] = p[1] = false;
p1[0] = p2[0] = 1;
for (int i = 1; i <= n; i++) {
p1[i] = (1ll * B1 * p1[i - 1]) % P1;
p2[i] = (1ll * B2 * p2[i - 1]) % P2;
if (!p[i]) continue;
for (int j = 2 * i; j <= n; j += i) {
p[j] = false;
}
}
}
int solve() {
for (int i = n; i; i--) {
h[i] = H(p[i]);
if (2 * i + 1 <= n) {
h[i] = h[2 * i] + h[i] + h[2 * i + 1];
}
else if (2 * i <= n) {
h[i] = h[2 * i] + h[i];
}
}
cout << h[1].h1 << endl;
sort(h + 1, h + n + 1);
int m = unique(h + 1, h + n + 1) - (h + 1);
return m;
}
int main() {
cin >> n;
init();
cout << solve() << endl;
} (1)．若修改常数B1或K1的值，该程序可能会输出不同的结果（）
| A．正确 | B．错误 |
时间开销的瓶颈是init()函数（）
| A．正确 | B．错误 |
在solve()函数种，h[]的合并顺序可以看作是（）
| A． 二叉树的BFS序 |
B． 二叉树的先序遍历 |
| C． 二叉树的中序遍历 |
D． 二叉树的后序遍历 |
输入“10”，输出的第一行是（ ）？
| A． 83 |
B． 424 |
| C． 54 |
D． 110101000 |
假设程序运行前能自动将maxn改为n+1，所实现的算法的时间复杂度是O(nlogn)（）
| A．正确 | B．错误 |
输入“16”，输出的第二行是（）？
| A． 7 |
B． 9 |
| C． 10 |
D． 12 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
#include <iostream>
#include <string>
using namespace std;
const int P = 998244353, N = 1e4 + 10, M = 20;
int n, m;
string s;
int dp[1 << M];
int solve() {
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = (1 << (m - 1)) - 1; j >= 0; j--) {
int k = (j << 1) | (s[i] - '0');
if (j != 0 || s[i] == '1')
dp[k] = (dp[k] + dp[j]) % P;
}
}
int ans = 0;
for (int i = 0; i < (1 << m); i++) {
ans = (ans + 1ll * i * dp[i]) % P;
}
return ans;
}
int solve2() {
int ans = 0;
for (int i = 0; i < (1 << n); i++) {
int cnt = 0;
int num = 0;
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
num = num * 2 + (s[j] - '0');
cnt++;
}
}
if (cnt <= m) (ans += num) %= P;
}
return ans;
}
int main() {
cin >> n >> m;
cin >> s;
if (n <= 20) {
cout << solve2() << endl;
}
cout << solve() << endl;
return 0;
}当n=10且m=10时，有多少种输入使得两行的结果完全一致？（）
| A． 1024 |
B． 11 |
| C． 10 |
D． 0 |
输入“11 2 10000000001”时，程序输出两个数32和23（）
| A．正确 | B．错误 |
假设输入的s是包含n个字符的01串，函数solve()所实现的算法时间复杂度是O(n*2m)（）
| A．正确 | B．错误 |
若n=8，m=8，solve和solve2的返回值的最大可能的差值为（）？
| A． 1477 |
B． 1995 |
| C． 2059 |
D． 2187 |
在n≤10时，solve()的返回值始终小于410（）
| A．正确 | B．错误 |
当n≤5时，solve()的最大可能返回值为（）？
| A． 65 |
B． 211 |
| C． 665 |
D． 2059 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
阅读程序
#include <iostream>
using namespace std;
const int N = 1000;
int c[N];
int logic(int x, int y) {
return (x & y) ^ ((x ^ y) | (~x & y));
}
void generate(int a, int b, int *c) {
for (int i = 0; i < b; i++) {
c[i] = logic(a, i) % (b + 1);
}
}
void recursion(int depth, int *arr, int size) {
if (depth <= 0 || size <= 1) return;
int pivot = arr[0];
int i = 0, j = size - 1;
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++; j--;
}
}
recursion(depth - 1, arr, j + 1);
recursion(depth - 1, arr + i, size - i);
}
int main() {
int a, b, d;
cin >> a >> b >> d;
generate(a, b, c);
recursion(d, c, b);
for (int i = 0; i < b; i++) cout << c[i] << " ";
} (1)．假设数组c长度无限制，该程序所实现的算法的时间复杂度是O(b)的（ ）
| A．正确 | B．错误 |
当1000≥d≥b时，输出的序列是有序的（）
| A．正确 | B．错误 |
当输入“5 5 1”时，输出为“1 1 5 5 5”（ ）
| A．正确 | B．错误 |
函数int logic(int x,int y)的功能是（）？
| A． 按位与 |
B． 按位或 |
| C． 按位异或 |
D． 以上都不是 |
当输入为“10 100 100”时，输出的第100个数是（）？
| A． 91 |
B． 94 |
| C． 95 |
D． 98 |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
次短路。已知有一个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]);
else
out( ⑤ );
}
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;
} (1)．⑤处应填（）
| A． pre2[a%n] |
B． pre[a%n] |
| C． pre2[a] |
D． pre[a%n]+1 |
④处应填（）
| A． upd(a,n+b,dis[a]+c,q) |
B． upd(n+a,n+b,dis2[a]+c.q) |
| C． upd(n+a,b,dis2[a]+c,q) |
D． upd(a,b,dis[a]+c,q) |
③处应填（）
| A． 0xff |
B． 0x1f |
| C． 0x3f |
D． 0x7f |
①处应填（）
| 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． make_pair(-d,b) |
B． make_pair(d,b) |
| C． make_pair(b,d) |
D． make_pair(-b,d) |
【知识点】 CCF非专业级别软件能力认证CSP-S/提高级
