csp初赛知识点
计算机基础知识
1.*计算机的分类
-
按年代分类
| 年代 |
实现方式 |
| 1946 ~ 1958 |
电子管 |
| 1959 ~ 1964 |
晶体管 |
| 1965 ~ 1970 |
集成电路 |
| 1971 ~ 至今 |
超大规模集成电路 |
考试方法：计算机按实现方式分类，至今有四类（要简单了解是哪四类）。按年代顺序分别是电子管 - 晶体管 - 集成电路 - 超大规模集成电路。
-
按性能分类
- 巨型机/超级计算机：用于科学研究，我国目前有银河和天河两类超级计算机。
- 大型机/中型机：用于科研领域。
- 小型机：用于服务器。
- 微型机：民用的手机/电脑都是微型机。
- 工作站：相当于微型机。
超算 > 大/中型 > 小型 > 微型 = 工作站
考试方法：计算机按性能分类，可以分成五类，具体五类简单了解即可。
2.**空间换算
| ** 8 bit** |
1 byte(B) |
| 1024 B |
1 KB |
| 1024 KB |
1 MB |
| 1024 MB |
1 GB |
| 1024 GB |
1 TB |
- 1024 = 2^10（必须记住）
- 2^10 * 2^10 = 2^20 （从数学意义上10个2相乘再乘上10个2相乘相当于20个2相乘）
- 拓展知识点：在平时买U盘或者磁盘的时候，厂家给我们玩了一个文字游戏，用的不是1024进行换算而是1000，所以通常大小会比实际大小缩水 7% 左右。
考试方法：
- 牢记bit和byte的换算
- 1024的二进制
- 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
-
逻辑非：单目运算符，逻辑取反，把真变成否，把否变成真
-
逻辑与：全真则真
-
逻辑或：全否则否
-
运算顺序：! > && > ||
-
补充：三目运算符本质上也是逻辑运算，需要强调一个点，三目运算符联立时是从右往左运算
-
补充：在部分题目中出现^和∨时，^是&&，∨是||
-
三目运算符
11.*位运算
在位运算中，如果有负数参与运算要先把负数变成补码再进行运算。位运算本质上就是把两个数的补码进行位运算，所以结果也是补码。所以如果运算结果是正数则不用理会，但如果是负数则需要通过补码取原码。
- 按位取与：&，表示把两个数字转成二进制补码进行按位取与计算，如果位数不足则补0
- 按位取或：|，表示把两个数字转成二进制补码进行按位取或计算，如果位数不足则补0
- 按位取反：~，表示把数字转成二进制补码进行按位取反计算。
- 按位异或：^，表示把两个数字转成二进制补码进行按位异或计算，不同为1，相同为0
数据结构
1.*图论基本概念
- 顶点/节点都统称为点
- 点与点之间的连线都统称为边
- 有向边：两个点之间的连线有方向，如a -> b，表示a能指向b，b不能指向a
- 无向边：两个点之间的连线没有方向，如a - b，表示a能指向b，b也能指向a
- 简单图：没有自环，没有重边的图。通常情况，涉及图论问题题目都默认是简单图
- 自环：从一个点出发到达自己的边叫自环
- 重边：从一个点出发到达另一个点的边的数量 > 1
- 完全图：从每个点出发都能连接除自己以外的所有点，完全图的边的数量是固定的
- 无向完全图边的数量是 n(n-1)/2，有向图则需要乘2
- 连通图：可以直接/间接访问到所有的点，完全图一定是连通图，连通图不一定是完全图。
- 环：一个点从自己出发，经过不重复的边最终访问到自己，过程中经过的所有路径组成一个环
- 无向图中a - b，不能组成一个环
- 有向图中a -> b 和 b -> a，可以组成一个环
2.**树
- 无环且连通的图就是树。哪怕这个图形状怪异，都可以摆成树的形状
- 根节点：最上层的一个点，一个树有且只有一个根节点。通常题目会规定一个根节点，默认是1作为根节点
- 深度：到根节点需要经过几条边，深度就是多少。一般题目会考察最大深度问题
- 高度：对于这个树而言的最大深度
- 叶子节点/叶节点：没有子节点/儿子的节点
- 祖先：对于一个节点而言，他到根节点经过的每一个节点都是他的祖先
- 子节点/儿子：对一个节点而言，与这个节点连接且深度比这个节点大1的节点
- 兄弟：两个或者多个点有同一个父节点/父亲称为兄弟
- 后代：祖先的相反词，如果a是b的祖先，那么b就是a的后代
- 子树：对于一个节点而言，他与他父亲/父节点断绝父子关系后，由他为根节点组成的树叫他的子树
3.***二叉树
遍历规则
- 前/先序遍历，中序遍历，后序遍历：他的前中后讲的是根。如前序就是根在最前，也就是根左右
- 可以通过前序+中序或者后序+中序得到二叉树。因为通过前序/后序可以找到根的位置，通过中序去确定左右
- 满二叉树/完美二叉树：每一层只要存在则一定排满的二叉树。所有叶结点的深度均相同的二叉树
- 完全二叉树：只要求按从上往下从左往右按顺序排列的二叉树
- 完整二叉树：要么没有儿子，要么有两个儿子
4.*栈
- 先进后出
- 用stack或者vector进行模拟
- stack是栈的标准容器，但是用得比较少
- vector可以完整的使用stack的所有功能，而且还能通过下标取值，比stack强大太多
- vector由于是一个容器，模拟栈的时候要符合先进后出的逻辑，所以需要尾插
- v.push_back()
- v.pop_back()
- v.empty()
- v.size()
- v.back()
5.*队列
- 先进先出/头插尾出
- 用queue进行模拟
- queue是队列的标准容器
- q.push()
- q.pop()
- q.empty()
- q.size()
- q.front()
- 队列没有迭代器且不能通过下标访问
6.*链表
- 可以使用 list 的数据结构，但是list在考试中不常见，一般考试仍然用结构体去模拟链表
- 和数组的共同点就是都是存储相同类型数据
- 区别点1
- 区别点2
- 链表：增加/删除/插入元素很方便，但是查询元素很慢
- 数组：无法直接增加/删除/插入元素，但是查询速度快
- 考点：如何使用结构体模拟
7.***字符串问题
- 字符串：表示一串连续的字符
- 子串：字符串中任意个连续的字符组成的字符串
- 题目中的子串如果没有强调非空，那么空串也算子串
- 字符串本身也是自己的子串
- 长度为n的字符串，最多有 (1 + n) x n / 2 + 1个字串，最少有n + 1个字串
- ***字符串表达式的前中后缀
- 前缀/后缀转中缀
- 模拟一个栈
- 从右往左/从左往右遇到数字则放入栈中，如果遇到符号就取出栈中最上面的两个元素进行计算，计算结果也放进去
- 注意进行减法和除法时，被减数/被除数是栈顶元素
- 中缀转前/后缀
- 按运算顺序给表达式加上小括号，原本有小括号的不用操作
- 把所有的符号放在括号左/右
- 从外层到里层把括号打开
数学部分
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)个剩下
做题技巧
- 正难则反：当直接求结果比较复杂时，可以使用全部情况 - 不符合条件的情况得到符合条件的结果数量
- 捆绑法：当两个或多个元素必须相邻时，可以通过将他们看作一个元素进行排列，最后讨论他们之间的排序
- 插板法：涉及到元素分配问题时可以使用插板法，仅在最少分配一个时才可以使用插板法
- 如果没有限制至少分一个，我们可以通过加数量的方式，让每个容器至少分一个
复杂度问题
时间复杂度
- 对整个程序而言，时间复杂度只考虑运行时间最多的那一个即可
- 对于一个算法而言，时间复杂度要考虑他运行的次数，通常是O(xx) ~ O(xx)，要考虑最优和最差情况
- log n代表n在二进制下的位数
空间复杂度
- 只需要记得，空间复杂度是所有容器中，最大容器所占空间的大小
- 偶尔遇到栈或队列等可动态变化的容器时，需要通过整个程序去判断他们在运行时最大可能占多少空间
在判断时间复杂度或空间复杂度时，需要省略掉结果中的常数
排序算法的稳定性
相对位置是否发生改变
相对位置指的是相同的元素之间的位置是否发生改变
杂项
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
- NOIP从1995年开始举办，2019年暂停一年，2020年恢复
- 复赛使用C，C++，Pascal，2022后只能使用C++
- 复赛使用Linux测评器
- NOI的全名：全国青少年计算机程序设计竞赛，现更名为全国青少年信息学奥林匹克竞赛
- NOIP的全名：全国青少年信息学奥林匹克联赛，1995 年至 2018 年已举办 24 次
- 如果题目问道NOIP举办了多少届，直接从卷面上第x届csp去减去1届
- APOI：亚洲与太平洋地区信息学奥林匹克竞赛，全亚太
- IOI：国际信息学奥林匹克竞赛，等级最高的信息学竞赛，全世界
图片分辨率考察空间换算
图片
分辨率 x 真彩色位数 / 8得到图片占多少byte
题目中可以会考察空间换算
视频
分辨率 x 真彩色位数 x 视频长度 x 视频帧数 / 8
比如视频长度95秒，每秒35帧，结果就是分辨率 x 真彩色位数 x 95 x 35 / 8
