今年是 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;
}

判断题
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. √
  既然 ans 在 if 时已经设置为谷底（或其右边），那么后面的序列必然不下降，改成 != 没有影响
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;
}

①处应填（）
- 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
略。

单项选择题

1.

题目

解析

2.

题目

解析

3.

题目

解析

4.

题目

解析

5.

题目

解析

6.

题目

解析

7.

题目

解析

8.

题目

解析

9.

题目

解析

10.

题目

解析

11.

题目

解析

12.

题目

解析

13.

题目

解析

14.

题目

解析

15.

题目

解析

阅读程序

1.

题目

解析

2.

题目

解析

3.

题目

解析

完善程序题

1.

题目

解析

2.

题目

解析

发表评论 取消回复

发表评论取消回复