CSP-J2020 游记

CSP_Sept · 2020-10-10 18:12:56 · 个人记录

Day -29

参加了洛谷的 CSP2020 模拟，拿了 60 分的好成绩。

很慌，怎么办。

扔篇题解：Link

Day -27

从 @Aestas16 那讹来了福州某中学的 S 组初赛模拟题。

能拿到 74 分是我没想到的（（（

其中有一题蛮好的：

例 1 有三趟航班，第 1 趟航班准点的概率是 0.9，第 2 趟航班准点的概率是 0.8，第 3 趟航班准点的概率是 0.9。当第 i(i\in\{1,2\}) 个航班晚点，第 i+1 个航班准点时，旅行失败；否则旅行成功。则旅行成功的概率是 \underline{\ \ \ \blacktriangle\ \ \ }。

思路 考虑几种成功的情况：

1. 准准准，概率是 0.648。
2. 准准晚，概率是 0.072。
3. 准晚晚，概率是 0.018。
4. 晚晚晚，概率是 0.002。

加起来，旅行成功的概率是 0.74。

答案 0.74

明天就初赛了，好慌啊 /dk

又打了一场模拟赛：Link，竟然 87 /cy

Day -26

初赛。

学了一下主定理，大概就这点有用的：

对于递推式 T(n)=aT\left(\dfrac{n}{b}\right)+f(n)（a 是递推下子问题的数量，\dfrac{n}{b} 是每次递推子问题的规模，f(n) 是递推后做的额外的计算工作），

若存在常数 k(k\ge0)，使 f(n)=\Theta(n^{\log_ab}\log^kn)，则 T(n)=\Theta(n^{\log_ab}\log^{k+1}n)。

例 2 [\text{NOIp2016 tg }T_{14}] 假设某算法的计算时间表示为递推关系式 T(n)=2T\left(\dfrac{N}{4}\right)+\sqrt{n},T(1)=1，则算法的时间复杂度为 \underline{\ \ \ \blacktriangle\ \ \ }。

解析 此式中 a=2,b=4，则 k=0，代入，得 \Theta(\sqrt{n}\log n)。

答案 \Theta(\sqrt{n}\log n)

又刷了套模拟卷（Link），得分 84。

草，选择题全选 C，判断题全选 T 是在开玩笑吗。。。

而且这个也钛水了吧，还 CSP-S2020 模拟

初赛是在搞笑吗

完善程序最后 5min 改答案直接丢 6pts。

阅读程序第 3 题瞎蒙 3 题全错。

阅读程序第 2 题瞎蒙 3 题错 2 题。

smzzdx，估分 66.5，估计要止步初赛了。

好像可以过？

直播讲解

Day -21

出成绩了，63.5，分数线 51。

Day 0

快比赛了还上了一天的 whk /dk

打 XJOI 模拟 Day1 拿了 200\text{ pts}。

晚上面了本县高中的巨佬（还有 NOI 银的）

然后水洛谷，看到一个帖子问 nth_element 怎么用，然后我想我肯定会用，就没管它了（伏笔）

\text{Day 1}

• 8:15

进场，密码 123456（

先打了个快速幂的板子，事实证明没用

• 8:40

终于领到试题了。

先扫了一遍题目，发现 A 比较可做，B 还行，C 题面臭长，D 是 dp。

先开 A，1s 看出若 n\text{ and }1=1 直接输出 -1 即可。

然后只要先找到最大的二的整数次幂 k(k\le n)，每次判断 n\text{ and }k=1 是否成立即可。

• 9:30

A 切了。开 B。

先写了 O(n^2\log n) 50pts 算法，每次询问 sort 一遍。

后来想起平衡树可以做到 O(n\log n)，然后打了 30min 平衡树板子最后炸了 /dk

思路是，只写插入 x 和查排名为 x 的数两个操作，但忘的差不多了。

中途去了趟厕所，突然想起珂以用 nth_element（我之前用过，见下图）

果然厕所是灵感的源泉（（（

然后玄学优化一通到了 O(n^2)，珂以 85pts。

赛后发现 nth_element 的复杂度果然是 O(n)，但是当时忘记快读了 /dk

跑了一发大样例跑了 1.2s，看来如果 CCF 少爷机跑得快的话珂以骗得 90pts（

草，原来正解是桶排吗 /dk

当时觉得分数 \le 600 是多余条件，事实上……

考场上忘记了 nth_element 的用法，调了 1h。（照应）

• 11:20

大概写完 B 了，开 D。

草，忘记回溯了。

搜索写挂了，只有 5pts 了（

• 11:30

开 C。发现题目好理解，However，读入处理钛麻烦了。

每次询问都要重新备份一遍，真是**东西，复杂度还不上天。

弃疗力！

• 11:52

提前离场了。。

估分：100+85+0+5=190，爬了

Day 2

现在慌的 1p，在等代码出来。

晚上可能会打 abc182 放松心情（雾

Day 4

终于搞到了代码（感谢巨佬 @Vector_）

Luogu : 100+85+0+0=185

jsk : 100+85+0+0=185

菜是原罪（悲）

Day 10

成绩出来了。

CCF 的数据真的是弱的 1p，D 打的假算法竟然还有 5pts。

于是就 100+85+0+5=190。

Day 25