今年是 2019 年,我于 2019 年 10 月 19 日 星期六 9:30 至 11:30 参加了 CSP-S1 2019 认证考试。
这次考试涉及的知识点范围比较广,但题目难度比较简单,得分比较容易,所以大多数人都能拿到 90 分以上,更有甚者可以轻轻松松拿到满分,但我比较菜,只有八十几分。
2019年10月19日,CSP-S1 2019 于 9:30 ~ 11:30 举行。
我提早一个小时到达考场外,经过漫长的等待后,终于于八点四十五左右被允许入场,然后花费了将近二十分钟才在教学楼的顶层找到了考场(为什么会在顶层啊。。。),随后休息一会,开始考试。
今年的题型与以往不同,全是选择题与判断题,考前预计这场认证考试全省分数线会有所上升(然而并没有上升,还跌到了 1 分),因为卷子更简单。
考试的时候,感觉前面的题目非常简单,尤其是单项选择题,根本没有难题。
但是后面的题目就显得比较毒瘤了。
一个看不懂目的的程序、一个有 $ \text{BUG} $ 的并查集,还有一个前后缀字符串长度为零无法读入的问题。
当然,这些我都注意到了,并巧妙地避开了。然而,我还是错了。太尴尬了。
最后的完善程序题大题有两小题,第一题比较简单,全对,但第二题太难了,我根本没有看懂。
$$ \color{grey}{\text{最后我还奇迹般地考了全校(某不知名弱校)第一??}} $$
单项选择题
1.
题目
若有定义:int a=7; float x=2.5, y=4.7;
则表达式 x+a%3*(int)(x+y)%2
的值是:()
- A. 0.000000
- B. 2.750000
- C. 2.500000
- D. 3.500000
解析
答案:D
代入计算即可,注意运算优先级(*
,/
,%
的运算优先级相同,从左往右算)。
x+a%3(int)(x+y)%2
=2.5+7%3(int)(2.5+4.7)%2
=2.5+7%3(int)(7.2)%2
=2.5+17%2
=2.5+1
=3.5
2.
题目
下列属于图像文件格式的有()
- A. WMV
- B. MPEG
- C. JPEG
- D. AVI
解析
答案:C
除了JPEG是图像文件格式以外,其他三个都是视频文件格式。
- WMV(Windows Media Video)是微软开发的一系列视频编解码和其相关的视频编码格式的统称,是微软Windows媒体框架的一部分
- MPEG(Moving Picture Experts Group,动态图像专家组)是ISO(International Standardization Organization,国际标准化组织)与IEC(International Electrotechnical Commission,国际电工委员会)于1988年成立的专门针对运动图像和语音压缩制定国际标准的组织。
- JPEG(全称是Joint Photographic Experts Group)是常见的一种图像格式,它由联合照片专家组开发并命名为”ISO 10918-1″,JPEG仅仅是一种俗称而已。
- AVI英文全称为Audio Video Interleaved,即音频视频交错格式,是微软公司于1992年11月推出、作为其Windows视频软件一部分的一种多媒体容器格式。
3.
题目
二进制数 11 1011 1001 0111 和 01 0110 1110 1011 进行逻辑或运算的结果是()
- A. 11 1111 1101 1111
- B. 11 1111 1111 1101
- C. 10 1111 1111 1111
- D. 11 1111 1111 1111
解析
答案:D
列竖式计算即可。
逻辑或的运算法则:
0 or 0 = 0, 0 or 1 = 1, 1 or 0 = 1, 1 or 1 = 1
4.
题目
编译器的功能是()
- A. 将源程序重新组合
- B. 将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)
- C. 将低级语言翻译成高级语言
- D. 将一种编程语言翻译成自然语言
解析
答案:B
编译器的功能是将一种语言(通常是高级语言)翻译成另一种语言(通常是低级语言)。
5.
题目
设变量 x 为 float 型且已赋值,则以下语句能将 x 中的数组保留到小数点后两位,并将第三位四舍五入的是()
- A. x=(x*100+0.5)/100.0;
- B. x=(int)(x*100+0.5)/100.0;
- C. x=(x/100+0.5)*100.0;
- D. x=x*100+0.5/100.0
解析
答案:B
个人经验,考场上可以代入数值手动计算验证。
6.
题目
由数字 1, 1, 2, 4, 8, 8 所组成的不同的 4 位数的个数是()
- A. 104
- B. 102
- C. 98
- D. 100
解析
答案:B
首先介绍一下有重复元素的排列公式:
$$P=\frac{\sum^n_1c_i}{c_1!c_2!\cdots c_n!}$$
那么,我们可以将四位数分为如下情形:
- 含 2, 4, 1, 8:答案为 $4!=24$
- 含 2, 4, 1, 1:答案为 $\frac{4!}{2!}=12$
- 含 2, 4, 8, 8:答案为 $\frac{4!}{2!}=12$
- 含 1, 1, 2, 8:答案为 $\frac{4!}{2!}=12$
- 含 1, 1, 4, 8:答案为 $\frac{4!}{2!}=12$
- 含 8, 8, 2, 1:答案为 $\frac{4!}{2!}=12$
- 含 8, 8, 4, 1:答案为 $\frac{4!}{2!}=12$
- 含 1, 1, 8, 8:答案为 $\frac{4!}{2!\times 2!}=6$
所以答案为 $24+12\times 6+6=102$。
7.
题目
排序的算法很多,若按排序的稳定性和不稳定性分类,则()是不稳定排序。
- A. 冒泡排序
- B. 直接插入排序
- C. 快速排序
- D. 归并排序
解析
答案:C
上述四项除了快速排序是不稳定排序,其他三项都是稳定排序。
- 假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,$r_i=r_j$,且 $r_i$ 在 $ r_j$ 之前,而在排序后的序列中,$r_i$ 仍在 $r_j$ 之前,则称这种排序算法是稳定的;否则称为不稳定的。
- 堆排序、快速排序、希尔排序、直接选择排序是不稳定的排序算法;
- 基数排序、冒泡排序、直接插入排序、折半插入排序、归并排序是稳定的排序算法。
8.
题目
G 是一个非连通无向图(没有重边和自环),共有 28 条边,则该图至少有()个顶点。
- A. 10
- B. 9
- C. 11
- D. 8
解析
答案:B
注意到,包含了 $8$ 个节点的无向完全图的边数为 $\frac{8\times (8-1)}{2}=28$ ,恰好等于题目中所给出的边数。
所以只要增加至少 $1$ 个顶点,就可以使得原图不连通。
9.
题目
一些数字可以颠倒过来看,例如 0, 1, 8 颠倒过来还是本身, 6 颠倒过来是 9 , 9 颠倒过来看是 6 ,其他数字颠倒过来都不构成数字。类似的,一些多位数也可以颠倒过来看,比如 106 颠倒过来是 901 。假设某个城市的车牌只有 5 位数字,每一位都可以取 0 到 9 。请问这个城市有多少个车牌倒过来恰好还是原来的车牌,并且车牌上的 5 位数能被 3 整除?()
- A. 40
- B. 25
- C. 30
- D. 20
解析
答案:B
由题目的提示可以知道,符合要求的车牌只可能包含 0, 1, 6, 8, 9 这五个数字,其中 6, 9 是比较特殊的。
那么我们考虑把车牌分成多种情况:
- 6 _ _ _ 9 / 9 _ _ _ 6
- _ 6 _ 9 _ / _ 9 _ 6 _
- 6 6 _ 9 9 / 9 9 _ 6 6
- 6 9 _ 6 9 / 9 6 _ 9 6
- 0 _ _ _ 0 / _ 0 _ 0 _
- 1 _ _ _ 1 / _ 1 _ 1 _
- 8 _ _ _ 8 / _ 8 _ 8 _
其中 _ 表示可填数。
枚举 0, 1, 8 构成的长度为 3 的回文串,按照对三取模的结果进行分类:
- mod 3 = 0
0 0 0
1 1 1
8 8 8 - mod 3 =1
0 1 0
1 8 1
8 0 8 - mod 3 = 2
0 8 0
1 0 1
8 1 8
那么我们分别得出之前所分各类的车牌数量:
- 6 _ _ _ 9 / 9 _ _ _ 6
3 - _ 6 _ 9 _ / _ 9 _ 6 _
3 - 6 6 _ 9 9 / 9 9 _ 6 6
1 - 6 9 _ 6 9 / 9 6 _ 9 6
1 - 0 _ _ _ 0 / _ 0 _ 0 _
3 - 1 _ _ _ 1 / _ 1 _ 1 _
3 - 8 _ _ _ 8 / _ 8 _ 8 _
3
所以答案为 $3\times 2+3\times 2+1\times 2+1\times 2+3+3+3=25$。
10.
题目
一次期末考试,某班有 15 人数学得满分,有 12 人语文得满分,并且有 4 人语、数都是满分,那么这个班至少有一门得满分的同学有多少人?()
- A. 23
- B. 21
- C. 20
- D. 22
解析
答案:A
容斥原理,答案为 $15+12-4=23$。
11.
题目
设 A 和 B 是两个长为 n 的有序数组,现在需要将 A 和 B 合并成一个拍好序的数组,请问任何以元素比较作为基本运算的归并算法,在最坏情况下至少要做多少次比较?()
- A. $n^2$
- B. $n\log n$
- C. $2n$
- D. $2n-1$
解析
答案:D
写出归并排序合并部分的 C++ 代码:
reg int i=l,j=mid+1,k=l; while(i<=mid&&j<=r){ if(a[i]<a[j]) temp[k++]=a[i++]; else temp[k++]=a[j++]; } while(i<=mid) temp[k++]=a[i++]; while(j<=r) temp[k++]=a[j++];
观察可以发现,最坏情况下,第一个 while
循环中比较次数最多,并且最后一定剩下一个元素无需比较,所以答案是 $2n-1$。
12.
题目
以下哪个结构可以用来储存图()
- A. 栈
- B. 二叉树
- C. 队列
- D. 邻接矩阵
解析
答案:D
常识性问题。
13.
题目
以下哪些算法不属于贪心算法?()
- A. Dijkstra 算法
- B. Floyd 算法
- C. Prim 算法
- D. Kruskal 算法
解析
答案:B
Floyd 算法的本质是动态规划,而其他的三种算法都利用的贪心的思想。
14.
题目
有一个等比数列,共有奇数项,其中第一项和最后一项分别是 2 和 118098 ,中间一项是 486 ,请问一下哪个数是可能的公比?()
- A. 5
- B. 3
- C. 4
- D. 2
解析
答案:B
经过计算可以得出
$$\frac{486}{2}=243=\frac{118098}{486}$$
而
$$243=3^{5}$$
15.
题目
有正实数构成的数字三角形排列式如图所示。第一行的数为 $a_{1,1}$;第二行的书从左到右依次为 $a_{2,1},a_{2,2}$,第 $n$ 行的数为 $a_{n,1},a_{n,2},\cdots,a_{n,n}$。从 $a_{1,1}$ 开始,每一行的数 $a_{i,j}$ 只有两条边可以分别通向下一行的两个数 $a_{i+1,j}$ 和 $a_{i+1,j+1}$。用动态规划算法找出一条从 $a_{1,1}$ 向下通到 $a_{n,1},a_{n,2},\cdots,a_{n,n}$ 中某个数的路径,使得该路径上的数之和最大。

令 C[i][j] 是从 $a_{1,1}$ 到 $a_{i,j}$ 的路径上的数的最大和,并且 C[i][0]=C[0][j]=0 ,则 C[i][j] =()
- A. $ \max { C[i-1][j-1], C[i-1][j] } + a _ {i, j} $
- B. $ C[i-1][j-1] + C[i-1][j] $
- C. $ \max { C[i-1][j-1], C[i-1][j] } + 1 $
- D. $ \max { C[i][j-1], C[i-1][j] } + a _ {i, j} $
解析
答案:A
这是 IOI 1999 数字三角形 的原题。
阅读程序
1.
题目
#include <cstdio> using namespace std; int n; int a[100]; int main() { scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); int ans = 1; for (int i = 1; i <= n; ++i){ if (i > 1 && a[i] < a[i - 1]) ans = i; while (ans < n && a[i] >= a[ans + 1]) ++ans; printf("%d\n", ans); } return 0; }
- 判断题
- 第 16 行输出 ans 时,ans 的值一定大于 i。()
- 程序输出的 ans 小于等于 n。()
- 若将第 12 行的
<
改为!=
,程序输出的结果不会改变。() - 当程序执行到第 16 行时,若 $\text{ans}-i>2$,则 $a _ {i+1}\leq a_i$。()
- 选择题
- 若输入的 a 数组是一个严格单调递增的数列,此程序的时间复杂度是()
- A. $O(\log n)$
- B. $O(n^2)$
- C. $O(n\log n)$
- D. $O(n)$
- 最坏情况下,此程序的时间复杂度是()
- A. $O(n^2)$
- B. $O(\log n)$
- C. $O(n)$
- D. $O(n\log n)$
- 若输入的 a 数组是一个严格单调递增的数列,此程序的时间复杂度是()
解析
答案:×√√√DA
这道题的代码意思是寻找第 $i$ 个位置右边第一个大于等于它的数字的下标。
- 判断题
- ×
反例数据:2 1 2
- √
显然,根据我们之前对题目的理解,这个下标不可能大于 n 。 - √
既然ans
在if
时已经设置为谷底(或其右边),那么后面的序列必然不下降,改成!=
没有影响 - √
根据题目意思可得本题显然正确。
- ×
- 选择题
- D
扫一遍,$O(n)$。 - A
单调下降子序列可以卡到 $O(n^2)$。
- D
2.
题目
#include <iostream> using namespace std; const int maxn = 1000; int n; int fa[maxn], cnt[maxn]; int getRoot(int v) { if (fa[v] == v) return v; return getRoot(fa[v]); } int main() { cin >> n; for (int i = 0; i < n; ++i) { fa[i] = i; cnt[i] = 1; } int ans = 0; for (int i = 0; i < n - 1; ++i) { int a, b, x, y; cin >> a >> b; x = getRoot(a); y = getRoot(b); ans += cnt[x] * cnt[y]; fa[x] = y; cnt[y] += cnt[x]; } cout << ans << endl; return 0; }
- 判断题
- 输入的 a 和 b 值应该在 [0, n-1] 的范围内。()
- 第 16 行改成
fa[i] = 0;
,不影响程序运行结果。()
3.若输入的 a 和 b 值均在[0, n-1] 的范围内,则对于任意 $0\leq i\leq n-1$,都有 $0\leq\text{fa}_i\leq n-1$。() - 若输入的 a 和 b 值均在 [0, n-1] 的范围内,则对于任意 $0\leq i\leq n-1$,都有 $1\leq\text{cnt}_i\leq n$。()
- 选择题
- 当 n 等于 50 时, 若 a, b 的值都在 [0, 49] 的范围内,且在第 25 行时 x 总是不等于 y ,那么输出为()
- A. 1276
- B. 1176
- C. 1225
- D. 1250
- 此程序的时间复杂度是()
- A. $O(n)$
- B. $O(\log n)$
- C. $O(n^2)$
- D. $O(n\log n)$
- 当 n 等于 50 时, 若 a, b 的值都在 [0, 49] 的范围内,且在第 25 行时 x 总是不等于 y ,那么输出为()
解析
答案:√×√×CC
有 $\text{BUG}$(合并不判父亲)的并查集,手动计算即可。
- 判断题
- √
这是一个并查集,根据初始化的操作范围 $[0,n-1]$,我们可以得出本题正确。 - ×
并查集初始化错误。 - √
并查集中父亲节点的编号肯定在节点编号范围 $[0,n-1]$ 内。 - ×
反例数据:5 1 1 1 1 1 1 1 1
- √
- 选择题
- C
根据我们考试技巧,我们构造一组方便计算的数据。50 1 2 2 3 3 4 ... 48 49
所以答案为 $\sum^n_{i=1}i=\frac{n\times(n-1)}{2}=1225$。
- C
本题的并查集没有使用优化(路径压缩或者按秩合并),所以时间复杂度为 $O(n^2)$。
- C
3.
题目
#include <iostream> #include <string> using namespace std; const int maxl = 202; string s, t; int pre[maxl], suf[maxl]; int main() { cin >> s >> t; int slen = s.length(), tlen = t.length(); for (int i = 0, j = 0; i < slen; ++i) { if (j < tlen && s[i] == t[j]) ++j; pre[i] = j; // t[0..j-1]是 s[0..i]的子序列 } for (int i = slen - 1, j = tlen - 1; i >=0; --i) { if (j >= 0 && s[i] == t[j]) --j; suf[i] = j; // t[j+1..tlen-1]是 s[i..slen-1]的子序列 } suf[slen] = tlen - 1; int ans = 0; for (int i = 0, j = 0, tmp = 0; i <= slen; ++i) { while (j <= slen && tmp >= suf[j] + 1) ++j; ans = max(ans, j - i - 1); tmp = pre[i]; } cout << ans << endl; return 0; }
解析
答案:√×××DC
这道题目是 CodeForces 原题,解析略。
完善程序题
1.
题目
(匠人的自我修养)一个匠人决定要学习 $n$ 个新技术。要想成功学习一个新技术,他不仅要拥有一定的经验值,而且还必须要先学会若干个相关的技术。学会一个新技术之后,他的经验值会增加一个对应的值。给定每个技术的学习条件和习得后获得的经验值,给定他已有的经验值,请问他最 多能学会多少个新技术。
输入第一行有两个数,分别为新技术个数 $n(1\leq n\leq 10^3)$,以及己有经验值 $(\leq 10^7)$。
接下来 $n$ 行。第 $i$ 行的两个正整数,分别表示学习第 $i$ 个技术所需的最低经验值 $(\leq 10^7)$,以及学会第 $i$ 个技术后可获得的经验值 $(\leq 10^7)$。
接下来 $n$ 行。第 $i$ 行的第一个数 $m_i(0\leq m_i\leq n-1)$ 表示第 $i$ 个技术的相关技术数量。紧跟着 $m$ 个两两不同的数,表示第 $i$ 个技术的相关技术编号。
输出最多能学会的新技术个数。
下面的程序以 $\Theta(n^2)$ 的时间复杂度完成这个问题,试补全程序。
#include<cstdio> using namespace std; const int maxn = 1001; int n; int cnt[maxn]; int child [maxn][maxn]; int unlock[maxn]; int threshold[maxn], bonus[maxn]; int points; bool find(){ int target = -1; for (int i = 1; i <= n; ++i) if(① && ②){ target = i; break; } if(target == -1) return false; unlock[target] = -1; ③ for (int i = 0; i < cnt[target]; ++i) ④ return true; } int main(){ scanf("%d%d", &n, &points); for (int i = 1; i <= n; ++i){ cnt[i] = 0; scanf("%d%d", &threshold[i], &bonus[i]); } for (int i = 1; i <= n; ++i){ int m; scanf("%d", &m); ⑤ for (int j = 0; j < m; ++j){ int fa; scanf("%d", &fa); child[fa][cnt[fa]] = i; ++cnt[fa]; } } int ans = 0; while(find()) ++ans; printf("%d\n", ans); return 0; }
- ①处应填()
- A. unlock[i] <= 0
- B. unlock[i] >= 0
- C. unlock[i] == 0
- D. unlock[i] == -1
- ②处应填()
- A. threshold[i] > points
- B. threshold[i] >= points
- C. points > threshold[i]
- D. points >= threshold[i]
- ③处应填()
- A. target = -1
- B. –cnt[target]
- C. bonus[target] = 0
- D. points += bonus[target]
- ④处应填()
- A. cnt[child[target][i]] -= 1
- B. cnt[child[target][i]] = 0
- C. unlock[child[target][i]] -= 1
- D. unlock[child[target][i]] = 0
- ⑤处应填()
- A. unlock[i] = cnt[i]
- B. unlock[i] = m
- C. unlock[i] = 0
- D. unlock[i] = -1
解析
答案:CDDDB
本题显然这题是一个类似于拓扑排序的题目。
按题目要求 $\Theta(n^2)$ 模拟即可。
- C
学习技能条件一,需要的前置技能数为 $0$ 且为学习。 - D
学习技能条件二,总经验达到该技能的经验要求。 - D
技能学习后总经验增加。 - D
即使看不懂,也应该猜到是学完技能后,相关技能的前置条件减少。 - B
定义每个技能学习需要的前置技能数。
2.
题目
(取石子) Alice 和 Bob 两个人在玩取石子游戏。他们制定了 $n$ 条取石子的规则,第 $i$ 条规则为:如果剩余石子的个数大于等于 $a_i$ 且大于等于 $b_i$ , 那么他们可以取走 $b_i$ 个石子。他们轮流取石子。如果轮到某个人取石子, 而他无法按照任何规则取走石子,那么他就输了。一开始石子有 $m$ 个。请问先取石子的人是否有必胜的方法?
输入第一行有两个正整数,分别为规则个数 $n(2\leq n\leq 63)$,以及石子个数 $m(m\leq 64)$。
接下来 $n$ 行。第 $i$ 行有两个正整数 $a_i$ 和 $b_i$。
$(1\leq a_i\leq 10^7,1\leq b_i\leq 64)$
如果先取石子的人必胜,那么输出 Win
,否则输出 Loss
。
试补全程序。
#include <cstdio> #include <algorithm> using namespace std; const int maxn = 64; int n, m; int a[maxn], b[maxn]; unsigned long long status, trans; bool win; int main(){ scanf("%d%d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d%d", &a[i], &b[i]); for(int i = 0; i < n; ++i) for(int j = i + 1; j < n; ++j) if (aa[i] > a[j]){ swap(a[i], a[j]); swap(b[i], b[j]); } status = ①; trans = 0; for(int i = 1, j = 0; i <= m; ++i){ while (j < n && ②){ ③; ++j; } win = ④; ⑤; } puts(win ? "Win" : "Loss"); return 0; }
- ①处应填()
- A. 0
- B. ~0ull
- C. ~0ull
- D. 1
- ②处应填()
- A. a[j] < i
- B. a[ j ] == i
- C. a[j] !=i
- D. a[j]>1
- ③处应填()
- A. trans |=1ull << (b[j] – 1)
- B. status |=1ull << (b[j] – 1)
- C. status +=1ull << (b[j] – 1)
- D. trans +=1ull << (b[j] – 1)
- ④处应填()
- A. ~status| trans
- B. status & trans
- C. status | trans
- D. ~status & trans
- ⑤处应填()
- A. trans =status | trans ^ win
- B. status = trans >> 1 ^ win
- C. trans =status ^ trans | win
- D. status = status << 1 ^ win
解析
答案:CBADD
滚动的状态压缩动态规划+博弈论,我也不会。
- C
根据题目要求,状态压缩到64位,A和D默认是32位整数,所以B或者C。最开始石子是0个,应该是输的状态,所以最低位不能是1,选C。 - B
题目实现有将规则按a[i]进行从小到大排序,所以可使用规则只增加不减少。此循环用于增加当前可选的规则,当i达到a[j]时规则可以使用。 - A
此行是用来在原有规则上,新增“取b[j]个棋子”的规则。二进制新增用|
。 - D
略。 - D
略。
近期评论