提高组初赛通过指南

MilkyCoffee · 2021-06-13 19:30:17 · 个人记录

计算机科学请移步：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 背包不可以使用贪心算法。