对数
2023 CSP-S 真题解析
计算机常见存储器分类笔记
1. 先按“断电会不会丢数据”分类
这是初赛最常考的分类。
类型 特点 常见例子 易失性存储器 断电后数据丢失 RAM 非易失性存储器 断电后数据仍然存在 ROM、HDD、SSD、U盘
最重要记忆：
> RAM 断电就丢，ROM / 硬盘 / SSD 断电不丢。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. RAM
RAM = Random Access Memory，随机存取存储器，平时一般叫内存。
主要特点：
* 速度快
* CPU 运行程序时会频繁使用
* 临时存放正在运行的程序和数据
* 断电后数据消失
* 属于易失性存储器
例如：
比如你打开浏览器、IDE、游戏后，这些程序运行时的数据主要放在 RAM 中。
一句话：
> RAM = 临时工作区。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. ROM
ROM = Read Only Memory，只读存储器。
主要特点：
* 断电后数据不会丢失
* 一般保存比较固定的数据或程序
* 属于非易失性存储器
传统 ROM 主要强调“只能读或很难修改”，现代设备中的固件也常使用 Flash ROM 等形式。
一句话：
> ROM = 长期保存固定程序。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. HDD
HDD = Hard Disk Drive，机械硬盘。
主要特点：
* 使用磁性介质存储数据
* 有机械结构
* 容量通常较大
* 价格相对便宜
* 断电后数据不丢
* 属于外存 / 辅助存储器
* 属于非易失性存储器
例如：
通常可以长期存在硬盘中。
一句话：
> HDD = 机械式长期存储。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. SSD
SSD = Solid State Drive，固态硬盘。
主要特点：
* 通常使用 Flash 闪存
* 没有机械结构
* 速度通常比 HDD 快
* 断电后数据不丢
* 属于外存
* 属于非易失性存储器
一句话：
> SSD = 更快的长期存储。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. RAM、ROM、HDD、SSD 对比
名称 中文 是否易失 速度 主要用途 RAM 随机存取存储器 是 很快 临时运行程序 ROM 只读存储器 否 较快 固件、固定程序 HDD 机械硬盘 否 较慢 长期保存文件 SSD 固态硬盘 否 较快 长期保存文件
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 内存和外存
还可以按用途分成：
内存
CPU 可以快速访问，主要服务于程序运行。
常见：
其中考试里最常说的“内存”一般特指 RAM。
外存
用于长期保存大量数据。
常见：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 存储层次
大致可以理解成：
越往上：
越往下：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. CACHE
Cache = 高速缓存。
位置大致在：
作用：
> 保存 CPU 最近或经常使用的数据，减少访问内存的时间。
特点：
* 比 RAM 快
* 容量比 RAM 小
* 通常也是易失性的
常见：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 寄存器
寄存器位于 CPU 内部。
特点：
* 速度最快
* 容量最小
* 直接参与 CPU 运算
例如 CPU 计算：
数据通常需要先进入寄存器再运算。
存储速度大致：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. FLASH
Flash 就是闪存。
特点：
* 非易失性
* 可以反复擦写
* 比传统 ROM 更方便修改
常见使用 Flash 的设备：
所以注意：
> SSD 不是 RAM，SSD 虽然也是芯片存储，但断电不丢。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
再记一条速度顺序：
以及：
> 易失性重点记 RAM；非易失性重点记 ROM、SSD、HDD。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
常见 LINUX 命令：
命令 作用 mkdir 创建目录 cd 切换目录 ls 查看文件 pwd 查看当前路径 rm 删除 cp 复制 mv 移动 / 重命名
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
数学笔记
容斥原理
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. 什么是期望
期望可以理解成：
> 一个随机事件重复进行很多次后，结果的平均值。
例如掷一个公平骰子，可能得到：
每个结果出现概率都是 1/6，所以期望为：
E=(1+2+3+4+5+6)/6=3.5
注意：期望不一定是实际可能出现的结果。
骰子不可能掷出 3.5，但平均值可以是 3.5。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 最基本公式
如果随机变量 X 可能取：
对应概率：
那么：
E(X)=x1×p1+x2×p2+...+xn×pn
一句话记忆：
> 期望 = 每种结果 × 它发生的概率，再全部相加。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 等概率情况
如果有 n 种结果，并且每种结果概率相同，那么直接求平均：
E=(x1+x2+...+xn)/n
例如随机从 2,4,8,10 中选一个：
E=(2+4+8+10)/4=6
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 不等概率情况
例如游戏：
期望收益：
E=10×0.5+20×0.3+0×0.2=11
表示长期玩很多次，平均每次收益约为 11 元。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 条件期望：先固定一个情况
很多初赛题会分两层随机。
例如：
这时最好：
> 先固定第一次的结果 x，计算在这个条件下的期望，再对 x 求平均。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
例：CSP-S 2023 第 8 题
第一次掷骰子得到 x，获得 2x 元。
第二次再掷一次：
固定第一次为 x，第二次成功保留收益的概率为 5/6，所以固定 x 的期望为：5/6 × 2x。
第一次的 x=1~6 等概率，因此再求平均：E=1/6 × Σ(5/6 × 2x)。
因为 1+2+3+4+5+6=21，所以：E=1/6 × 5/6 × 42=35/6。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 做题最常用模板
遇到期望题，可以按照这 4 步：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
