开始疯狂刷题！！！ 我要当榜一 我要刷到第十名

𝕿𝖍𝖆𝖙'𝖘 𝖔𝖋𝖈𝖔𝖚𝖗𝖘𝖊!

（做CSP-J/S组模拟题的往下划）

答案之书说：请不要点这里！！！

UID: 508, 注册于 1 年前, 最后登录于 0.0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001 毫秒后, 最后活动于 -1 秒前.

解决了 121 兆道题目，RP: 203.37亿万 (No. 1-10)

2024年 CSP-J/S 组模拟题

声明：本次模拟题的所有题目均由 @Farewell_bye 独自制作，不得盗用。

难度 $>$ CSP-J 且 $\le$ CSP-S

测试代码（Dev-C++）：

#include<iostream>
#include<windows.h>
#include<conio.h>
using namespace std;
char user[44];
double score=0;
char answer[44]={'X',('B','B','B','A','D','C','A','D','B','A','D','A','C','A','B'),('A','B','B','C','C'),('A','A','B','A','A','B','C'),('B','A','B','C','A','B'),('A','C','B','B','D','A','B','D','D','A')}; 
int main(){
	cout<<"2024年 CSP-J/S 组模拟题\n";
	cout<<"声明：本次模拟题的所有题目均由 @Farewell_bye 独自制作，不得盗用。\n";
	cout<<"难度 > CSP-J 且 ≤ CSP-S\n";
	cout<<"按任意键开始做题...\n";
	getch();
	system("cls");
	cout<<"请先按任意键查看题目，并在下方输入答案（换行确定答案，输入Z重新查看题目）：\n";
	getch();
	for(int c=1;c<=43;c++){
		cout<<c<<'.';	
		test:
		system("start http://183.237.11.102:5208/d/qyyzjtx2024/user/508");
		cin>>user[c];
		if(user[c]=='Z') goto test;
		else if(user[c]==answer[c]){
			if(c<=15) score+=2.0;
			else if(c<=18) score+=1.5;
			else if(c<=20) score+=3.0;
			else if(c<=25) score+=1.5;
			else if(c<=27) score+=3.0;
			else if(c<=29) score+=1.5;
			else if(c<=33) score+=3.0;
			else{
				score+=3.0;
			}
		}
	} 
	cout<<"考试结束！您的得分是："<<score<<"/100\n等级为：";
	if(score>=90.0) cout<<"A+"; 
	else if(score>=80.0) cout<<"A"; 
	else if(score>=70.0) cout<<"B+"; 
	else if(score>=60.0) cout<<"B"; 
	else if(score>=50.0) cout<<"C+"; 
	else if(score>=40.0) cout<<"C"; 
	else if(score>=30.0) cout<<"D+"; 
	else if(score>=20.0) cout<<"D"; 
	else cout<<"不及格（太低了吧！！！）";
}

题目：

单项选择（每题 2 分，共 30 分）

1. 在 CSP 的考试中，以下物品不可以带入考场的是：

   A. 刻有“Farewell_bye”签名的衬衫。

   B. 出自“Farewell_bye”的空白笔记本。

   C. 可以使自己拥有充沛精力的巧克力。

   D. 只可以观看时间的手表。

2. 一个 U 盘有 $16MB$，内存最接近于：

   A. 有 $15MB$ 的 U 盘。

   B. 有 $16368KB$ 的 U 盘。

   C. 有 $167608322837B$ 的 U 盘。

   D. 有 $16.1MB$ 的 U 盘。

3. 现有一栈 $stk$，一栈 $kts$，那么模拟 $\{s,t\}$ 元素进出队列的操作是：

   A. $stk.push(s);stk.push(t);kts.push(stk.top());stk.pop();stk.pop();kts.pop();$

   B. $stk.push(s);kts.push(stk.top());stk.pop();stk.push(t);kts.push(stk.top());stk.pop();$

   C. $stk.push(s);stk.push(t);kts.push(stk.top());stk.pop();stk.pop();kts.push(stk.top());kts.pop();$

   D. $stk.push(s);kts.push(t);kts.push(stk.top());stk.pop();stk.pop();kts.push(stk.top());kts.pop();$

4. 现有 $5$ 个A班人，$4$ 个B班人，和 $Farewell\_bye$ 站在一起拍照，但是 $Farewell\_bye$ 必须和B班人站在一起，而且要站在B班人的最中间，请问共有多少种排法？

   A. $17280$

   B. $362880$

   C. $3628800$

   D. $181440$

5. 中序表达式 $a\times(b+c)+d-f\times g$ 的二叉树的深度是多少？（规定根节点的深度为 $1$）

   A. $2$

   B. $3$

   C. $4$

   D. $5$

6. 根据摩尔定律，单块集成电路的集成度是6年前的几倍？

   A. $3$

   B. $4.5$

   C. $16$

   D. $3.5$

7. 下面哪项不是链表所具有的？

   A. 插入元素时间复杂度 $O(N)$。

   B. 遍历 $i$ 位置的元素最坏情况时间复杂度 $O(N)$。

   C. 删除元素时间复杂度 $O(1)$。

   D. 事先不必估计存储空间。

8. 下列判断 $a\neq 0$ 的是：

   A. $a-1 == 0\ ?\ 1:0$。

   B. $a-1==0\ ?\ 0:1$。

   C. $a+1==1\ ?\ 1:0$。

   D. $a+1==1\ ?\ 0:1$。

9. 如果一个无向图有 $\log2^n$ 个顶点，那么它最少有多少条边？

   A. $n-2$。

   B. $n-1$。

   C. $n$。

   D. $n+1$。

10. 下面这段代码等价于：

int ans = 0, n;
	cin>>n;
	for(int i = (int)log2(2^n); i <= (int)log2((2*(2^n-1)+2)*0.5); i++) {
  		ans++;
	}

$\ \ \ \ \$A. $ans=1$;

$\ \ \ \ \$B. $ans=(int)log2(2^n)$;

$\ \ \ \ \$C. $ans=(int)log2((2*(2^n-1)+2)*0.5$;

$\ \ \ \ \$D. $ans=((int)log2(2^n)+(int)log2((2*(2^n-1)+2)*0.5)*((int)log2(n))/2$;

11. 字符串 $S$ $\{Farewell\_bye\}$ 有多少个不同的子串？

    A. $75$。

    B. $32$。

    C. $40$。

    D. $76$。

12. 冯·诺依曼的主要贡献是：

    A. 提出存储程序原理，并设计出 $EDVAC$。

    B. 提出理想计算机的数学模型。

    C. 设计出了晶体管计算机。

    D. 设计出了第一台微型机。

13. 三个苹果分给两个小朋友，但要满足以下规则：

• 苹果 $a$ 不能分给小朋友 $B$。

• 小朋友 $A$ 不能看到小朋友 $B$ 当前手中的苹果数量比他多。

• 小朋友 $B$ 要拿到苹果 $b$。

  则可以满足的分配顺序为：

  A. $b→A;c→B;a→A$。

  B. $a→A;c→B;b→A$。

  C. $a→A;b→B;c→A$。

  D. $b→B;a→A;c→A$。

14. 对于一棵二叉树，前序遍历为 abdfgkcehij，中序遍历为 bdfkgaijhec，则后序为：

    A. kgfdbjiheca。

    B. kgfdbijheca。

    C. kgfbdjiheca。

    D. kgfdbjiheac。

15. 拓扑排序的前提是：

    A. 有向图。

    B. 有向无环图。

    C. 有向无环连通图。

    D. 有向无环强连通图。

阅读程序（判断题大多 1.5 分，选择题大多 3 分）

一：$n$ 和 $m$ 都是 不超过 $10^6$ 的正整数。

#include <bits/stdc++.h>
using namespace std;
int f(int t) {
	if (t < 3) return 3 - t;
	if (t < 5) return 2 ^ t;
	if (t < 7) return t * t;
	if (t < 9) return t ^ 3;
	for (int i = t - 1; i >= 9; i -= 3) {
		f(i);
	}
}
int main() {
	int n, m, ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		ans += f(m-i); 
	}
	printf("%d", ans);
	return 0;
}

16. 本程序存在缺陷，一旦 $n$ 和 $m$ 超过 $60$ 左右，运行时间将会大于 1s。

    A. 正确 B. 错误

17. 当 $n$ 或 $m$ 至少有一个为 $0$ 时，输出总是 $0$。

    A. 正确 B. 错误

18. 当输入为 $2 \ 5$ 时，输出为 $24$。

    A. 正确 B. 错误

19. 当 $m > n+8$ 时，输出总为：

    A. $n+7$ B. $4\times n$ C. $8\times n$ D. $16 \times n$

20. 当输入为 $5\ 10$ 时，输出为：

    A. $924$ B. $42$ C. $84$ D. $168$

二：$n$ 是小于等于 $2000$ 的正整数，且 $n$ 为 $s$ 的长度。

#include <bits/stdc++.h>
using namespace std;
const int N = 2100;
int n, tot, T;
char s[N], t[N];
signed main() {
	scanf("%d\n%s", &n, s + 1);
	int l = 1, r = n;
	while (l <= r) {
		if (s[l] < s[r]) {
			t[++tot] = s[l];
			l++;
		} else if (s[l] > s[r]) {
			t[++tot] = s[r];
			r--;
		} else {
			int L = l, R = r;
			while (L <= R && s[L] == s[R]) {
				L++, R--;
			}
			if (L > R) {
				t[++tot] = s[l];
				l++;
			} else {
				if (s[L] < s[R]) {
					t[++tot] = s[l];
					l++;
				} else {
					t[++tot] = s[r];
					r--;
				}
			}
		}
	}
	for (int i = 1; i <= tot; i++) {
		printf("%c", t[i]);
		if (++T == 80) printf("\n");
		T %= 80;
	}
	return 0;
}

21. 程序执行的是一个每次可以从S的开头或者结尾取出一个字符，放到一个T字符串的尾部。输出字典序最小的T字符串，每80个字符换一行输出。

    A. 正确 B. 错误

22. （2分）当输入为 6 ACDBCB 的时候，输出为 ABCBCD。

    A. 正确 B. 错误

23. （2分）程序最坏情况下的时间复杂度是 $O(n\ \log\ n)$。

    A. 正确 B. 错误

24. 程序一定有输出。

    A. 正确 B. 错误

25. 程序的输出长度一定为 $n$。

    A. 正确 B.错误

26. 当输入为 6 123456 的时候，输出为：

    A. 654321 B. 123456 C. abcdef D. fedcba

27. 当输入为 10 a7dk23d7sd 时，输出为：

    A. s7d32kdd7a B. a7dk23d7sd C. a7ddk23d7s D. ds7d32kd7a

三：$n$ 保证是小于等于 $60$ 的正整数。

#include <bits/stdc++.h>
using namespace std;
int a[1000010], n, b[1000010];
const int mx = 10000;
void init() {
	for (int i = 1; i <= n; i++) {
		a[i] = b[i] = mx;
	}
	for (int i = 1; i <= n; i++) {
		int t = a[i] & 0x3f, s = b[i] & 0x3f;
		a[i] = a[i] | (t & i);
		b[i] = b[i] | (s & i);
		if (i < n) a[i] >>= i | b[i+1];
		else a[i] >>= i | b[1];
		if (i < n) b[i] >>= i | a[i+1];
		else b[i] >>= i | a[1];
		a[i] = a[i] << i / 5;
		b[i] = b[i] << i / 5;
	}
}
signed main() {
	cin >> n;
	init();
	cout << a[b[n]] + b[a[n]];
	return 0;
}

28. $a$ 数组和 $b$ 数组在一定的 $n$ 下可能全为 $10000$。

    A. 正确 B. 错误

29. $a$ 数组和 $b$ 数组在一定的 $n$ 下可能全为 $0$。

    A. 正确 B. 错误

30. 当输入为 $5$ 时，输出为：

    A. $10$ B. $0$ C. $15$ D. $12$

31. 当输入为 $59$ 时，输出为：

    A. $118$ B. $223$ C. $0$ D. $-1$

32. 当输入处于 $1$ 到 $3$ 之间，输出为：

    A. $0$ B. $1$ C. $2$ D. $3$

33. 当输入为 $33$ 时，$a_{33}$ 和 $b_{33}$ 的值分别为：

    A. $0\ 0$ B. $320000\ 320000$ C. $33\ 33$ D. $126359\ 126359$

完善程序（每题 3 分，共 30 分）

一：无形的墙

这是一座很老的山了，上面几乎寸草不生，但依旧有一户人家住在这里。

某一天，这里发生了奇怪的事情，从山的四周向中间出现了一道看不见的墙！而且还在不断缩小！！！现在你想知道是否有一种可能，能使你安全的离开。

假设是一个 $n \times n$ 的山区，一开始的隐形墙在第 $m$ 层（每几层代表从外向内数第几圈），你在 $(x,y)$ 的位置，隐形墙每秒向内缩两格，你每秒可以移动一格。当隐形墙缩小到正中心时（即只剩一格时），就会停止不动，然后消失。换种说法，当你和隐形墙共存到它消失，你就成功的活下来了。当然，如果你一开始就在隐形墙外面，那你当然活下来了。数据保证你不会在隐形墙中。

只能向上、下、左、右中的任意一个方向移动。

如果你和隐形墙同时收缩到中间一格，则你可以存活。如果收缩过程中跑到了隐形墙里面，那么属于失败。

现在想知道，你能否成功的活下来。

输入共一行，四个正整数 $n,m,x,y$，其中 $n$ 保证是奇数，四个正整数用空格隔开，意义如题目描述所示。$m$ 保证一定合法。而且每一步不能穿过隐形墙。

输出共一行，一个字符串，如果你能成功活下来就输出 Yes，否则就输出 No。

样例：

输入：9 1 4 4
输出：Yes

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y;
signed main() {
    scanf("%d%d%d%d", &n, &m, &x, &y);
    if (①) {
        printf("Yes");
        return 0;
    }
    int z = ②;
    int zou = ③;
    int suo = ④;
    if (⑤) {
        if (zou >= suo) printf("No");
        else printf("Yes");
        return 0;
    }
    if (zou > suo) printf("No");
    else printf("Yes");
    return 0;
}

34. ① 位置应该填：

    A. $(x < m\ ||\ x > (n - m + 1))\ ||\ (y < m\ ||\ y > (n - m + 1))$

    B. $x < 1\ ||\ y < 1\ ||\ x > m\ ||\ y>m$

    C. $x < n\ \&\&\ y < m\ \&\&\ x>=1\ \&\&\ y>=1$

    D. $(x < m\ ||\ x > (n - m + 1))\ ||\ (y < m\ ||\ y > (n - m + 1)\ ||\ x == y)$

35. ② 位置应该填：

    A. $n/ 2$

    B. $(n-1)/2$

    C. $(n+1)/2$

    D. $2^n/2$

36. ③ 的位置应该填：

    A. $abs(z - y) + abs(y - x)$

    B. $abs(z - x) + abs(z - y)$

    C. $abs(z - x) + abs(x - y)$

    D. $abs(z - x) + abs(z + x)$

37. ④ 的位置应该填：

    A. $(z - m) / 2$

    B. $(z - m + 1) / 2$

    C. $(z - m + 1)$

    D. $z - m$

38. ⑤ 的位置应该填：

    A. $(z - m)$

    B. $(z - m + 1) \& 1$

    C. $(z - m + 1)$

    D. $(z - m) \& 1$

二：星河万里

在一个宇宙中，有许多星系，在每个星系中，有许多星球， 在每个星球中，有许多物质，在每种物质中，有许多能量。

现在我们构造一个宇宙，使它有 $n$ 个星球，这些星球由于被神秘人控制，所以有奇特的能力：引力。

由于这个星球有许多引力，所以星球之间会发生碰撞，现在已知会发生 $k$ 次碰撞。每一次碰撞是第 $x$ 个和第 $y$ 个星球脱离了引力而成的。

现在给每个星球一个引力的定义，若当前为第 $i$ 个星球，则它的引力是 $g_i$。再定义每一个星球的排位，第 $i$ 个星球的排位是 $p_i$。

如果星球 $i$ 脱离了引力，则星球 $i$ 将会向着它的引力而去，若有星球在 $i$ 的引力的排位上，则会发生碰撞，碰撞之后所有被碰撞的星球会消失。如果没有星球在此排位上，则星球 $i$ 停留在此排位上。当一个星球停留在排位上时，它会失去引力，所以这种情况我们把它的引力定为它原本的排位，把它原来的排位变成它的引力，也就是它们的引力和排位会互换。

如果星球 $x$ 和星球 $y$ 会在一个位置发生碰撞，输出 YES 和发生碰撞的排位；如果不在一个位置，输出 NO 和它们分别会发生碰撞或停留的排位。不会有多个星球排位相同，但引力可能相同。如果 $x$ 碰撞过后的位置会被 $y$ 经过，那么结果依然是 NO，且把 $y$ 的排位与引力互换。

第一行两个整数 $n$ 和 $k$，代表有 $n$ 个星球，$k$ 次脱离。

接下来 $n$ 行，每行两个整数 $g_i$ 和 $p_i$，分别代表星球 $i$ 的引力和排位。保证 $g_i \neq p_i$。

最后 $k$ 行，每行两个整数 $x$ 和 $y$，代表发生脱离的星球的排位。保证排位存在且 $x \neq y$，同时不出现 $x$ 撞上 $y$ 的情况。

输出共 $k$ 行，每行为一个字符串和一个整数，代表是否发生碰撞和最终移到的排位。

样例组：

输入1：
4 1
2 1
3 2
5 3
1 5
1 3
输出1：
NO 2 5

输入2：
5 1
1 2
3 4
5 6
10 8
10 9
8 9
输出2：
YES 10

由于本题目难度过大，所以增加注释。

#include <bits/stdc++.h>
using namespace std;
const int M = 101000;
int rea[M], yin[M];
int n, k;
int a, b;
signed main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &a, &b);
        /*1.1*/
        /*1.2*/;//有在 b 排位的星球
    }
    int x, y;
    while (k--) {
        scanf("%d%d", &x, &y);
        if (/*2.1*/) {
            if (/*2.2*/) {
                //由于 x 和 y 碰撞后不会再被脱离引力，因为它们已经不存在了，所以我们不需要在图中删除
                if (yin[x] == yin[y]) {
                    printf("YES %d\n", yin[x]);
                } else {
                    printf("NO %d %d\n", yin[x], yin[y]);
                }
            } else {//y 会停留在排位
                int YIN = yin[y];//y 的引力
                rea[YIN] = 1;//星球转移
                rea[y] = 0;//星球转移
                yin[YIN] = y;//引力转移
                //至此，y 的转移已全部完成
                if (yin[x] == YIN) {
                    printf("YES %d\n", yin[x]);
                } else {
                    printf("NO %d %d\n", yin[x], YIN);
                }
            }
        } else {//x 会停留在排位
            int YIN = yin[x];//x 的引力
            /*3.1*///星球转移
            /*3.2*///星球转移
           	 /*3.3*///引力转移
            //至此，x 的转移已全部完成
            if (rea[yin[y]]) {
                //由于 x 和 y 碰撞后不会再被脱离引力，因为它们已经不存在了，所以我们不需要在图中删除
                if (YIN == yin[y]) {
                    printf("YES %d\n", YIN);
                } else {
                    printf("NO %d %d\n", YIN, yin[y]);
                }
            } else {//y 会停留在排位
                int YINy = yin[y];//y 的引力
                /*4.1*/;//星球转移
                /*4.2*/;//星球转移
                /*4.3*/;//引力转移
                //至此，y 的转移已全部完成
                if (YIN == YINy) {
                    printf("YES %d\n", YIN);
                } else {
                    printf("NO %d %d\n", /*5.1*/, /*5.2*/);
                }
            }
        }
    }
    return 0;
}

39. 1.1 和 1.2 分别填入：

    A. $yin[b] = a;$ 和 $rea[b] = 1;$

    B. $yin[a] = b;$ 和 $rea[b] = 1;$

    C. $yin[b] = b;$ 和 $rea[b] = 1;$

    D. $yin[b] = a;$ 和 $rea[a] = 1;$

40. 2.1 和 2.2 分别填入：

    A. $rea[x]$ 和 $rea[yin[y]]$

    B. $rea[yin[x]]$ 和 $rea[yin[y]]$

    C. $rea[yin[x]]$ 和 $rea[y]$

    D. $rea[x]$ 和 $rea[y]$

41. 3.1 、 3.2 和 3.3 分别填入：

    A. $rea[YIN] = 0;$ 、 $rea[x] = 0;$ 和 $yin[YIN] = y;$

    B. $rea[YIN] = 1;$ 、 $rea[x] = 1;$ 和 $yin[x] = YIN;$

    C. $rea[YIN] = 0;$ 、 $rea[x] = 1;$ 和 $yin[x] = YIN;$

    D. $rea[YIN] = 1;$ 、 $rea[x] = 0;$ 和 $yin[YIN] = x;$

42. 4.1 、 4.2 和 4.3 分别填入：

    A. $rea[YINy] = 0;$ 、 $rea[y] = 0;$ 和 $yin[YINy] = y;$

    B. $rea[YINy] = 1;$ 、 $rea[y] = 1;$ 和 $yin[y] = YINy;$

    C. $rea[YINy] = 0;$ 、 $rea[y] = 1;$ 和 $yin[y] = YINy;$

    D. $rea[YINy] = 1;$ 、 $rea[y] = 0;$ 和 $yin[YINy] = y;$

43. 5.1 和 5.2 分别填入：

    A. $YIN$ 和 $YINy$

    B. $YINy$ 和 $YINy$

    C. $YIN$ 和 $YIN$

    D. $YINy$ 和 $YIN$

    所有题目到这就结束了，下面有个抛硬币的代码，用来解压：

#include<iostream>
#include<stdlib.h> 
#include<conio.h>
#include<ctime>
#include<iomanip>
#include<windows.h>
using namespace std;
int main(){
	srand(time(0));
	cout<<"模拟抛硬币系统\n";
	cout<<"按任意键开始模拟......\n";
	getch();
	unsigned long long on=0,off=0,all=0;
	system("cls");
	cout<<"请问按一下抛多少次（记得输入数字后换行）？";
	int x;
	cin>>x;
	system("cls");
	b:
	cout<<"抛硬币\n";
	for(int c=1;c<=x;c++){
		int a=rand()%2+1;
		if(a==1) off++;
		else on++;
		all++;
		long double on1=(on*1.0)/(all*1.0)*100.0,off1=(off*1.0)/(all*1.0)*100.0;
		cout<<"\r总次数："<<all<<"    正面次数："<<on<<"    反面次数："<<off<<"    正面概率："<<fixed<<setprecision(4)<<on1<<"%    反面概率："<<fixed<<setprecision(4)<<off1<<"%";
	}
	cout<<"\n\n按任意键继续抛"<<x<<"次";
	if(x==1) cout<<"，长按一直抛。"; 
	getch(); 
	system("cls");
	goto b;
}