CSP-J1 2021 讲解
为了不影响阅读体验，卷子放最后了^_^
Now stop UPDing（不知道还有没有用，所以没删）
一、单选
- 答案:D.C
解析:C 语言是面向过程的，其他三项是面向对象的。
- 答案:B.图灵奖
解析:常识题，图灵奖是计算机领域的。
- 答案:A.二进制
解析:计算机内使用二进制进行储存。
- 答案:C.$n-1$
解析:设第一个数为 $max$ 并将其依次和之后的 $n-1$ 个数进行比较并取较大值即可，比较次数为 $n-1$。
- 答案:D.$c,d,a,e,b$
解析:$c,d$ 出栈后，栈内元素从栈底到栈顶为 $a$、$b$，$a$ 的出栈顺序必然在 $b$ 之后。
- 答案:D.$m-n+1$
解析:树的边数为 $n-1$，故需删去 $m-(n-1)$ 条边。
- 答案:C.$5.75$
解析:$1 \times 2^2+0 \times 2^1+1 \times 2^0+1 \times 2^{-1}+1 \times 2^{-2}=5.75$。
- 答案:A.$16$
解析:高度为 $5$ 的完全二叉树的底层结点个数在 [1,16] 内，故有 $16$ 种不同的形态。
- 答案:B.
abc+*d*
解析:树长这样，后序遍历即可。
*
/ \
* d
/ \
a +
/ \
b c- 答案:B.$15$
解析:先按照“区分队伍的编号"来计算，然后再除去三个队伍的排列即可。C{6,2} $\times$ C{4,2} $\times$ C{2,2}$ \div $A{3,3}$=15$。
- 答案:B.贪心
解析:哈夫曼编码采用了贪心策略。
- 答案:A.$18$
解析:分类讨论:
-
第一位放 $3$，后两位各可选放 $1$ 或 $2$，共有 $2 \times 2=4$ 种;
-
第一位放 $1$ 或 $2$，后两位可选择：放两个不同的数，有 A{3,2}$=6$ 种或放两个相同的数，有 $1$ 种。综上，共有 $4+(6+1) \times 2=18$ 种。
- 答案:C.$210$
解析:手算模拟即可：$7 \times 5 \times 3 \times 2 \times 1=210$。
- 答案:B.$2$
解析:共有三种可能的遍历顺序：$abdce$，$acdbe$，$acedb$。
故最后一个遍历到的点有 $2$ 种可能。
- 答案:B.$15$
解析∶最优方案之一∶$1,2$ 过河，$1$ 返回，$4,8$ 过河，$2$ 返回，$1,2$ 过河。总耗时为 $2+1+8+2+2=15$。我的错解:让 $1$ 渡另外三人过河，得出耗时 $8+1+4+1+2=16$。
二、读程序
1.
分析:$f(x)$ 返回二进制表示下 $a$ 中 $1$ 的个数，$g(a)$ 返回二进制表示下 $a$ 中最低位的 $1$ 所对应的 $2$ 的幂。
- 答案:B
解析:$n=1001$ 时，第 $22$ 行会进行 cin>>a[1000]; 而数组 $a$ 的下标范围是 [0,999]，会发生下标越界。
- 答案:B
解析:由程序功能可知，非整数并不会使程序陷入死循环。
- 答案:B
解析:对于 $a[4]=(10)10=(1010)2$，有 $f(x)=2$，$g(x)=2$，题面中输出结果为 $5$，故错误。
- 答案:A
解析:$(511998)10=(1111001111111110)2$，算得 $f(x)=16$，$g(x)=2$，正确。
- 答案:B
解析:移动后在调用 $g(a[i])$ 时会提示 $g$ 函数未定义。
- 答案:B
解析:由 $65536=2^{16}$，$2147483647=2^{31}-1$ 得：
$(-65536)10$ 在二进制下的表示为 $16$ 个 $1$ 接 $16$ 个 $0$，$(2147483647)10$ 在二进制下的表示为 $1$ 个 $0$ 接 $31$ 个 $1$，算得 $f(-65536)=16$，$g(65536)=65536$，$f(2147483647)=31$，$g(2147483647)=1$。
2.
分析:解密所给字符串。加密原理为将 $3$ 个字符(共 $3 \times 8=24$ 位)拆开成 $4$ 个 $6$ 位表示的小字符。
- 答案:B
解析:题面描述为小字符的取值范围，此程序进行解密过程，输出的字符串可由任意字符构成。
- 答案:A
解析:程序仅对字母、数字、"+"、"/"、"="这 $64$ 种字符进行了区分，其他所有字符都会被看作同一字符。故若输入字符串为"123 (123"和"123) 123"，两者输出相同。
- 答案:A(有争议)
解析:第一行输出了 $int(char(0xff))$，如果 $char$ 类型有符号则输出 $-1$，否则输出 $255$。
- 答案:B
解析:观察程序得，$encode$ 中只有一个 $O(n)$ 的循环，循环内部为简单运算和 $string$ 的 $+=$ 操作。
- 答案:B
解析:手算即可。
- 答案:C
解析:根据输入字符串长度为 $12$，末尾有 $1$ 个"="可知：输出字符串长度为 $8$，故排除 $AB$。$CD$ 选项的差别仅在最后一位，只需相应地根据输入字符串中的 $jE$ 部分计算出最后一位即可。
计算时如果记忆了一些关键的 $ASCII$ 码会比较好算，但如果没记也并不是不能做：在 $27$ 题中，排除 $AB$ 后，发现 $CD$ 选项的第一个字符都是 $c$，第 $7$ 个字符都是 $2$，可以根据输入字符串计算得出 $c$ 和 $2$ 对应的 $ASCII$ 码，并将其应用在 $26,27$ 题的计算中。
3.
程序本身较难读懂，可以从 $2$ 开始多找几个点算一算帮助理解， 实在不行也可以直接硬做。
- 答案:A
解析:$f[1],g[1]$ 在 $x=1$ 以外的情况下用不到。
- 答案:B
解析:不会出现。$C[i]$ 记录的值为的最小质因子的次数 $+1$，即 $f[i]$ 的一个因子。在 $f[i* k]=f[i]/c[i* k]* (C[i* k]+1)$ 中，带入 $c[i* k]=c[i+1]$ 得：$f[i* k]=f[i]/(C[i]+1)* (C[i+2])$，起到将 $f[i]$ 中的因子 $c[i]+1$ 替换为 $c[i]+2$ 的效果，不会出现除不尽需要下取整的情况。
- 答案:B
解析:可以简单地找出反例如：$g[4]=7$，$g[5]=6$。
- 答案:A
解析:在第二层循环内部，$a[i* k]=1$ 起到了筛合数的效果，而合数 $i \times k$ 只会在这一种情况($k$ 是其最小的质因子)下被筛去(其他情况下，如 $i \times k=i'\times k'$，因为 $k'$ 不是最小的质因子，因此在 $i'$ 的循环进行到 $k'$ 之前就会 $break$)，所以时间复杂度是 $O(n)$ 的。
- 答案:C
解析: $f[i]=2$ 说明是质数，$100$ 以内质数有 $25$ 个。
- 答案:C
解析: $1000=23 \times 53$，故 $f[1000]=16$，$g[1000]=2340$。
三、完善程序
1.
- 答案:D
解析:变量 $c$ 记录离开的人数，需要循环至 $c=n-1$ 为止。
- 答案:C
解析:$p$ 记录当前的人报的数，如果报的是 $1$ 则离开。
- 答案:C
解析:更新离开的人数。
- 答案:D
解析:交替报 $0$ 或 $1$。
- 答案: B
解析:表示当前报数的人，故应该从 $0 \sim (n-1)$ 绕圈循环进行。
2.
- 答案:B
解析:按照横纵坐标对所有点进行排序。
- 答案:D
解析: $unique$ 函数起到删去多余的点的效果，如果该点是第一个点，则保留，否则判断该点和前一个点坐标是否完全相同，是则舍去，否则保留。
- 答案:C
解析: $BD$ 选项均可能出现选点错误/进入死循环的情况，$A$ 选项计算结果错误(如 $a=3,b=4$，得 $mid=5$)。
- 答案:B
解析:点是按照坐标升序排的(即 $cmp(A[i],A[i+1])==1)$，二分时也用同样的方式进行比较:若 $cmp(A[mid],p)==1$，则 $p$ 点一定在 $mid$ 右侧。
- 答案:D
解析:后文中二分查找的点是矩形的左上顶点和右下顶点，故前两层循环起到枚举左下顶点和右上项点的效果，需要判断 $i$ 点是否位于点的左下方。
累了
