TheSky233's Blog

𝐴𝑛𝑑 𝑖𝑛 𝑡ℎ𝑎𝑡 𝑙𝑖𝑔ℎ𝑡...

0%

CSP-S 2022 游记 / Black Fate.

发表于 分类于
本文字数： 6.7k 阅读时长 ≈ 6 分钟

CSP-S 2022 游记 / Black Fate.

前言

$\texttt{rt}\Delta$，本人已经初三了，因 whk 原因，考完这次 CSP（or NOIP？） 后会 AFO 一段时间，再回来应该已经是中考考完了吧，会不会回来我也不知道（笑）。

话说回来，初赛没过就真的止步于此了。

登场人物介绍

省流

正文

Day 0 （ CSP-S 2022 S1，$\textit{2022/9/17}$ ）

祝所有人 RP+=INF！

说句闲话：

  • CSP-S 2019 洛谷自测考了 $76 \text{ pts.}$

  • CSP-S 2020 洛谷自测考了 $71 \text{ pts.}$

  • CSP-S 2021 洛谷自测考了 $57 \text{ pts.}$

  • SCP 2021 洛谷自测考了 $74 \text{ pts.}$

  • SCP-S 2022 组考了 $22+25+15=62 \text{ pts.}$

图灵保佑我过初赛，Robert Tarjan 保佑我过初赛，冯·诺依曼保佑我过初赛，克劳德·香农保佑我过初赛，赫伯特•亚历山大•西蒙保佑我过初赛，姚期智保佑我过初赛，Bjarne Stroustrup 保佑我过初赛,傅里叶保佑我过初赛，爱因斯坦保佑我过初赛，钱学森保佑我过初赛，杜子德保佑我过初赛！

Day 1 （ CSP-S 2022 S1，$\textit{2022/9/18}$ ）

下午考 tg 组，先摸半天的鱼。

  • $\textit{12:00}$，出发去考点。

闲话：听说上午 J 组很难，寄了。

  • upd on $\textit{2022/9/19}$：J 组好像不难

牛顿迭代进入 J 组预警 指针乱飘，numeric_limits，神奇的位运算读程序题，大量纯背诵内容（点名排序的稳定性），哈.不会出 CSP-J1 可以不出的

——chen_zhe 锐评

S 组考完后的感想：

程序补全 T2 是送分是吧，阅读程序 T3 模负数是吧，for(int j=0;j<i;j*=2) 是吧，三叉树编码是吧

还好初赛之前写了排序全家桶，知道基数排序，计数排序和桶排序是不一样的！！！1

名人锐评

寄了捏 $:($

测过 lgvc 的 S 组自测 之后的感想：

$\texttt{I love CCF}$！自测 $\text{76 pts}$，CCF NB！

Day -39 （CSP-S 2022 S2，$\textit{2022/9/19}$ ）

xzl 自测 $79\text{ pts}$，lx 自测 $65.5\text{ pts}$，感觉能过线的样子。

在学校被一个比我小两岁还比我强的人在 whk 全方面被单调队列了捏。破防了

Day -38 $\sim$ Day -36 （ $\textit{2022/9/20} \sim \textit{2022/9/22}$ ）

搞了一周的 whk。

双周练。语文寄 数学寄 英语寄 物理寄。一周没碰到 OI 水平下滑 $\inf$。

  • upd：听说 NJ S 分数线 $65.5 \text{ pts}$？那我应该过了 $:)$

  • upd：听说 SZ S 分数线 $75 \text{ pts}$？那我应该寄了 $:($

估测像 YC 这样的弱市分数线会在 $[57,70]$ 之间。

Day -35 （ $\textit{2022/9/23}$ ）

$\text{Phigros}$ 更新了，但没时间打 c.s.q.n. 和 Brave Notes，先摆一会，等周末去摸一把试试。

打 船 AT $\text{rks}+0.01$。

打 RESSiSTANCE $\text{rks}+0.01$。

FC You are the Miserable AT $\text{rks}+0.01$。

$\text{rks}\ 15.25$。

Day -34 （ $\textit{2022/9/24}$ ）

更新了 $\text{Phigros}$，打了一把 c.s.q.n. ，初见 $\texttt{896767 A}$。

从教练口中得知 S 考了 $76.5 \text{ pts.}$ 应该能过线吧。

在 $\textit{13:01}$ 的时候发现有一场月赛 【LGR-121】洛谷 9 月月赛 II & NR I Div.2，花了十分钟把 A 切了然后去上学力

  • upd：做法是假的，数据弱了。

Day -33 （ $\textit{2022/9/25}$ ）

市选了。

$\textit{8:00}$ 开题，发现 T1 T2 都是萌萌题，sort+模拟就行了，码量不超过 $\texttt{300B}$。

T3 是一个 bfs 走迷宫+十字形统计的题（$m$ 与 $n$ 同阶），写了个 $\Theta(n^3)$ 暴力，一次测样例就过了，然后发现 $n,m \le 2000$，开始优化。

大概在 $\textit{10:00}$ 的时候把优化做法写完了。二维前缀和上二分，把复杂度降到了 $\Theta\left(n^2 \log_2 n\right)$。发现极限数据大概是 $4e8$，感觉要寄。

T4 完全不会，写了个 $O(nk^n)$ 的暴力跑了（注：$n \le 10^5,k \le 10^4$）。

回头看 T2，发现要开 long long，然后开了。

最后的半个小时全在拍 T3 的暴力做法和二维前缀和做法，发现后者在绝大多数情况比前者劣，在极限情况比前者优很多，卡了一波常。

预计得分：$100+100+80+10=290 \text{ pts.}$

考完后问了一下 rym,xzl,lx 等人，发现他们 T3 都写的暴力，然后我想了想，随机数据下暴力真的比优化快，暴力 $\Theta (nm)$ 的部分跑不满，优化 $\Theta(\log_2 n)$ 的部分必跑满，而且常数还大。

  • upd：感谢 @GaryGe 提供的 $\Theta(nm)$ 做法，orz。

感觉要寄。

Day -32 （ $\textit{2022/9/26}$ ）

还有一天 CCF 就要公布官方成绩了！

可惜还要上学（悲

rym 打算明天早上九点拿老师手机查分数，很慌，但应该能过线。

Day -31 （ $\textit{2022/9/27}$ ）

早上九点没查到 S1 分数，然后发现 JS 下午才发分数 /oh

S 过力 /hsh

Day -30 （ $\textit{2022/9/28}$ ）

化学周练 $69 \text{ pts.}$（满分 $70$），原因是高锰酸钾制取氧气实验寄了一题，/oh。

物理小题寄了一堆，原因是自己脑抽了，/hsh。

市选 T3，欢迎爆切/bx

Day -29 （ $\textit{2022/9/29}$ ）

啥事都没干。

Day -28 （ $\textit{2022/9/30}$ ）

发了 $20$ 多张卷子，写不完了啊啊啊啊 /kel

打 Cthugha IN $\text{rks}+0.01$。

Day -27 （ $\textit{2022/10/1}$ ）

Day -26 （ $\textit{2022/10/2}$ ）

写完了ODT 学习笔记。

Day -25 （ $\textit{2022/10/3}$ ）

在 $\tt CP$ 的要求下，vp 了 2021 CSP-S。

AC T1 之后就不会了。

下午参加了 【LGR-122】洛谷 10 月 CSP-S 模拟赛。

开题。发现 T1 好像要用线段树维护，然后写了线段树。

过了 $30\ \text {min}$ 发现写的东西很冗长，删了重构了。

花了 $1\ \text h$ 过了 T1 大样例，用了 __int128 ,可能会挂。

T2 不会，T3 不会，T4 不会。

估分：$100+0+0+0=100$。

实际：$35+20+0+0=55$。

T1 挂惨了，没判区间长度 $\ge 30$ 然后爆 __int128 了。

怄火。

Day -24 （ $\textit{2022/10/4}$ ）

在 $\tt CP$ 的要求下，vp 了 2020 CSP-S。

AC T2 之后就不会了。

下午参加了 JRKSJ 的比赛 Round 6 Div.2。

A 秒了。B 交互题，什么混乱邪恶。C 看了下，感觉可做，懒得写。D 不会。Ex 看了下，暴力拿了 $20$。

$100+20+0+0+0=120$。

Day -23 （ $\textit{2022/10/5}$ ）

上午打了 「DTOI」Round 2 - The Star

花了半小时切了 A，送分送到位好评。

然后开 B。发现 B 似乎有什么神秘的性质，推了半小时什么都没推出来，交了发暴力拿了 $2 \text{ pts}$。然后暴力打了 $1 \sim 100$ 的表，发现 $f(x)$ 在某段区间里都是相同的，然后 $f(x)$ 单调不减。然后就二分搜索 $f(x-1)<f(x)$ 的 $x$，dfs 回溯时统计就行了。拿了 $30 \text{ pts}$。

想了很久，觉得记忆化可能会有用，写了记忆化，艹过了 $70 \text{ pts.}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
inline ll f(ll x){
	return floorl(sqrtl(sqrtl(x))+0.5);
}

ll binary_search(ll n){
	if(mp[n]) return mp[n];
	ll l=0,r=1e18,ans=0;
	while(l<=r){
		ll mid=(l+r)>>1;
		if(f(mid)>=f(n)) r=mid-1,ans=mid;
		else l=mid+1;
	}
	mp[n]=ans;
	return ans;
}

ll dfs(ll n){
	if(n<=1) return 0;
	if(mp_ans[n]) return mp_ans[n];
	ll f_x=binary_search(n);
	ll x=dfs(f_x-1);
	ll a=f_x,b=binary_search(f_x-1);
//	cout<<x<<' '<<f_x<<' '<<binary_search(f_x-1)<<endl;
	if(b==0 || f(b)==0) return 0;
//	cout<<(a-b)*(1.0/f(b))<<endl;
	mp_ans[n]=x+(a-b)*(1.0/f(b));
	return x+(a-b)*(1.0/f(b));
}

貌似复杂度是 $\Theta(T\times \sqrt[4]{n}\times \log_2n)$ 的。不会优化，遗憾离场。

$\text{Total：}100+70+0+0=170$。 $\text{rk 44}$。

下午只见

和

$\mathbf{504\ Gateway\ Time-out}$

$\text{The gateway did not receive a timely response from the upstream server or application.}$

$\rule{300pt}{0.5pt}$

$\text{Powered by Tengine}$

你谷日爆。

Day -22 $\sim$ -15 （ $\textit{2022/10/6} \sim \textit{2022/10/13}$ ）

摆。

  • upd on $\textit{2022/10/9}$：明天学校月考，寄。
  • upd on $\textit{2022/10/11}$：被班主任因为打扫不认真罚写检讨然后抄中学生守则了 /oh /hsh

Day -14 （ $\textit{2022/10/14}$ ）

月考年级 $\text{rk}\ 1$。

滚去学 $\text{Splay}$ 了。

用 $2$ 小时终于敲完过模板了。

Day -13（ $\textit{2022/10/15}$ ）

Splay 学习笔记。

去做 CF 好题 了。

下午打了 【LGR-123】洛谷 10 月月赛 I & CoE 挑战编程 V Div.2。

A 模拟秒切（吹爆 std::to_string 和 auto）。

B 不会。试着输出 $1 \sim n $ 拿了 $30 \text{ pts}$，然后口胡了个 dfs 序切掉了。

C 不会，觉得 Div 2 出两道图论略显离谱。然后

1
2
print(1)
# Cheat some pts plz

骗得了 $10 \text{ pts.}$

D 不会，然后有理数取余也不会。然后

1
2
3
4
5
6
7
#include<bits/stdc++.h>
int n;
int main(){
    std::cin>>n;
    if(n==1) std::cout<<0;
    else std::cout<<-1;
}

骗得了 $8 \text{ pts.}$

然后看才打了 $48\ \text{min}$，去做作业了，摆烂。

$\text{Total：}100+100+10+8=218$。 $\text{rk 328}$。

晚上随便摸了一把 Stasis IN，没想到就 φ 了（$+0.02$）。

几个月的怨念解除！

Day -12（ $\textit{2022/10/16}$ ）

上午考了等级考试，考完之后觉得是 trash。

考完之后摸了一把 Don’t Never Around，成功 4g FC，$+0.01$

Day -11 $\sim$ Day -10（ $\textit{2022/10/17} \sim \textit{2022/10/18}$ ）

无事发生。

Day -9（ $\textit{2022/10/19}$ ）

我我我草草草草，放学回家随便摸了一把杀了 DNA （$+0.01$）

Day -8 $\sim$ Day -7（ $\textit{2022/10/20} \sim \textit{2022/10/21}$ ）

颓废。

Day -6（ $\textit{2022/10/22}$ ）

打了场 ABC，ABC 秒切，一直再做 D 和 E，然后赛时一直 WA，赛后发现一个是 dp 一个是状压 dp

$\texttt{:}\kern{2pt}\raisebox{-1pt}\texttt{)}$

Day -5（ $\textit{2022/10/23}$ ）

上午打了 【LGR-124】洛谷 10 月 CSP-J 模拟赛 & JROI R8，A 循环节，B 构造。

C 想了个自以为很妙的贪心，把负数放第一个 $\texttt{[]}$，正数放最后一个 $\texttt{[]}$，然后连续整数平方和就完事了。赛后挂至 $60$。核心代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void Solve(){
	auto func = [&](int l,int r,ll k) -> ll{
		ll x=0;
		F(i,l,r) add(x,(a[i]+k)*(a[i]+k)%mod2);
		return x;
	};
	auto calc = [&](ll p) -> ll{
		return (ll)p*(p+1)*(2*p+1)/6;
	};
	read(n,k);
	F(i,1,n) read(a[i]);
	int pos=upper_bound(a+1,a+n+1,-1)-a;
	if(k==1){
		write(func(1,n,1));
		return;
	}
	ll ans=func(1,pos-1,1)%mod2*k%mod2;
	F(i,pos,n) {
		ll p=a[i]+k,q=a[i];
		ans=(ans+calc(p)-calc(q))%mod2;
//		write(calc(p),' '); write(calc(q),'\n');
	}
	write(ans);
}

$\text{Total：}100+100+60+0=260$，$\text{rk 176}$。

Day -2

JS CSP-S 取消了。（$\text{upd}$：最后并没有取消）

后记

终究还是错过了这次的 CSP-S 和 NOIp，话说回来，参加了也就抱个 $\text{2= or 3=}$吧（笑）。

半退役状态。