2022年CSP-S提高级初赛（第一轮）真题讲解

根据视频整理出的部分知识点。

欢迎纠错~

【如果可以的话，蒟蒻请求置顶】

1.Linix: ls（lst）查看当前目录的文件和子目录

cd(change...) 改变目录

cp（copy) 复制

2.time命令： user + sys 不一定= real,用户用秒表记录的是real时间

3.栈的基本操作，比较简单懒得写

4.快速排序：选择一个基本数x，把<x的放在左区间 >x的放右区间，继续分治 最坏复杂度n^2

归并排序：分（拆分子序列） + 治（排序），复杂度log2n

5.基数排序:按照数位一位一位排序（0-9的桶，先按个位放到桶里，然后再取出放回数组,接下来按照10位排序，以此类推...)

6.%X:16进制显示

7.完全二叉树：除了最后一层，其他层都满，最后一层左边是满的，右边可能不满（注意最后一层是满的也算是完全二叉树）

8.强连通图：有向图中，每个点之间都有路径能互相到达

9.欧拉路径：一条经过每个边一次的路径恰好一次的路径；

欧拉回路：一个回路是欧拉路径；

具有欧拉回路的图为欧拉图 简称E图

判断条件（见下图懒得写了）

具体做法：可以靠枚举得出规律，当然可以靠枚举直接推。

特例：n = 2 时答案是不成立的

（所以在用取值法排除答案时最好不要代入2）

10.有歧义，根据答案时8个人组一个队伍，但是也可以理解成8个人4个队。（****CCF）

知识点：乘法原理，比较简单

11.同样是乘法原理（2022数学题的难度比以前简直是天差地别）

12.哈希表：利用哈希函数确定地址遇到冲突可用线性探查（其实还有别的方法），即一直往后找找到空地址为止.

具体做法：

13.水题，没有太难的知识点，会算时间复杂度即可

14.水题，没有太难的知识点

15.递归函数的运算，两种方法：

16.程序思路：查找t在s的哪个位置（类似于find()）,但有优化：如图s = day, i = 0时，如果无法匹配，就看i = 3是什么，如果是“y"那么从i = 1查找，是”a"从i = 2查找...以此类推（具体见下图）

技巧：程序想不出来干嘛用时可以先看题目

17.大致思路：基数排序（类CSP-J 2019）(虽然这两货差别其实有点大...)

具体思路：k是进制，先确定有几位，然后基数排序

以十进制为例：

稳定的算法：归并排序，冒泡排序，插入排序，基数排序

桶排序：把数字分到桶里，再单独排序，最后得到有序数列

计数排序：统计每个数出现的次数，然后再排序（可以看成大小是1的桶）

18.考察负数除法求余：一般来说有两种情况，取决于编译器

对于Dev-c++，除数往绝对值小的那边取值：

如-22 / 5 = -4余-2， 22/-5 = -4余2

但在本题中其实哪种情况算出来的结果是一样的

注：(x / y) *y + x % y == x只要y!=0一定满足

19.难死我了根本不会

首先先模拟单序列二分（如图）

然后双序列二分: