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

文章目录

• • • • $Result$
      • $Feeling$
      • $Solutions$
      • $TheEnd$

$Result$

赛时：

赛后：

---

$Feeling$

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

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

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

---

$Solutions$

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

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{3}{2}}$，归并是$nlogn$的
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：错误，$floyd$顺序不能改变，$k$是阶段，$i,j$是枚举转移的点
2：错误，输入都有$m$，怎么可能无关？
3：正确，最大的答案可能是1e9级别的
4：正确，$i,j$相当于枚举哪两个点是可以“瞬移”的（可以耗费0到达彼此），枚举两个瞬移点做$floyd$，更新$F$数组
5：看图自行推导
6：显然

---

阅读3

原题题解


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

---

完善1

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

---

完善2

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

---

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

$TheEnd$

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