个人向吐槽：怎么这么多图论题啊
选择题
- 简单题，略。选 A。
- 答案是 $\dfrac{1920 \times 1080 \times 4 \times 1440 \times 30 \times 0.25}{1024^3}$，约为 $83.4$，选 C。
- 造计算机题，略。选 B。
- Fibonacci 堆 Dijkstra，应为 $O(m + n \log n)$。选 C。
- 每个点都遍历一次，每次枚举相邻点，显然 $O(n^2)$，选 B。
- 简单题，略。选 D。
- 简单题，略。选 A。
- 记第 $n$ 个错排数为 $D_n$，答案即为 $\dfrac{D_5}{5!}$。选 D。
- 简单题，略。选 C。
- 主定理裸题。选 B。
- 可以感性理解：第一次选择线段的期望长度为 $0.5$，那么第二次显然为 $0.25$，选 C。
- 选择排序 $O(n^2) - O(n^2)$，冒泡 $O(n) - O(n^2)$，插入 $O(n) - O(n^2)$，快排 $O(n \log n) - O(n^2)$。选 A。
- 相当于从 6 条边里选 4 条边。选 A。
- 造计算机题，略。选 B。
- NOI 规则题，略。选 D。
阅读程序
题 1
程序内容：遍历一个字符串，若目前遍历到的字符在该字符串的出现次数小于等于 50 次，就在字符串最后插入一个对应字符。
判断 1. 显然正确。
判断 2. len 在原来的程序中不断改变，而在这种写法中，len 不变。故会影响答案，错误。
判断 3. 错误，反例：aaa...aaabbb...bbccc...cccddd...ddd...zzz...zzz。
判断 4. 错误，反例：aa。
选择 1. 保证字符串不是空串，那么一定会有插入字符那一过程。故 $x < y$，选 B。
选择 2. 字符重复 51 次时不再插入，之前又重复 2 次，故结果为 $w$ 重复 53 次，选 D。
题 2
程序内容：一个写法奇怪的，使用了堆优化的全源最短路。
判断 1. 显然正确。
判断 2. 错误，应该小于 20010。
判断 3. 显然正确。
判断 4. 错误，如果这样 update(j, 0) 会出问题。
选择 1. 一个点只会被松弛 1 次，注意图可能不连通，故答案为 $O(n \min(n, m))$，选 D。
选择 2. 每条边至多访问一次，做 $n$ 次最短路，故答案为 $O(nm \log n)$，选 C。
题 3
程序内容：一个假的 dijkstra 与一个假的 floyd 对拍。
判断 1. 正确，无法处理自环。
判断 2. 正确，容易构造出数据。
判断 3. 正确，只需松弛 $n-1$ 次。
判断 4. 错误，dijkstra 没堆优化是 $O(n^2)$ 的。
选择 1. 手玩数据，选 B。
选择 2. 最多 10 条边，必须要留下 4 条边使其连通，故答案为 6 条，选 C。
完善程序
题 1
选择 1. 按 $a_i$ 从小到大排序，选 B。
选择 2. 能穿上则穿否则返回 false，选 D。
选择 3. 注意判断边界，选 B。A 在 $l = n, r = n + 2$，答案为 $n + 2$ 时会出锅。
选择 4. 简单题，略。选 A。
选择 5. 简单题，略。选 D。
题 2
基本思路：答案一定为 $a \times \frac{x}{2} + b$ 的形式，枚举 $a = 2i - j$，计算 $b$ 的范围。
选择 1. $n = m$ 显然只有 $n + 1$ 种情况，选 D。
选择 2. 初始时只有 1 种情况：分数为 0，选 C。
选择 3. $x, x/2$ 最多只有 $n - m$ 个，所以 $x+1$ 最少有 $i - (n - m)$ 个，选 C。
选择 4. 不算 $+1$ 的分数为 $(2i-j) \times x/2$，选 B。
选择 5. lst 指的是目前得分范围的最大值，故选 A。