洛谷CSP 2020 第一轮（初赛）模拟 题解

· · 个人记录

一

1.

114$ 的相反数是 $-114$ $(114)_2$ = $1110010

则 (-114)_2 = 0001101 (等于 114 的反码)

2.

Luogu$, $LeetCode$, $Codeforces$ 都是 $OJ 3. $AAA$ 对应 $703 26$ × $26$ = $676

所以 BAA 对应 703 + 676 = 1379

然后 BBA 对应 1379 + 26 = 1405

所以 BYA 对应 1379 + 26 × 24 = 2003

然后 T 是第 20 个，对应加 19，就是 2003 + 19 = 2022

4.

5. 《算法竞赛进阶指南》上面有讲，用快排的思想，可以做到 $O(n)

6. 第一个的话是因为要联通，第四个的话树上是没有环的

7. 这道题最优方案是： 42 = 15 + 27 = (10 + 5) + (13 + 14)，代价为 42 + 15 + 27 = 84

8. 从前序遍历中可得知根是 H

从中序遍历中可得知 左子 和 右子

左子: BG

右子: FAEDC

如图: (将就看看吧...)
H_1
G_2 D_3
B_4 A_6 C_7
F_{12} E_{13}

综上所述: 最大下标至少为 13

9. 啊这...慢慢算就出来了

10. 最理想的情况: 一找就找到了，所以是 k 次

11. 枚举 C 班选了多少个风纪委员，再讨论，两侧是讨论的过程，数一下正好 18 种

12. 计数排序的复杂度 与 每个数的大小有关

插入排序就是n^2

希尔排序是n^{\frac 32}

归并是nlogn的

13. 随机一个 [a, b)⋂N^+

实际上就是随机一个 [a, b - 1)⋂N^+

如果你做过数据，这题随便拿下

14.

15. 常识题，$NOI$ 从 $1984$ 年开始举办，$NOI2020$ 是在长沙 ~~(我太菜了，还在家里玩泥巴)~~ ## 二 ### (1) 1. 显然输入就可以输入一个奇数 2. 显然 3. 这些行是为了记忆化的，删去只会影响程序效率 4. 确实 5. 慢慢推，加在一起就是 $8

  1. 最坏情况下纵向推 n 层，横向访问 m^2 遍

  2. 正确，i , j i,ji,j相当于枚举哪两个点是可以“瞬移”的（可以耗费0到达彼此）

    (2)

  3. 错误，输入都有 m，怎么可能无关？

  4. 正确，最大的答案可能是 1e9 级别的

  5. 正确，枚举两个瞬移点做 floyd，更新 F 数组

  6. 自行推导

  7. 显然

(3)

  1. 当且仅当 i < j 时才成立，如果 i = j 的话是 1

  2. 错误，是组合

  3. 不一定，有模数

  4. 确实

  5. 显然 C_{10}^5 肯定是最大值，而且没有超过模数

  6. 自己画一个杨辉三角求个前缀和即可

三

(1)

  1. 这个点遍历了，相当于去掉它

  2. 如果这个点没有入度了，相当于没有限制了，可以直接跑，如果 w = 0 ，说明它的父亲是没有删除的，那么自然它也可以遍历

  3. 父亲删除了，自己不能删，父亲没删，自己可以删

  4. 每个没有父亲的点开始遍历

  5. 把没有遍历到的点遍历完

    (2)

  6. 最开始的 sum 只有第 n 个数

  7. 显然放入 s_i 这个数

  8. 去掉最小值，再取平均值

  9. 遇到更优的，则重置 k 数组，并放入 i-1

  10. 遇到相同的最优解，直接放入 i-1

    \color{Blue}\colorbox{Yellow}{THE END}