XP04 初赛笔记
2026-08-19 20:52:08
发布于：广东
对数
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 5;
int a[maxn];
typedef long long ll;
int n, l, r;
ll f(int x) {
ll ans = 0;
for(int i = 1, j = n; i < j; i++){
while (j > i && a[i] + a[j] > x) j--;
ans += j - i;
}
return ans;
}
void solve() {
cin >> n >> l >> r;
for (int i = 1; i <= n; i++) cin >> a[i];
sort(a + 1, a + 1 + n);
cout << f(r) - f(l - 1) << endl;
}
int main(){
int T;
cin >> T;
while (T--) solve();
return 0;
}
计算机常见存储器分类笔记
1. 先按“断电会不会丢数据”分类
这是初赛最常考的分类。
| 类型 | 特点 | 常见例子 |
|---|---|---|
| 易失性存储器 | 断电后数据丢失 | RAM |
| 非易失性存储器 | 断电后数据仍然存在 | ROM、HDD、SSD、U盘 |
最重要记忆：
RAM 断电就丢，ROM / 硬盘 / SSD 断电不丢。
2. RAM
RAM = Random Access Memory，随机存取存储器，平时一般叫内存。
主要特点：
- 速度快
- CPU 运行程序时会频繁使用
- 临时存放正在运行的程序和数据
- 断电后数据消失
- 属于易失性存储器
例如：
硬盘中的程序
↓
加载到 RAM
↓
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
ROM
其中考试里最常说的“内存”一般特指 RAM。
外存
用于长期保存大量数据。
常见：
HDD
SSD
U盘
存储卡
光盘
8. 存储层次
大致可以理解成：
寄存器
↓
Cache
↓
RAM
↓
SSD / HDD
越往上：
速度越快
容量越小
价格越贵
越往下：
速度越慢
容量越大
单位容量价格更低
9. Cache
Cache = 高速缓存。
位置大致在：
CPU
↓
Cache
↓
RAM
作用：
保存 CPU 最近或经常使用的数据，减少访问内存的时间。
特点：
- 比 RAM 快
- 容量比 RAM 小
- 通常也是易失性的
常见：
L1 Cache
L2 Cache
L3 Cache
10. 寄存器
寄存器位于 CPU 内部。
特点：
- 速度最快
- 容量最小
- 直接参与 CPU 运算
例如 CPU 计算：
a+b
数据通常需要先进入寄存器再运算。
存储速度大致：
寄存器 > Cache > RAM > SSD > HDD
11. Flash
Flash 就是闪存。
特点：
- 非易失性
- 可以反复擦写
- 比传统 ROM 更方便修改
常见使用 Flash 的设备：
SSD
U盘
存储卡
BIOS/UEFI 固件存储
所以注意：
SSD 不是 RAM，SSD 虽然也是芯片存储，但断电不丢。
RAM：内存，断电丢失
ROM：只读存储，断电不丢
SSD：固态硬盘，断电不丢
HDD：机械硬盘，断电不丢
Cache：高速缓存，比RAM快
寄存器：CPU内部，速度最快
再记一条速度顺序：
寄存器 > Cache > RAM > SSD > HDD
以及：
易失性重点记 RAM；非易失性重点记 ROM、SSD、HDD。
常见 Linux 命令：
| 命令 | 作用 |
|---|---|
mkdir |
创建目录 |
cd |
切换目录 |
ls |
查看文件 |
pwd |
查看当前路径 |
rm |
删除 |
cp |
复制 |
mv |
移动 / 重命名 |
数学笔记
容斥原理
1. 什么是期望
期望可以理解成：
一个随机事件重复进行很多次后，结果的平均值。
例如掷一个公平骰子，可能得到：
1 2 3 4 5 6
每个结果出现概率都是 1/6，所以期望为：
E=(1+2+3+4+5+6)/6=3.5
注意：期望不一定是实际可能出现的结果。
骰子不可能掷出 3.5，但平均值可以是 3.5。
2. 最基本公式
如果随机变量 X 可能取：
x1,x2,x3,...,xn
对应概率：
p1,p2,p3,...,pn
那么：
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. 不等概率情况
例如游戏：
50% 概率获得 10 元
30% 概率获得 20 元
20% 概率获得 0 元
期望收益：
E=10×0.5+20×0.3+0×0.2=11
表示长期玩很多次，平均每次收益约为 11 元。
5. 条件期望：先固定一个情况
很多初赛题会分两层随机。
例如：
第一次随机得到 x
第二次根据 x 决定收益
这时最好：
先固定第一次的结果 x，计算在这个条件下的期望，再对 x 求平均。
例：CSP-S 2023 第 8 题
第一次掷骰子得到 x，获得 2x 元。
第二次再掷一次：
1 种：和第一次相同 → 收益清零
5 种：和第一次不同 → 保留 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 步：
① 列出所有可能结果
② 求每种结果的概率
③ 计算：结果 × 概率
④ 全部相加
这里空空如也
有帮助，赞一个