CSP-J2020 游记

### Day -29 参加了洛谷的 [CSP2020 模拟](https://www.luogu.com.cn/contest/34867)，拿了 $60$ 分的~~好成绩~~。 很慌，怎么办。 扔篇题解：[Link](https://www.luogu.com.cn/blog/supervise/luogu-csp2020-1) ### Day -27 从 @[Aestas16](https://www.luogu.com.cn/user/128141) 那~~讹~~来了福州某中学的 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](http://ks.wjx.top/jq/86518350.aspx)，竟然 $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](https://www.bilibili.com/read/cv7907230)），得分 $84$。 草，选择题全选 `C`，判断题全选 `T` 是在开玩笑吗。。。 ~~而且这个也钛水了吧，还 CSP-S2020 模拟~~ ___ 初赛是在搞笑吗 完善程序最后 5min 改答案直接丢 6pts。 阅读程序第 3 题瞎蒙 3 题全错。 阅读程序第 2 题瞎蒙 3 题错 2 题。 smzzdx，估分 $66.5$，估计要止步初赛了。 ~~好像可以过？~~ [直播讲解](https://live.polyv.cn/watch/1946668) ### 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（我之前用过，见下图）  $$\small{\color{grey}\text{来自 CSP2020 备战日记}}$$ 果然厕所是灵感的源泉（（（ 然后玄学优化一通到了 $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 终于搞到了[代码](https://github.com/Sept0913/sv/tree/master/CSP2020%20Code)（感谢巨佬 @[Vector_](/user/126763)） 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 $190\text{ pts}$，全国 $rk2925$。 ___ ### 总结 游记结束了，下面是总结。 （过几天补）