csp初赛资料自用

惘闻文雀 · 2025-03-15 21:44:47 · 算法·理论

csp初赛知识点

计算机基础知识

1.*计算机的分类

• 按年代分类

  年代	实现方式
  1946 ~ 1958	电子管
  1959 ~ 1964	晶体管
  1965 ~ 1970	集成电路
  1971 ~ 至今	超大规模集成电路

  考试方法：计算机按实现方式分类，至今有四类（要简单了解是哪四类）。按年代顺序分别是电子管 - 晶体管 - 集成电路 - 超大规模集成电路。

• 按性能分类

  • 巨型机/超级计算机：用于科学研究，我国目前有银河和天河两类超级计算机。
  • 大型机/中型机：用于科研领域。
  • 小型机：用于服务器。
  • 微型机：民用的手机/电脑都是微型机。
  • 工作站：相当于微型机。

  超算 > 大/中型 > 小型 > 微型 = 工作站

  考试方法：计算机按性能分类，可以分成五类，具体五类简单了解即可。

2.**空间换算

• bit 代表 位，byte 代表 字节

• 1024 = 2^10（必须记住）
• 2^10 * 2^10 = 2^20 （从数学意义上10个2相乘再乘上10个2相乘相当于20个2相乘）

• 拓展知识点：在平时买U盘或者磁盘的时候，厂家给我们玩了一个文字游戏，用的不是1024进行换算而是1000，所以通常大小会比实际大小缩水 7% 左右。

  考试方法：

  1. 牢记bit和byte的换算
  2. 1024的二进制
  3. 2进制的乘法(用数学意义去理解)

3.**贡献人员

• 艾伦·图灵：计算机科学/人工智能之父，提出了计算机科学理论。图灵奖以他命名，称之为“计算机界的诺贝尔奖”
• 冯·诺依曼：现代计算机之父，提出了储存程序控制原理，可以理解为提出了组成一个计算机所需要的全部结构，至今为止几乎所有的计算机依然是冯诺依曼结构。
• 克劳德·香农：创造了信息论，提出了信息传递所需要的全部设备构造的系统。

4.*计算机的构成

• 计算机由五个部分构成（运算器，存储器，控制器，输入设备，输出设备），缺少前两个就无法正常使用计算机，这个组成结构称为冯诺依曼结构。
• CPU：计算机的中央处理器，由运算器+控制器+寄存器组成，电脑的大脑。
• 内存储器："内存"，内存空间分为两部分分别是RAM和ROM。
  • RAM：随机存取存储器，断电后数据会丢失
  • ROM：只读存储器，断电后数据不会丢失
  • 内存读写速度快，存储空间小
• 外存储器："外存"，位于电脑外部，断电后数据不会丢失，如硬盘，光盘，U盘都叫做外存。
  • 外存读写速度慢，存储空间大
• 输入设备：人想要给计算机传递信息所用到的设备，常用的输入数据包括键盘、鼠标、麦克风、摄像头等
• 输出设备：计算机想要给人传递信息所用到的设备，常有的输出设备包括显示器、音响、打印机等。

5.*关于CPU

• 断电后会保留ROM和外存的数据
• 访问速度上，寄存器 > 高速缓存 > 内存 > 外存

6.*文件扩展名

• 图像存储：jpg/jpeg/png/pic/bmp/gif/webp。
• 音频存储：mp3/wav。
• 视频存储：mp4/avi/mpeg/flv/rmvb/rpm。

7.**编程语言常识

• 机器语言：由0/1代码组成，计算机只能识别机器语言。
• 汇编语言：用符号去代表二进制数，可以用编译器编译为机器语言，非专业人士通常也不会学习。
• 高级语言：除了以上两种，现在几乎全部语言都是高级语言。
  • 按面向区分
  • 面向过程：C语言
  • 面向对象：C++，Java，python（除C语言以外的大部分语言，如果考试考到，只会考到C语言）
  • 按编译方式
  • 逐行编译：python，php
  • 全文编译：除了python和php的全部语言

8.*ASCII码

• 由于C++底层都是由01数字组成，所以C++中的字符需要由对应的数字，ASCII码就是字符与数字对应的规则。
• 考点：
  • 数字的范围：'0'~'9'，'0'对应48。
  • 大写字母范围：'A'~'Z'，'A'对应65。
  • 小写字母范围：'a'~'z'，'a'对应97。
  • ASCII码的范围是0 ~ 127一共128个字符
• 一定要对48，65，97要有一种敏感度，因为通常这几个会在程序阅读中，直接或者间接的考察字符ASCII问题

9.**机器数与真值

• 由于C++底层都是由01数字组成，所以C++中的数字也有对于的二进制数字，我们在考试中遇到关于机器数与真值的问题，通常都针对有符号整数。
• 有符号与无符号问题，有符号即有正数也有负数，无符号则只表示非负数
• 反码：对正数来说，反码就是原码；对负数来说，反码就是除符号位以外，原码全部取反(0和1互换)
• 补码：对正数来说，补码就是原码；对负数来说，补码就是反码+1

10.*逻辑运算

• 逻辑运算的结果只有真和否，如果要用数字表示结果则只有0和1(非0)，注意逻辑运算中任何非0的结果都会表示为1

• 逻辑非：单目运算符，逻辑取反，把真变成否，把否变成真

• 逻辑与：全真则真

• 逻辑或：全否则否

• 运算顺序：! > && > ||

• 补充：三目运算符本质上也是逻辑运算，需要强调一个点，三目运算符联立时是从右往左运算

• 补充：在部分题目中出现^和∨时，^是&&，∨是||

• 三目运算符

  • 表达式1 ? 表达式2 : 表达式3

  • 其中表达式1是逻辑运算，如果表达式1为真，执行表达式2，为否执行表达式3

  • 其中表达式2必须和表达式3是同种类型

  int t = (5 < 2 ? 1 : 5 > 2 ? 2 : 3);

11.*位运算

在位运算中，如果有负数参与运算要先把负数变成补码再进行运算。位运算本质上就是把两个数的补码进行位运算，所以结果也是补码。所以如果运算结果是正数则不用理会，但如果是负数则需要通过补码取原码。

• 按位取与：&，表示把两个数字转成二进制补码进行按位取与计算，如果位数不足则补0
• 按位取或：|，表示把两个数字转成二进制补码进行按位取或计算，如果位数不足则补0
• 按位取反：~，表示把数字转成二进制补码进行按位取反计算。
• 按位异或：^，表示把两个数字转成二进制补码进行按位异或计算，不同为1，相同为0

数据结构

1.*图论基本概念

1. 顶点/节点都统称为点
2. 点与点之间的连线都统称为边
   • 有向边：两个点之间的连线有方向，如a -> b，表示a能指向b，b不能指向a
   • 无向边：两个点之间的连线没有方向，如a - b，表示a能指向b，b也能指向a
     • 特别强调一点，在代码中，无向边相当于两个有向边。
3. 简单图：没有自环，没有重边的图。通常情况，涉及图论问题题目都默认是简单图
   • 自环：从一个点出发到达自己的边叫自环
   • 重边：从一个点出发到达另一个点的边的数量 > 1
4. 完全图：从每个点出发都能连接除自己以外的所有点，完全图的边的数量是固定的
   • 无向完全图边的数量是 n(n-1)/2，有向图则需要乘2
5. 连通图：可以直接/间接访问到所有的点，完全图一定是连通图，连通图不一定是完全图。
6. 环：一个点从自己出发，经过不重复的边最终访问到自己，过程中经过的所有路径组成一个环
   • 无向图中a - b，不能组成一个环
   • 有向图中a -> b 和 b -> a，可以组成一个环

2.**树

1. 无环且连通的图就是树。哪怕这个图形状怪异，都可以摆成树的形状
2. 根节点：最上层的一个点，一个树有且只有一个根节点。通常题目会规定一个根节点，默认是1作为根节点
   • 根节点没有父节点/父亲
   • 根节点的祖先集合是空
3. 深度：到根节点需要经过几条边，深度就是多少。一般题目会考察最大深度问题
4. 高度：对于这个树而言的最大深度
5. 叶子节点/叶节点：没有子节点/儿子的节点
6. 祖先：对于一个节点而言，他到根节点经过的每一个节点都是他的祖先
7. 子节点/儿子：对一个节点而言，与这个节点连接且深度比这个节点大1的节点
   • 二叉树有左儿子右儿子的区分，其他树没有顺序
8. 兄弟：两个或者多个点有同一个父节点/父亲称为兄弟
9. 后代：祖先的相反词，如果a是b的祖先，那么b就是a的后代
10. 子树：对于一个节点而言，他与他父亲/父节点断绝父子关系后，由他为根节点组成的树叫他的子树

3.***二叉树

遍历规则

1. 前/先序遍历，中序遍历，后序遍历：他的前中后讲的是根。如前序就是根在最前，也就是根左右
2. 可以通过前序+中序或者后序+中序得到二叉树。因为通过前序/后序可以找到根的位置，通过中序去确定左右
3. 满二叉树/完美二叉树：每一层只要存在则一定排满的二叉树。所有叶结点的深度均相同的二叉树
4. 完全二叉树：只要求按从上往下从左往右按顺序排列的二叉树
5. 完整二叉树：要么没有儿子，要么有两个儿子
   • 完整二叉树的节点数一定是奇数个

4.*栈

1. 先进后出
2. 用stack或者vector进行模拟
   • stack是栈的标准容器，但是用得比较少
   • vector可以完整的使用stack的所有功能，而且还能通过下标取值，比stack强大太多
3. vector由于是一个容器，模拟栈的时候要符合先进后出的逻辑，所以需要尾插
   • v.push_back()
   • v.pop_back()
   • v.empty()
   • v.size()
   • v.back()

5.*队列

1. 先进先出/头插尾出
2. 用queue进行模拟
3. queue是队列的标准容器
   • q.push()
   • q.pop()
   • q.empty()
   • q.size()
   • q.front()
4. 队列没有迭代器且不能通过下标访问

6.*链表

1. 可以使用 list 的数据结构，但是list在考试中不常见，一般考试仍然用结构体去模拟链表
2. 和数组的共同点就是都是存储相同类型数据
3. 区别点1
   • 链表：链式存储
   • 数组：顺序存储
4. 区别点2
   • 链表：增加/删除/插入元素很方便，但是查询元素很慢
   • 数组：无法直接增加/删除/插入元素，但是查询速度快
5. 考点：如何使用结构体模拟

7.***字符串问题

1. 字符串：表示一串连续的字符
2. 子串：字符串中任意个连续的字符组成的字符串
   • 题目中的子串如果没有强调非空，那么空串也算子串
   • 字符串本身也是自己的子串
   • 长度为n的字符串，最多有 (1 + n) x n / 2 + 1个字串，最少有n + 1个字串
3. ***字符串表达式的前中后缀
   • 前缀/后缀转中缀
     • 模拟一个栈
     • 从右往左/从左往右遇到数字则放入栈中，如果遇到符号就取出栈中最上面的两个元素进行计算，计算结果也放进去
     • 注意进行减法和除法时，被减数/被除数是栈顶元素
   • 中缀转前/后缀
     • 按运算顺序给表达式加上小括号，原本有小括号的不用操作
     • 把所有的符号放在括号左/右
     • 从外层到里层把括号打开

数学部分

1不是质数也不是合数

*最大公约数/最小公倍数

求法1：短除法

求法2：辗转相除法/欧几里得算法

仅用于求两个数最大公约数

取两个数字中大的作被除数，小的作除数，运算后，将除数再次作为被除数，余数作为除数，反复运算直到余数为0时，最后一次运算的除数就是两个数字的最大公约数

在比赛或考试中可以使用gcd(a, b)求最大公约数，a * b / gcd(a, b)求最小公倍数

**进制问题

10进制转n进制

方法：用10进制数除以n，后续不断用商继续除以n，直到商为0，把每次除法的余数都从右到左写出即是进制转换的结果

n进制转10进制

方法：各位相乘再相加，n进制的个位乘n的0次方 + n进制的十位乘n的1次方...得到的结果就是10进制数

除了2，8，16进制互转以外，其他进制互转都需要通过10进制作为媒介来转换

注意：16进制的前缀是0x/0X，8进制前缀是0，2进制前缀是0b/0B

排列组合

排列数：从n个元素中选出m个，并且排序

计算方式：A(n, m)表示从n开始乘，每次递减1，一共m个数字

表达方式：A(n, m) = n! / (n - m)!

组合数：从n个元素中选出m个，不需要排序

计算方式：C(n, m)表示从n开始乘，每次递减1，一共m个数字，除以m!

表达方式：C(n, m) = n! / (n - m)! / m!

特别注意：C(n, m) = C(n, (n - m))：从n个同学里选m个同学等价于从n个同学中选(n - m)个剩下

做题技巧

1. 正难则反：当直接求结果比较复杂时，可以使用全部情况 - 不符合条件的情况得到符合条件的结果数量
2. 捆绑法：当两个或多个元素必须相邻时，可以通过将他们看作一个元素进行排列，最后讨论他们之间的排序
3. 插板法：涉及到元素分配问题时可以使用插板法，仅在最少分配一个时才可以使用插板法
   • 如果没有限制至少分一个，我们可以通过加数量的方式，让每个容器至少分一个

复杂度问题

时间复杂度

1. 对整个程序而言，时间复杂度只考虑运行时间最多的那一个即可
2. 对于一个算法而言，时间复杂度要考虑他运行的次数，通常是O(xx) ~ O(xx)，要考虑最优和最差情况
3. log n代表n在二进制下的位数

空间复杂度

1. 只需要记得，空间复杂度是所有容器中，最大容器所占空间的大小
2. 偶尔遇到栈或队列等可动态变化的容器时，需要通过整个程序去判断他们在运行时最大可能占多少空间

在判断时间复杂度或空间复杂度时，需要省略掉结果中的常数

排序算法的稳定性

相对位置是否发生改变

相对位置指的是相同的元素之间的位置是否发生改变

杂项

IP部分

IPv4：四个八位的二进制数，用.隔开，例如12.34.56.78，小数点隔开的每个数字都在0~255之间

IPv6：8个16进制的数字，用:隔开，防止IPv4不够用

缩写

LAN:局域网

WAN:广域网

MAN:城域网

以AN结尾的基本都与网络有关

ROM只读存储器，RAM随机存储器

WWW万维网

FTP:文件传输协议

SMTP:简单邮件传输协议

P2P:对等网络

TCP:传输控制协议

UDP:用户数据报协议

IMAP:交互邮件访问协议

HTTP(S):超文本传输协议，S代表加密

NOIP

1. NOIP从1995年开始举办，2019年暂停一年，2020年恢复
2. 复赛使用C，C++，Pascal，2022后只能使用C++
3. 复赛使用Linux测评器
4. NOI的全名：全国青少年计算机程序设计竞赛，现更名为全国青少年信息学奥林匹克竞赛
5. NOIP的全名：全国青少年信息学奥林匹克联赛，1995 年至 2018 年已举办 24 次
6. 如果题目问道NOIP举办了多少届，直接从卷面上第x届csp去减去1届
7. APOI：亚洲与太平洋地区信息学奥林匹克竞赛，全亚太
8. IOI：国际信息学奥林匹克竞赛，等级最高的信息学竞赛，全世界

图片分辨率考察空间换算

图片

分辨率 x 真彩色位数 / 8得到图片占多少byte

题目中可以会考察空间换算

视频

分辨率 x 真彩色位数 x 视频长度 x 视频帧数 / 8

比如视频长度95秒，每秒35帧，结果就是分辨率 x 真彩色位数 x 95 x 35 / 8