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

一只书虫仔 · 2020-10-10 18:16:13 · 个人记录

…… 那故事就还没有结束

初赛 Part

Day -1

好东西

Day 0

写一些对自己初赛有帮助的话：

• 草稿纸是个好东西，有些 k 叉树找规律或者求通项公式等的题一定要模拟。
• 阅读程序要自己模拟。
• 前缀表达式后缀表达式要复习。
• CCF 于 1984 年开始创建比赛。
• 复习时间复杂度计算方法。
• 复习期望，一条 [0,1] 的线段随机选择端点连接长度期望值为 \dfrac{1}{3}。
• 注意强制类型转换的作用。
• 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 组疯狂送分。

选择比较简单，可能几道组合题比较难枚举。

阅读程序第一题直接模拟。

阅读程序第二题找规律：

但貌似是 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)。