CSP-S2021初赛易错题解析

发布时间 2023-09-09 21:55:51作者: 天雷小兔
一.1.

错误原因:没读题

解析:

ls是list的缩写,用于列出当前目录下所含的文件和子目录

cd是change directory的缩写,用于改变文件目录

cp是copy的缩写,用于复制

 

8.

错误原因:计算错误

解析:

一棵含有n个节点的二叉树的高度至少为floor(log2n)+1,还有一种方法,如果是深度为10的满二叉树的话,节点数为1023,深度为11的满二叉树有2047个节点,足够了,所以选11

12.

错误原因:计算错误

解析:

可以举一个例子,画出它的递归树,就可以发现,递归树形似一颗完全二叉树,完全二叉树的节点个数接近于2n,每次进入一个函数就要开辟新的空间,耗费时间,所以时间复杂度为O(2n)

 

14.

错误原因:不会

解析:

首先考虑等边三角形,共有9种,然后考虑等腰三角形,假设a,b为腰,那么有2+4+6+8+8+8+8+8=52种,还有ac为腰,bc为腰的可能性,所以总方案数为9+52*3=165种

15.

错误原因:计算错误

解析:

答案19,A->C->E->H->J

跑一遍dijkstra就行了,但是要注意松弛时候的标记

 

二.1.这一道题是数学题,计算了两个圆的面积交

20.

错误原因:不知道acos(0.5)是什么

解析:
acos(0.5)=PI/3,acos(-1)=PI,这一组样例是圆心重合,直接计算小球的体积即可

 

2.这一道题中的solve1和solve2都是求最大子段和的,每次考虑3种情况,第一种,最大子段和在中点左边,第二种,最大子段和在中点右边,第三种,最大子段和在中点左右,知道了这些,就可以做题了

23.

错误原因:没认真模拟

解析:

不可能,最多1次,及n为0,否则都会在h==m是退出

 

25.

错误原因:没读懂代码

解析:

假设n为256,则solve1会形成一棵递归树,节点个数为1+2+4+8+16+32+64+128=255,约等于256,所以时间复杂度为O(n)

 

26.

错误原因:没读懂代码

解析:

solve2比solve1多了两次循环,而循环的复杂度为O(log2n),所以时间复杂度为O(nlog2n)

 

3.这道题是base64编码的加密与解密

28.

错误原因:考虑不周全

解析:

可能出现‘\n’等字符,例子"QQpC",会输出"a\nb"所以不一定输出一行

 

33.

错误原因:模拟错误

解析:

由于加密是每3为变4位,所以可以分成4组,最后一组缺2个,所以是2个等号,只能是B和D,再比较B和D的区别,B是"MGN",而D是“MWN”,通过模拟,可以发现,应该是“MWN”,所以选D

 

三.1.这道题的思路类似于dijkstra,初始化f[4]=1,枚举未松弛集合中的最小值,更新4种操作,即可得到答案

35.

错误原因:理解错误

解析:

这里应该是判断n是否的到最小解,所以填!Vis[n]

 

37.

错误原因:理解错误

解析:

这里应该是更改已松弛的点的最小步数,所以填Vis[i]

 

2.这道题略难,用到了笛卡尔树,Euler序,分块等知识

39.

错误原因:代码理解错误

解析:

这里,是将S[top]的右儿子变成p,因为,这时S[top]的val已经大于等于p的val,所以要将S[top]的右儿子变成p,故选D

 

40.

错误原因:代码理解错误

解析:

这里的min函数,是按x节点和y节点的深度比较的,故选A

 

41.

错误原因:代码理解错误

解析:

这里应该是按块内的节点的深度比较的,故选D

42.

错误原因:代码理解错误

解析:

这里的S枚举了所有的情况,按照情况进行加减,每次取最小值,故选D

 

43.

错误原因:代码理解错误

解析:

Dif存储的是每个块中的节点深度关系,这里要进行块内查询,故选C