Luogu CSP 2020 第一轮（初赛）模拟题解&总结_PHP

文章目录

$R e s u l t$

赛时：

赛后：

$F e e l i n g$

感觉难度偏低，题目考得面还是可以的，跟OI相关的多很多
甚至出现了阅读2，阅读3两道原题。。。
~~修电脑的题终于tmd少点了~~
然后自我感觉状态还可以，一个小时半做完的，最后是错了第三题、十四题、二十题

其中第三题是我菜没办法，第十四题忘记了一棵树也可以算作森林，第二十题算对了，选错了。。。

严格意义上来说我应该是92，因为第二十题是4分的

$S o l u t i o n s$

红色是考场时做的标记，蓝色是修改后的

1~6

在这里插入图片描述
1：显然-114在二进制下为11110010，然后补码就是第一个1和最后一个1不变，中间的取反，得到A
2：Luogu就是洛谷啊。。。。Gitee是托管代码的。。。Leetcode源自美国硅谷，是一个OJ。。。Codeforces是俄罗斯一个团队创立的OJ
3：AAA对应703， $26\times 26=676$ ，所以BAA对应703+676=1379，然后BBA对应1379+26=1405，所以BYA对应 $1379+26\times 24=2003$ ，然后T是第20个，对应加19，就是2022
4： $4096\times 2160\times 24/8=26542080B=25920KB=25.3512MB$ （其实还要加上54B，但可以忽略不计）
5：《算法竞赛进阶指南》上面有讲，用快排的思想，可以做到 $O (n)$
6：第一个的话是因为要联通，第四个的话树上是没有环的

7~15

7：我蒙的！我蒙的！我蒙的！
8：可以把这棵树画出来

9：显然。。。
10：最理想的情况下一找就找到了，所以是 $k$ 次
11：枚举C班选了多少个风纪委员，再讨论，两侧是讨论的过程，数一下正好18种
12：计数排序的复杂度与每个数的大小有关，插入排序就是 $n^2$ ，希尔排序是 $n^{\frac 32}$ ，归并是 $n l o g n$ 的
13：随机一个 $[a,b)\bigcap N^+$ ，实际上就是随机一个 $[a,b-1]\bigcap N^+$ ，如果你做过数据，这题随便拿下
14：7个顶点的完全图有 $7\times 6/2=21$ 条边，边数最多的森林是树，它有 $n - 1 = 7 - 1 = 6$ 条边，所以要删去15条
15：常识题，NOI从1983年开始举办，NOI2020是在长沙（我太菜了，去不了）

阅读1

1：显然输入就可以输入一个奇数
2：显然
3：这些行是为了记忆化的，删去只会影响程序效率
4：确实
5：上面有我的推导过程，加在一起就是8
6：最坏情况下纵向推 $n$ 层，横向访问 $m^2$ 遍

阅读2

在这里插入图片描述

原题题解
1：错误， $f l o y d$ 顺序不能改变， $k$ 是阶段， $i, j$ 是枚举转移的点
2：错误，输入都有 $m$ ，怎么可能无关？
3：正确，最大的答案可能是1e9级别的
4：正确， $i, j$ 相当于枚举哪两个点是可以“瞬移”的（可以耗费0到达彼此），枚举两个瞬移点做 $f l o y d$ ，更新 $F$ 数组
5：看图自行推导
6：显然