Day -29
参加了betway必威体育官方的 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\ \ \ }$。
思路 考虑几种成功的情况:
- 准准准,概率是 $0.648$。
- 准准晚,概率是 $0.072$。
- 准晚晚,概率是 $0.018$。
- 晚晚晚,概率是 $0.002$。
加起来,旅行成功的概率是 $0.74$。
答案 $0.74$
明天就初赛了,好慌啊 /dk
又打了一场模拟赛:,竟然 $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)$
又刷了套模拟卷(),得分 $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 银的)
然后水betway必威体育官方,看到一个帖子问 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$。
Day 25
$190\text{ pts}$,全国 $rk2925$。
总结
游记结束了,下面是总结。
(过几天补)