CSP-S 2019 初赛题解

## [题目](https://ti.luogu.com.cn/problemset/1031)

----

### 1. 表达式求值

```cpp
x + a % 3 * (int)(x + y) % 2
2.5 + 1 * (int)7.2 % 2
2.5 + 7 % 2
2.5 + 1
3.5
```

知识点：
- 运算优先级
  1. 类型转化：`int(...)` 或 `(int)...`
  1. `*` `/` `%`
  1. `+` `-`
- `()` 可以改变运算顺序，提高内部运算的优先级
- [C++ 内置运算符、优先级和关联性](https://learn.microsoft.com/zh-cn/cpp/cpp/cpp-built-in-operators-precedence-and-associativity?view=msvc-170)

----

### 2. 图片文件格式

- WMV 视频文件
- MPEG 视频文件
- JPEG 图片文件
- AVI 视频文件

知识点：
- 文件格式

| 分类         | 常见格式（扩展名）                                               |
|--------------|------------------------------------------------------------------|
| 文本文档     | `.txt`, `.rtf`, `.doc`, `.docx`, `.odt`                          |
| 表格／数据   | `.csv`, `.xls`, `.xlsx`, `.ods`                                  |
| 可打印文档   | `.pdf`, `.pdf/a`（档案长期保存用）                               |
| 网页／标记   | `.html`, `.htm`, `.xml`, `.md`, `.json`                          |
| 图像格式     | `.jpg`, `.jpeg`, `.png`, `.gif`, `.tiff`, `.svg`, `.bmp`, `.webp`, `.eps` |
| 音频格式     | `.mp3`, `.wav`, `.aac`, `.flac`, `.ogg`, `.wma`                 |
| 视频格式     | `.mp4`, `.avi`, `.mov`, `.wmv`, `.mkv`, `.webm`, `.3gp`, `.mpeg` |
| 可执行／脚本 | `.exe`, `.bin`, `.app`, `.sh`, `.bat`                            |
| 其他格式     | `.pdf/a`, `.epub`, `.md`, `.json`, `.sqlite`, `.sql`, `.obj`, `.fbx` |

----

### 3. 按位或运算

$$
\begin{aligned}
  &11101110010111\newline
\text{or } &01011011101011\newline
 =&11111111111111
\end{aligned}
$$

知识点：
- 逻辑运算与位运算
  - 真值表

### 逻辑或运算

| 输入 A | 输入 B | 输出 A ∨ B |
|--------|--------|-------------|
| 0      | 0      | 0           |
| 0      | 1      | 1           |
| 1      | 0      | 1           |
| 1      | 1      | 1           |

### 逻辑与运算

| 输入 A | 输入 B | 输出 A ∧ B |
|--------|--------|-------|
| 0      | 0      | 0     |
| 0      | 1      | 0     |
| 1      | 0      | 0     |
| 1      | 1      | 1     |

### 逻辑异或运算

| 输入 A | 输入 B | 输出 A ⊕ B |
|--------|--------|-------------|
| 0      | 0      | 0           |
| 0      | 1      | 1           |
| 1      | 0      | 1           |
| 1      | 1      | 0           |

----

### 4. 编译器

将一种语言（通常是高级语言）翻译成另一种语言（通常是低级语言）。

知识点：编程语言

### [编程语言世代](https://zh.wikipedia.org/zh-cn/%E7%A8%8B%E5%BC%8F%E8%AA%9E%E8%A8%80%E4%B8%96%E4%BB%A3)
- 第一代语言：机器语言，01
- 第二代语言：汇编语言
- 第三代语言：高级语言，例如C
- 第四代语言：极高级语言，例如SQL
- 第五代语言：自然语言

----

### 5. 浮点数取整

```cpp
x = (int)(x * 100 + 0.5) / 100.0;
```

知识点：

- 浮点数转int会向下取整。
- 类型转化的优先级比运算更高。
- 常见函数：
  - [ceil](https://en.cppreference.com/w/cpp/numeric/math/ceil) 向上去整
  - floor 向下取整
  - round 四舍五入
- 以上三个函数的返回值类型与参数类型一致。

```cpp
int main() {
  cout << int(-10.7) << endl; // -10
  return 0;
}
```

----

### 6. 计数

| 情况   | 数学表达式                           |
|--------|--------------------------------------|
| ABCD   | `1 × A(4,4) = 24`               |
| AABC   | `2 × C(3,2) × C(4,2) × A(2,2) = 72`   |
| AABB   | `1 × C(4,2) = 6`                         |

总方案数：102

知识点：
- [排列组合](https://oi-wiki.org/math/combinatorics/combination/)

### 组合数

$$
\begin{aligned}
C(n,m) &= n!/m!/(n-m)!\newline
{n\choose m} &= \frac{n!}{m!(n-m)!}
\end{aligned}
$$

----

### 7. 排序算法

快速排序是不稳定排序。

----

### 8. 图论计数

- 完全图边数 m 与点数 n 的关系：m = n(n - 1)/2
- 非连通无向图的边数 m 与点数 n 的关系: m <= (n - 1)(n - 2)/2

----

### 9. 计数

- 根据颠倒规则
  - 可以放在第 3 位的数字有 {0, 1, 8}
  - 可以其他位置的数字有 {0, 1, 8, 6, 9}
  - 确定了前 2 位就可以确定后 2 位
- 要使 5 位数能被 3 整除
  - 各位上数字之和要能被 3 整除
  - 0, 6, 9 能被 3 整除
  - 1, 8 如果在前两位出现，那么在后两位也要作为颠倒的结果出现<br>2 × 1 和 2 × 8 模 3 的余数都为 2

- 注意到第 3 位可以通过取 0 / 1 / 8 来让 5 位数被 3 整除。
- 前 2 位任取 {0, 1, 8, 6, 9}，方案数为 5 × 5 = 25，第 3 位根据模数确定，总方案数为 25。

----

### 10. 集合

- $|U| = 15$
- $|V| = 12$
- $|U\cap V| = 4$
- $|U\cup V| = |U| + |V| - |U\cap V| = 23$

知识点：

- [容斥原理](https://oi-wiki.org/math/combinatorics/inclusion-exclusion-principle/)

----

### 11. 归并

假设 $|A|=|B|=1$，需要 1 次比较完成归并。

知识点：

- 归并排序

----

### 12. 数据结构

可以用存储图的数据结构：

- [邻接矩阵](https://baike.baidu.com/item/%E9%84%B0%E6%8E%A5%E7%9F%A9%E9%99%A3)
- [邻接表](https://baike.baidu.com/item/%E9%84%B0%E6%8E%A5%E8%A1%A8)

知识点：
- 栈
- 二叉树
- 队列
- 邻接矩阵

----

### 13. 贪心算法

知识点：

- 贪心算法
- 最短路算法
- 最小生成树算法

----

### 14. 等比数列

$$
486/2=243=3^5
$$

----

### 15. 动态规划

知识点：
- 动态规划