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

文章目录

R e s u l t Result Result

赛时：

赛后：

F e e l i n g Feeling Feeling

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

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

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

S o l u t i o n s Solutions Solutions

红色是考场时做的标记，蓝色是修消防工程师是干什么的改后的

1~6

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

7~15

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

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

阅读1

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

阅读2

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

阅读3

原题题解

1：当且仅当 i < j i<j i<j时才成立，如果 i = j i=j i=j的话是1
2：错误，是组合
3：不一定，有模数
4：确实
5：显然 C 10 5 C_{10}^5 C105​肯定是最大值，而且没有超过模数
6：自己画一个杨辉三角求个前缀和即可

完善1

1：这个点遍历了，相当于去掉它
2：如果这个点没有入度了，相当于没有限制了，可以直接跑，如果 w = 0 w=0 w=0，说明它的父亲是没有删除的，那么自然它也可以遍历
3：父亲删除了，自己不能删，父亲没删，自己可以删
4：每个没有父亲的点开始遍历
5：把没有遍历到的点遍历完

完善2

1：最开始的 s u m sum sum只有第 n n n个数
2：显然放入 s i s_i si​这个数
3：去掉最小值，再取平均值
4：遇到更优的，则重置k数组，并放入i-1
5：遇到相同的最优解，直接放入i-1

本人版权意识薄弱，如果放出题目侵权请私信我
有意见和问题可以在下方评论区留言

T h e E n d The\ End TheEnd

本文地址：https://blog.csdn.net/xuxiayang/article/details/108961812