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

· · 个人记录

一

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

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

  1. 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

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

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

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

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

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

左子: BG

右子: FAEDC

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

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

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

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

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

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

插入排序就是n^2

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

归并是nlogn的

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

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

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

常识题，NOI 从 1984 年开始举办，NOI2020 是在长沙 (我太菜了，还在家里玩泥巴)

二

(1)

  1. 显然输入就可以输入一个奇数

  2. 显然

  3. 这些行是为了记忆化的，删去只会影响程序效率

  4. 确实

  5. 慢慢推，加在一起就是 8

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

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

    (2)

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

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

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

  11. 自行推导

  12. 显然

(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}