A卷答案（官方答案）（CSP-S2020第一轮）

以上是官方答案。

A卷题目（CSP-S2020第一轮）下载链接（洛谷附加文件）

单项选择题
CBBBD BAACC CDBDC

阅读程序
1、FFTTCC
2、FT*BAD
3、TFFDDC

完善程序
1、DBDDB
2、DBCAB

我的考场答案：

其中做错了的：

• 阅读程序第 3 题第 3 小题（最劣时间复杂度是否为 \mathcal O (n!)）应该选（×），正确的最劣时间复杂度为 \mathcal O \!\left( {(n!)}^2 \cdot n \right)。
• 阅读程序第 3 题第 5 小题（当 st0 = "0123456789ab" 且 st1 = "ba9876543210" 且 m = 1 时，输出的答案为）应该选 D（68），做法是：
  容易构造一个比较劣的耗费 \mathcal O (n^2) 步的操作序列，于是可以猜想当 n 足够大时答案为关于 n 的二次多项式，用给出的三个值进行插值即可得到答案为 68。

其中有争议的：

• 阅读程序第 2 题第 2 小题（问 d[a] 改为 d[b] 是否仍然正确）题目可能有争议。
• 阅读程序第 2 题第 3 小题（问 d[i] 严格单调递增时 swap 的平均执行次数）题目可能有争议，期望 swap 执行次数似乎为 \mathcal O (\log^2 n)，无正确选项。