那故事就还没有结束 —— CSP 2020 游记

> …… 那故事就还没有结束 ## 初赛 Part ### Day -1 [好东西](https://www.luogu.com.cn/blog/Shuchong/luo-gu-gong-kai-csp-s-1-kao-dian-jiao-shi-ji-hua) ### Day 0 写一些对自己初赛有帮助的话： - 草稿纸是个好东西，有些 $k$ 叉树找规律或者求通项公式等的题一定要模拟。 - 阅读程序要自己模拟。 - 前缀表达式后缀表达式要复习。 - CCF 于 $1984$ 年开始创建比赛。 - 复习时间复杂度计算方法。 - 复习期望，一条 $[0,1]$ 的线段随机选择端点连接长度期望值为 $\dfrac{1}{3}$。 - $+-$ 优先级比 $\bmod \times$ 和 $/$ 低。 - 注意强制类型转换的作用。 - 2020 年 8 月，第 $37$ 届全国青少年信息学奥林匹克竞赛在长沙举行。 - NOI 比 IOI，APIO 和 NOIp 的历史悠久。 - 断电后 RAM（随机存储器）里的内容会丢失，ROM（只读存储器）里的内容会保存。 - ENIAC 为 $1946$ 年诞生的电子管计算机。 - 正确的一项还是错误的一项，允许的还是不允许的，要看清。 - 对 `a * d - b * c` 来说，`a d * b c * -` 是后缀表达式，`- * a d * b c` 是前缀表达式。 - 蔡勒公式： - 蔡勒公式中某年的1、2月要看作上一年的13、14月来计算 ### Day1 8.07 At Home 准备出发去首师附了，`while (1) rp++` --- 12.09 In The Car 考完了，感觉要退役了。 选择题还行，阅读程序第一个还可以，第二个是个奇怪的二分，全是时间复杂度分析题可还行。第三题 …… 99 行阅读程序 …… 不过有几道送分题。 完善程序是两个奇怪的题，个人感觉第一个比第二个难。 总体感觉不好，可能会退役，希望下午能考好。 --- 17.39 At Home 考完了，感觉 J 组疯狂送分。 选择比较简单，可能几道组合题比较难枚举。 阅读程序第一题直接模拟。 阅读程序第二题找规律： $$\begin{cases}k>1,ans=\dfrac{n-(k-2)}{k-1}\\k=1,ans=n\end{cases}$$ 但貌似是 $k$ 进制加法？ 阅读程序第三题：不知道干啥的 dfs，只错了三个出乎我意料。 完善程序一个分解质因数一个贪心板子，貌似还可以。 估计人人 $80+$，所以分数线应该会很高。 这样的话 …… 那我可能要拼 rp 了 /kel ### Day 3 出分和分数线了： > 分数线：J 57.5，S 48 J 肯定过了，S 比分数线多了 0.5 分过了 /fad ## 复赛 Part ### Day 1 CSP-J： T1 很简单，首先如果 $n$ 是奇数那么一定没有解，否则就从 $2^{25}$ 开始枚举（赛时用计算器算了一下，$2^{25}>10^7$，所以可行），因为题面说有唯一解，所以直接枚举即可。 T2 打了个 $O(n^2)$，桶排根本没想到。。。stO fjr Orz T3 是个什么东西？ T4 赛时打了个 dp，考完感觉是个错解，但 tm 过了大样例。。。 感觉 1= 不稳，然后看到群里一个个都 $300$ 分 阿克 。。。 CSP-S： 暴 力 场 T1 暴力，感觉 $20 \sim 40$。 T2 骗分，感觉看运气。 T3 暴力，感觉 $40\sim 55$。<- 这个分估假了 …… 可能会爆到 $10 \sim 20$. T4 $n=3$，感觉 $20$。 蓝勾无缘 /kk --- devout 比我想象中的要高大好多 /se fjr 太强了，他阿克了 J 并且 S 200+ /se ClCN 要捧杯进队了 /se --- 补一点赛时做出来或赛后做出来的题的题解： CSP-J： - A：暴力枚举，$\mathcal O(25)$。 - B：开桶，然后计算枚举，$\mathcal O(na_i)$。 - D：dp，对于每一个格子，可以从左一列某个格子转下来到达，也可以从左一列每一个格子转上来到达，因此记录两个数组，然后跑 dp，注意行列枚举顺序，$\mathcal O(3nm)$。