2024CCF 提高级 CSP-S 初赛

分類：CSP-S 提高组
來源：https://lib.nbdp.net/paper/146.html

一、单选题（每题 2 分，共 30 分）查看答案

第 1 题在Linux 系统中，如果你想显示当前工作目录的路径，应该使用哪个命令？（）

A. pwd
B. cd
C. Ls
D. echo

答案： A. pwd

第 2 题假设一个长度为n 的整数数组中每个元素互不相同，且这个数组是无序的。要找到这个数组中最大元素的时间复杂度是多少？（）

A. O(n)
B. O(log n)
C. O(n log n)
D. O(1)

答案： A. O(n)

第 3 题在C++中，以下哪个函数调用会造成栈溢出？（）

A. int foo( return 0; )
B. Int bar( int x=1; return x)
C. Void baz() { int a[1000];baz();}
D. Void qux() {return;}

答案： C. Void baz() { int a[1000];baz();}

第 4 题在一场比赛中，有10 名选手参加，前三名将获得金银铜牌，若不允许并列，且每名选手只能获得一枚铜牌，则不同的颁奖方式共有多少种？（）

A. 120
B. 720
C. 504
D. 1000

答案： B. 720

第 5 题下面那个数据结构最适合实现先进先出（FIFO）的功能？（）

A. 栈
B. 队列
C. 线性表
D. 二叉搜索树

答案： B. 队列

第 6 题一直f(1) = 1,且对于n>=2 有f(n) = f(n -1) + f( n/2 ) ,则f(4)的值为：（）

A. 4
B. 5
C. 6
D. 7

答案： B. 5

第 7 题假设一个包含n 个顶点的无向图，且该图是欧拉图。一下关于该图的描述中哪一项不一定正确？（）

A. 所有顶点的度数均为偶数
B. 该图联通
C. 该图存在一个欧拉回路
D. 该图的边数是奇数

答案： D. 该图的边数是奇数

第 8 题对数组进行二分查找的过程中，以下哪个条件必须满足？（）

A. 数组必须是有序的
B. 数组必须是无序的
C. 数组长度必须是2 的幂
D. 数组中的元素必须是整数

答案： A. 数组必须是有序的

第 9 题考虑一个自然数n 以及一个模数m，你需要计算n 的逆元（即n 在模m 意义下的乘法逆元）。下列哪种算法最为合适？（）

A. 使用暴力方法依次尝试
B. 使用扩展欧几里得解法
C. 使用快速幂解法
D. 使用线性筛法

答案： B. 使用扩展欧几里得解法

第 10 题在设计一个哈希表时，为了减少冲突，需要使用适当的哈希函数和和冲突解决策略。已知某哈希表中有n 个键值对，表的装载因子为α（0<α≤1）。在使用开放地址法解决冲突的过程中，最坏情况下查找一个元素的时间复杂度为（）

A. O(1)
B. O(log n)
C. O (1/(1-α))
D. O(n)

答案： D. O(n)

第 11 题假设有一颗h 层的完全二叉树，该树最多包含多少个节点（）

答案： 1

A. $2^h-1$

答案： 1

B. $2^{h+1}-1$

答案： 1

C. $2^h$

答案： 1

D. $2^{h+1}$

第 12 题设有一个10 个顶点的完全图，每两个顶点之间都有一条边，有多少个长度为4 的环？（）

A. 120
B. 210
C. 630
D. 5040

答案： C. 630

第 13 题对于一个整数n，定义f(n)为n 的各个位数之和，问使f(f(x))=10 的最小自然数x 是多少？

A. 29
B. 199
C. 299
D. 399

答案： B. 199

第 14 题设有一个长度为n 的01 字符串，其中有k 个1，每次操作可以交换相邻两个字符。在最坏的情况下将这k 个1 移到字符串最右边所需要的交换次数是多少？（）

A. K
B. K*(k-1)/2
C. (n-k)*k
D. (2n-k-1)*k/2

答案： C. (n-k)*k

第 15 题如图是一张包含7 个顶点的有向图。如果要删除一些边，使得从节点1 到节点7 没有可行路径，且删除的边数最少，请问总共有多少种可行的删除边的集合？（）

A. 1
B. 2
C. 3
D. 4

答案： D. 4

二、判断题（每题 2 分，共 20 分）

第 16 题

#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] << " ";
}

判断题

第 16 题当1000>=d>=b 时，输出的序列是有序的（）

A.正确
B.错误

答案： A.正确

第 17 题当输入“5 5 1”时，输出为“1 1 5 5 5”（）

A.正确
B.错误

答案： 2

第 18 题假设数组c 长度无限制，该程序所实现的算法的时间复杂度是O(b)的（）

A.正确
B.错误

答案： 2

第 19 题函数int logic(int x,int y)的功能是（）

A. 按位与
B. 按位或
C. 按位异或
D. 以上都不是

答案： B. 按位或

第 20 题（4 分）当输入为“10 100 100”时，输出的第100 个数是（）

A. 91
B. 94
C. 95
D. 98

答案： C. 95

第 22 题

#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;
}

假设输入的 s 是包含 n 个 01 字符串，完成以下的判断题和单选题：

判断题

第 22 题假设输入的s 是包含n 个字符的01 串，函数solve()所实现的算法时间复杂度是O(n*2^m)。（）

A.正确
B.错误

答案： A.正确

第 23 题输入“11 2 10000000001”时，程序输出两个数32 和23.（）

A.正确
B.错误

答案： A.正确

第 24 题（2 分）在n≤10 时，solve()的返回值始终小于410（）

A.正确
B.错误

答案： 2

第 25 题当n=10 且m=10 时，有多少种输入使得两行的结果完全一致？（）

A. 1024
B. 11
C. 10
D. 0

答案： C. 10

第 26 题当n≤5 时，solve()的最大可能返回值为？（）

A. 65
B. 211
C. 665
D. 2059

答案： C. 665

第 27 题若n=8，m=8，solve 和solve2 的返回值的最大可能的差值为（）

A. 1477
B. 1995
C. 2059
D. 2187

答案： C. 2059

第 29 题

#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;
		elsereturn 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;
}

判断题

第 29 题假设程序运行前能自动将maxn 改为n+1，所实现的算法的时间复杂度是O(nlogn)。( )

A.正确
B.错误

答案： A.正确

第 30 题时间开销的瓶颈是init()函数（）

A.正确
B.错误

答案： 2

第 31 题若修改常数B1 或K1 的值，该程序可能会输出不同呢的结果（）

A.正确
B.错误

答案： A.正确

第 32 题在solve()函数种，h[]的合并顺序可以看作是：（）

A. 二叉树的BFS 序
B. 二叉树的先序遍历
C. 二叉树的中序遍历
D. 二叉树的后序遍历

答案： B. 二叉树的先序遍历

第 33 题输入“10”，输出的第一行是？（）

A. 83
B. 424
C. 54
D. 110101000

答案： A. 83

第 34 题 (4 分)输入“16”，输出的第二行是？（）

A. 7
B. 9
C. 10
D. 12

答案： C. 10

三、编程题（每题 25 分，共 50 分）

第 36 题（1）合并序列，有两个长度为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 = __(1)__ ;
	while (l < r) {
		int mid = (l + r) >> 1;
		if ( __(2)__ ) {
			r = mid;
		} else {
			l = mid + 1;
		}
	}
	return __(3)__;
}

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 = __(4)__ ;
	while (l < r) {
		int mid = ((long long)l + r) >> 1;
		if ( __(5)__ ) {
			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;
}

第 36 题 ⑴处应填( )。

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

答案： A. an-a

第 37 题 ⑵处应填( )。

答案： 1

ai" lay-filter="filter">

答案： 1

= ai" lay-filter="filter">

C. a[mid] < ai
D. a[mid] ≤ ai

答案： 1

第 38 题 ⑶处应填( )。

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

答案： A. a+l

第 39 题 ⑷处应填( )。

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

答案： A. a[n-1]+b[n-1]

第 40 题 ⑸处应填( )。

A. get_rank(mid) < k
B. get_rank(mid) ≤ k

答案： A. get_rank(mid) < k

k" lay-filter="filter">

答案： 1

= k" lay-filter="filter">

第 42 题（次短路）已知有一个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) __(1)__ ;
	q.push( __(2)__ );
	dis[b] = d;
	pre[b] = a;
	return true;
}
void solve() {
	priority_queue<pair<int, int> >q;
	q.push(make_pair(0, s));
	memset(dis, __(3)__ , 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))
					__(4)__
				} 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( __(5)__ );
	}
	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;
}

第 42 题 ⑴处应填( )。

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. udp(pre[b],n+b,dis[b],q)

第 43 题 ⑵处应填( )。

A. make_pair(-d,b)
B. make_pair(d,b)
C. make_pair(b,d)
D. make_pair(-b,d)

答案： A. make_pair(-d,b)

第 44 题 ⑶处应填( )。

A. 0xff
B. 0x1f
C. 0x3f
D. 0x7f

答案： B. 0x1f

第 45 题 ⑷处应填( )。

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. upd(a,n+b,dis[a]+c,q)

第 46 题 ⑸处应填( )。

A. pre2[a%n]
B. pre[a%n]
C. pre2[a]
D. pre[a%n]+1

答案： A. pre2[a%n]

2024CCF 提高级 CSP-S 初赛

Links to this page: