提高组初赛通过指南

MilkyCoffee

2021-06-13 19:30:17

Personal

计算机科学请移步：Link

这篇博文与计算机科学除知识点外的不同点：

博主更强了
废话更少了
考点更精了

在您阅读这篇文章之前，请您将计算机科学部分指南通读（不背也没有太大关系，据博主观察这种题虽然考的概率极高但是 60\% 均是常识，但是有些年份会有及其毒瘤的题目，比如考你非常偏僻的缩写是什么意思）。

待填坑，可能会投日报。

附：按照目前进度，可以考虑 7.10 之前更新完毕。

本文可以进行在原有内容上的创编与改造，但是必须附上原文链接。

正文：

CSP-S / NOIp 的初赛分两种题目，近几年来是 1 至 15 题为选择题，16 至 20 为其他题目，而后五道大题需要 OI 经验，在这方面能力欠佳的同学可以配合能力全面提升综合题单和 OI-wiki 进行知识的学习，在这里将会列举出选择题常考的知识点。

选择题：

数学类 / 数论
- 进制
  例题： ``` 请选出以下最大的数（） ``` `A.`$(550)_{10}$ `B.` $(777)_{8}$ `C.` $2^{10}$ `D.` $(22F)_{16}
  正确答案：C；解析：(550)_{10}=550,(777)_{8}=511,2^{10}=1024,(22F)_{16}=559
- 位运算
  
  详见 OI-wiki : Link
  
  例题：
```
二进制数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
- 中国剩余定理
  
  详见 OI-wiki : Link
  
  例题：
```
一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班的学生人数 n 在以下哪个区间？已知 n<60。（ ）
```
  A.30<n<40 B.40<n<50 C.50<n<60 D.20<n<30
  
  正确答案：C；解析：班级人数为 53 ，按照 CRT 的求解过程计算或者一眼秒出答案验算正确即可。
- 杂项-数学（简单）
  
  CSP 2020 提高组初赛第 11 题：计算即可。 CSP 2020 提高组初赛第 13 题：4 \times 4 \times 3 \times 3 \div 2 = 72
  
  CSP 2019 提高组初赛第 6 题：排列组合
无脑计算类
- 分辨率
  
  初赛时题目会给出 xx 位真彩色图像（也就是存储一个像素需要多少 bit）然后硬算即可。
  
  例题：
```
现有一段 8 分钟的视频文件，它的播放速度是每秒 24 帧图像，每帧图像是 一幅分辨率为 2048×1024像素的 32 位真彩色图像。请问要存储这段原始无压缩视频，需要多大的存储空间？（ ）。
```
  A. 30G B. 90G C. 150G D. 450G
  
  正确答案：C；解析：8*60*24*2048*1024*32/8/1024/1024/1024=90
- 基础语法类
  
  CSP 2019 提高组初赛第 1 题：运用存储数据类型的知识进行计算即可。
OI 类
- 数据结构
  - 栈
    
    具体算法参考 OI-wiki : Link
    
    例题：
```
今有一空栈 S，对下列待进栈的数据元素序列a,b,c,d,e,f依次进行：进栈，进栈，出栈，进栈，进栈，出栈的操作，则此操作完成后，栈底元素为（ ）。
```
    A.b B.a C.d D.c
    
    正确答案：B；解析：。
  - 哈希
    
    具体算法参考 OI-wiki : Link
    
    例题：
```
将(2, 7, 10, 18)分别存储到某个地址区间为 0~10 的哈希表中，如果哈希函数h(x)=（ ），将不会产生冲突，其中 a mod b 表示 a 除以 b 的余数。
```
    A. x^2\ mod\ 11 B. 2x\ mod\ 11 C. x mod 11 D. \llcorner x/2 \lrcorner mod 11
    
    正确答案：D；解析：挨个计算看结果是否冲突即可。
- 搜索
  - dfs（深度优先搜索）
    
    详见 OI-wiki ：Link
    
    无实际例题。
    
    正确答案：；解析：。
  - bfs（广度优先搜索）
    
    详见 OI-wiki ：Link
    
    例题：
```
广度优先搜索时，一定需要用到的数据结构是( )
```
    A.栈 B.二叉树 C.队列 D.哈希表
    
    正确答案：C；解析：。
  - 二叉搜索树
    
    这类题型往年没有考过，但是今年可能会考。
    
    详见 OI-wiki ：Link
- 图论
  - 构成
    
    连通无向图构成条件 : 边 = 顶点数 * (顶点数 - 1) / 2
    
    例题：
```
G是一个非连通无向图（没有重边和自环），共有28条边，则该图至少有 （）个顶点。
```
    A.10 B.9 C.11 D.8
    
    正确选项：B；解析：由上方的公式可得，边为 28 的联通无向图顶点数为 8 ，加上一个单独的点构成非联通无向图，顶点数为 9。
  - 存储方式
    
    设图具有 n 个点，m 条边。
    - 邻接表
      
      运用搜索遍历图：O(n+m)；空间复杂度：O(m)；查询是否存在由 u 发出的某条边：O(d^+(u))，二分优化后为 O(log(d^+(u)))；遍历点 u 的所有出边：O(d^+(u))
      
      应用：稀疏图或适用。
    - 邻接矩阵
      
      运用搜索遍历图：O(n^2)；空间复杂度：O(n^2)；查询是否存在某条边：O(1)；遍历一个点的所有出边：O(n)
      
      应用：稠密图。
    - 链式前向星
      
      运用搜索遍历图：O(n+m)；空间复杂度：O(m)；查询是否存在 u 发出的某条边：O(d^+(u))；遍历一个点的所有出边：O(d^+(u))
      
      应用：网络流或通用。
    例题：
```
具有 n 个顶点，e 条边的图采用邻接表存储结构，进行深度优先遍历运算的时间复杂度为（ ）。
```
    A. O(n+e) B. O(n^2) C. O(e^2) D. O(n)
    
    正确答案：A；解析：。
  - 最短路径
    - Floyd
      - 额外条件：无负环
      - 空间复杂度：O(n^2)
      - 时间复杂度：O(n^3)
      - 不属于贪心
    - Bellman-Ford
      - 额外条件：无负环
      - 空间复杂度：随存储方式而定
      - 时间复杂度：O(nm)
      - 不属于贪心
    - SPFA
      - 额外条件：无负环，Bellman-Ford 的优化
      - 空间复杂度：随存储方式而定
      - 时间复杂度：大多数情况下跑的很快，但是可以被网格图卡到 O(nm)
      - 不属于贪心
    - dijkstra
      - 额外条件：无负环
      - 空间复杂度：随存储方式而定
      - 时间复杂度：暴力是 O(n^2)，用堆 O(m\ log\ n)，用优先队列 O(m\ log\ m)，用 ZKW 线段树 O(m\ log\ n)，用 Fibonacci 堆 O(n\ log\ n + m)
      - 属于贪心
    例题：
```
对一个 n 个顶点、m 条边的带权有向简单图用 Dijkstra 算法计算单源最短路时，如果不使用堆或其它优先队列进行优化，则其时间复杂度为（ ）。
```
    A. O((m+n^2)log\ n) B. O(mn+n^3) C. O((m+n)log\ n) D. O(n^2)
    
    正确答案：D；解析：。
  - 二分图
    
    具体算法参考 OI-wiki : Link
    
    例题：
```
二分图是指能将顶点划分成两个部分，每一部分内的顶点间没有边相连的简单无向图。那么，24 个顶点的二分图至多有（ ）条边。
```
    A.144 B.100 C.48 D.122
    
    正确答案：A；解析：按照二分图的定义进行计算即可，12 \times 12 = 144
- 动态规划
  
  ~~具体请看 OI-wiki~~ 这部分的经验主要由练习题目等获得。
  
  例题（由于有图片就不直接写出来了）:https://ti.luogu.com.cn/problemset/1031 第十五题
  
  正确答案：A；解析：根据图片，显然。
- 排序
  
  选择、冒泡、插入排序的时间复杂度为 O(n^2)；计数排序的时间复杂度为 O(n+w)；基数排序的时间复杂度为 O(nk\ log\ n)，空间复杂度为 O(n+k)；快速排序的时间复杂度为 O(n\ log\ n) 至 O(n^2)；归并排序的时间复杂度为 O(n\ log\ n)，空间复杂度为 O(n)；一般认为桶排序的时间复杂度为 O(n)
  
  其中，选择、快速排序为不稳定的排序方式。
- 杂项
  
  注：这里收录一些不完全属于某种算法的题目与知识点。
  - 表达式求值
    
    具体请见 OI-wiki：Link，但因为 OI-wiki 描述的相当不清晰，下面进行简单的释义：
    - 前缀表达式：符号-数A-数B（波兰表达式）
    - 中缀表达式：数A-符号-数B
    - 后缀表达式：数A-数B-符号（逆波兰表达式）
    对于表达式转换的题目，可以依照算式优先级从优先级小的向优先级大的一次进行转换（例题解析帮助理解，是个人的方法，可能不是很科学）。
    
    例题：
```
表达式 a*(b+c)-d 的后缀表达形式为（ ）。
```
    A.abc*+d- B.-+*abcd C.abcd*+- D.abc+*d-
    
    正确答案：D；解析：如下
```
原式可化为：(a*(b+c))d- = a(b+c)*d- = abc+*d- ，所以选择 D 选项。
```
  - CSP 2020 提高组初始第六题：考察贪心的应用，即使你不知道 ACD 选项，也一定清楚 0-1 背包不可以使用贪心算法。