2019-CSP-入门级解析

**一、单项选择题**
**1**:答案:cn
**2**:答案:01 0010 1000 0011
**3**:答案:4个字节
**4**:答案:s = a - c
**5**:答案:7次 $log_{2}100≈7$
**6**:答案:可随机访问任一元素。链表是插入和删除方便，定位困难。
**7**:答案:18。算式不好摆，列举吧。
|有球袋子数量|方案数|摆法|
|:--:|:--:|:--:|
|1|1|(8)|
|2|4|(1,7)(2,6)(3,5)(4,4)|
|3|5|(1,1,6)(1,2,5)(1,3,4)(2,2,4)(2,3,3)|
|4|5|(1,1,1,5)(1,1,2,4)(1,1,3,3)(1,2,2,3)(2,2,2,2)|
|5|3|(1,1,1,1,4)(1,1,1,2,3)(1,1,2,2,2)|
**8**:答案:15。空结点也要按顺序结构存储，所以$2^4-1=15$
**9**:答案:97
**10**:答案:29。分解质因数困难的话，直接拿答案倒套。
**11**:答案:2400。贪心:$3*600+2*300=2400$
**12**:答案:4。抽屉原理
**13**:答案:75。乘法原理。前2位有0、1、8、6、9共5种选择，第3位只能放0、1、8，后2位由前2位决定，因此总方案数为5*5*3*1*1=75.
**14**:答案:ABDEGHJCFI。忘记了看课件学习如何构造。
**15**:答案:图领奖
**二、阅读程序**
**第1题**
(1)**×**，程序没有说明是大小写字母
(2)**√**，$i$如果等于$0$，则除数为$0$，会造成运行错误。
(3)**×**，循环明显找的是$n$的所有因数
(4)**√**，判断语句的作用是比**'a'**大的字母重新排列为从**'A'**开始的字母，其他情况保持不变
(5)答案:6。只对$n$的因数位置上的字符进行转换，$18$的因数有$6$个，所以最多$6$个不同。
(6)答案:100000,上面分析已经说明找的是$n$的因数位置，这题算因数个数，应用**算数基本定理**思考，即分解质因数，求出质因数的个数，然后求出因数的个数。$100000=2^5*5^5$，根据**算术基本定理**，$6*6=36$
**第2题**
(1)**√**，显然统计没有超过$n$，一共$2$个数组，那么最后$ans$也不可能超过$2n$.
(2)**×**，新题型难的地方就在这里了，千万不能蒙。既然问的是不是偶数，我们就试着能不能找到数据，推翻结论。
因为统计的是两个数组的同一个位置，所以想数据可以从这里入手。
假如只有一组数据：
|x|y|
|:-:|:-:|
|3|7|
根据程序执行流程，都满足$a[x]$<$y$ && $a[y]$<$x$
此时$a[x]$和$a[y]$都为$0$，所以$a[3]=7$,$b[7]=3$
这时如果循环结束进入统计部分，当执行到$i=3$的时候，第$2$个$ans$计算后的值就不是偶数了。
(3)**×**，这个反例也很容易想。
|x|y|
|:-:|:-:|
|3|3|
(4)**×**，继续想反例。
|x|y|
|:-:|:-:|
|1|2|
|1|3|
(5)答案:2n-2m。你可以想数据测试，当然从逻辑上也可以分析。因为**两两不同**，所以相当于每次执行了$a[x]=y$和$b[y]=x$,则$m$组数据，共有$2m$个位置是大于$0$的，所以最终答案为$2n-2m$.
(6)答案:2n-2。你可以想数据测试。
逻辑上分析如下：
```
a[x]=y;
b[y]=x;
```
是必执行的。
因为$x$都是不同的，$y$是相同的。
所以,下面这句肯定不会执行的，因为$a[x]$肯定为0.
```
if(a[x]>0) b[a[x]]=0; 
```
而下面这句必然执行：
```
if(b[y]>0) a[b[y]]=0;
```
$b[y]$保存的是上一次的$x$，相当于把之前$a[x]$清$0$。
那么最终得出结论，循环结束的时候，只有2个位置有值：$a$数组的最后一个$x$位置，还有$b[y]$，所以答案为:$2n-2$.
**第3题**
首先这题，明显是一道递归题，根据区间的最小值划分两个区间后继续递归。
(1)**×**，想一组相同的数据模拟即可，因为有以下这条语句
```
if(l>r) return 0;
```
所以不会造成越界上的问题。
(2)**√**，因为当区间为$1$个数的时候，再调用递归，会遇到这句
```
if(l>r) return 0;
```
所以会返回$0$，再观察函数的返回值算式：
```
return lres+rres+depth*b[mink];
```
因为$b$数组都为$0$，所以一直返回$0$，最后结果也为$0$.
(3)答案:5000。最坏情况应该是$a$数组从小到大，当$n=100$时
![](/api/file/getImage?fileId=619d939ed170a10014000794)
$(2+100)*99/2≈5000$
(4)答案:600。看图分析，这里是估算，不是精确计算次数。
![](/api/file/getImage?fileId=619d939ed170a10014000793)
找规律计算：$100+2*50+4*25+8*12+16*6+32*3+64*1≈600$
(5)答案:385。看下图分析：
![](/api/file/getImage?fileId=619d939ed170a10014000795)
(6)答案:580。和要求最小，层数就要少，那么每次两个区间长度要尽可能接近，如果画草图，你会发现，这不就是二叉树么。
所以计算也就简单了：$1*1+2*2+4*3+8*4+16*5+32*6+37*7=580$
**三、完善程序**
**第1题**
首先，第$5$空最容易填，很容易猜出$size$是边长，当$n=1$的时候，边长是$2$，当$n=2$的时候，边长是$4$。说明边长=$n*2$,选项中没有$n*2$，只有**左移**，左移$1$位，相当于扩大**2倍**，所以第$5$空选择：**1 << n**
接着，可以从主程序的调用看出，递归每次传入的是需要翻转矩形左上角的坐标。
在递归程序中
```
int step=1<<(n-1);
```
在计算步长，用来划分子问题。
所以第$2$空和第$3$空就简单了，不难看出$4$次递归按：左上、右上、左下、右下的顺序。
所以第$2$空为左上角，选择: **x,y**
第$3$空为右下角，选择:**x+step,y+step**
观察递归函数，只有边界判断的时候有赋值语句，显然第$1$空不是填$0$或$1$。
从$4$次递归调用的最后一个调用最后一个参数(t^1)可以观察出，第$1$空应该填$t$.
再回头看第$4$空，第$3$个形参显然是$n$，然后根据题意，一开始初值为$0$，所以选:**n,0**.
**第2题**
(1)第$1$空，排除法。
题目说了计数，$++cnt[i]$不可能。
$++cnt[a[i]*maxs+b[i]]$也不可能，如果二维转一维，应该写成$(a[i]-1)*maxs+b[i])$
$++cnt[a[i]]$也不可能，题目说了对第二关键词排序。
所以答案为$++cnt[b[i]]$.
(2)第$2$空，观察第$5$空的选项，$ord$或$res$保存的应该是数组下标，否则第$5$空给出的选项就说不通。
所以优先选择$ord[--cnt[b[i]]]=i$.
样例代入后，结果如下：
$ord[0]=2$
$ord[1]=1$
$ord[2]=0$
(3)第$3$空显然送的，参照第$1$空分析，所以选$++cnt[a[i]]$.
(4)既然$ord$数组保存的是坐标(通过$2$的分析，可以看出$ord$按从小到大排序的).
通过第$4$空的选项，我们发现$res$保存的是第二关键词$b[i]$排序后的数组下标。
因为当前$cnt$(前缀和表示的是该数在第几个位置)记录的是第一关键词$a[i]$的位置，所以$ord[i]$表示下标的情况下，第一关键词显然是$a[ord[i]]$，符合的只有$res[--cnt[a[ord[i]]]]=ord[i]$.
(5)通过上面分析，$res$也是按从小到大排序的，且保存的是数组下标。所以第$5$空不用犹豫，选$a[res[i]],b[ord[res[i]]]$，直接按顺序输出即可。

Merlin's Blog

Navigation

Recent Posts

Friend Links