Sept

Everything needs hard.

CSP-J2020 游记

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(我之前用过,见下图)

$$\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

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

Luogu : $100+85+0+0=185$

jsk : $100+85+0+0=185$

菜是原罪(悲)

Day 10

成绩出来了。

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

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


总结

游记结束了,下面是总结。

(过几天补)


2020-10-10 18:12:56 in 游记