CSP-S1 2019 认证考试 题解

今年是 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是图像文件格式以外,其他三个都是视频文件格式。

  1. WMV(Windows Media Video)是微软开发的一系列视频编解码和其相关的视频编码格式的统称,是微软Windows媒体框架的一部分
  2. MPEG(Moving Picture Experts Group,动态图像专家组)是ISO(International Standardization Organization,国际标准化组织)与IEC(International Electrotechnical Commission,国际电工委员会)于1988年成立的专门针对运动图像和语音压缩制定国际标准的组织。
  3. JPEG(全称是Joint Photographic Experts Group)是常见的一种图像格式,它由联合照片专家组开发并命名为”ISO 10918-1″,JPEG仅仅是一种俗称而已。
  4. 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}$ 中某个数的路径,使得该路径上的数之和最大。

T15 image

令 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;
}
  • 判断题
    1. 第 16 行输出 ans 时,ans 的值一定大于 i。()
    2. 程序输出的 ans 小于等于 n。()
    3. 若将第 12 行的 < 改为 !=,程序输出的结果不会改变。()
    4. 当程序执行到第 16 行时,若 $\text{ans}-i>2$,则 $a _ {i+1}\leq a_i$。()
  • 选择题
    1. 若输入的 a 数组是一个严格单调递增的数列,此程序的时间复杂度是()
      • A. $O(\log n)$
      • B. $O(n^2)$
      • C. $O(n\log n)$
      • D. $O(n)$
    2. 最坏情况下,此程序的时间复杂度是()
      • A. $O(n^2)$
      • B. $O(\log n)$
      • C. $O(n)$
      • D. $O(n\log n)$

解析

答案:×√√√DA

这道题的代码意思是寻找第 $i$ 个位置右边第一个大于等于它的数字的下标。

  • 判断题
    1. ×
      反例数据:

       

      2
      1 2
      

    2. 显然,根据我们之前对题目的理解,这个下标不可能大于 n 。

    3. 既然 ansif 时已经设置为谷底(或其右边),那么后面的序列必然不下降,改成 != 没有影响

    4. 根据题目意思可得本题显然正确。
  • 选择题
    1. D
      扫一遍,$O(n)$。
    2. A
      单调下降子序列可以卡到 $O(n^2)$。

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;
}
  • 判断题
    1. 输入的 a 和 b 值应该在 [0, n-1] 的范围内。()
    2. 第 16 行改成 fa[i] = 0;,不影响程序运行结果。()
      3.若输入的 a 和 b 值均在[0, n-1] 的范围内,则对于任意 $0\leq i\leq n-1$,都有 $0\leq\text{fa}_i\leq n-1$。()
    3. 若输入的 a 和 b 值均在 [0, n-1] 的范围内,则对于任意 $0\leq i\leq n-1$,都有 $1\leq\text{cnt}_i\leq n$。()
  • 选择题
    1. 当 n 等于 50 时, 若 a, b 的值都在 [0, 49] 的范围内,且在第 25 行时 x 总是不等于 y ,那么输出为()
      • A. 1276
      • B. 1176
      • C. 1225
      • D. 1250
    2. 此程序的时间复杂度是()
      • A. $O(n)$
      • B. $O(\log n)$
      • C. $O(n^2)$
      • D. $O(n\log n)$

解析

答案:√×√×CC

有 $\text{BUG}$(合并不判父亲)的并查集,手动计算即可。

  • 判断题

    1. 这是一个并查集,根据初始化的操作范围 $[0,n-1]$,我们可以得出本题正确。
    2. ×
      并查集初始化错误。

    3. 并查集中父亲节点的编号肯定在节点编号范围 $[0,n-1]$ 内。
    4. ×
      反例数据:

       

      5
      1 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$。

    2. C
      本题的并查集没有使用优化(路径压缩或者按秩合并),所以时间复杂度为 $O(n^2)$。

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;
}
  1. ①处应填()
    • A. unlock[i] <= 0
    • B. unlock[i] >= 0
    • C. unlock[i] == 0
    • D. unlock[i] == -1
  2. ②处应填()
    • A. threshold[i] > points
    • B. threshold[i] >= points
    • C. points > threshold[i]
    • D. points >= threshold[i]
  3. ③处应填()
    • A. target = -1
    • B. –cnt[target]
    • C. bonus[target] = 0
    • D. points += bonus[target]
  4. ④处应填()
    • A. cnt[child[target][i]] -= 1
    • B. cnt[child[target][i]] = 0
    • C. unlock[child[target][i]] -= 1
    • D. unlock[child[target][i]] = 0
  5. ⑤处应填()
    • A. unlock[i] = cnt[i]
    • B. unlock[i] = m
    • C. unlock[i] = 0
    • D. unlock[i] = -1

解析

答案:CDDDB

本题显然这题是一个类似于拓扑排序的题目。
按题目要求 $\Theta(n^2)$ 模拟即可。

  1. C
    学习技能条件一,需要的前置技能数为 $0$ 且为学习。
  2. D
    学习技能条件二,总经验达到该技能的经验要求。
  3. D
    技能学习后总经验增加。
  4. D
    即使看不懂,也应该猜到是学完技能后,相关技能的前置条件减少。
  5. 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;
}
  1. ①处应填()
    • A. 0
    • B. ~0ull
    • C. ~0ull
    • D. 1
  2. ②处应填()
    • A. a[j] < i
    • B. a[ j ] == i
    • C. a[j] !=i
    • D. a[j]>1
  3. ③处应填()
    • A. trans |=1ull << (b[j] – 1)
    • B. status |=1ull << (b[j] – 1)
    • C. status +=1ull << (b[j] – 1)
    • D. trans +=1ull << (b[j] – 1)
  4. ④处应填()
    • A. ~status| trans
    • B. status & trans
    • C. status | trans
    • D. ~status & trans
  5. ⑤处应填()
    • A. trans =status | trans ^ win
    • B. status = trans >> 1 ^ win
    • C. trans =status ^ trans | win
    • D. status = status << 1 ^ win

解析

答案:CBADD

滚动的状态压缩动态规划+博弈论,我也不会。

  1. C
    根据题目要求,状态压缩到64位,A和D默认是32位整数,所以B或者C。最开始石子是0个,应该是输的状态,所以最低位不能是1,选C。
  2. B
    题目实现有将规则按a[i]进行从小到大排序,所以可使用规则只增加不减少。此循环用于增加当前可选的规则,当i达到a[j]时规则可以使用。
  3. A
    此行是用来在原有规则上,新增“取b[j]个棋子”的规则。二进制新增用 |
  4. D
    略。
  5. D
    略。