CSP-S 2022 游记 / Black Fate.
TheSky233
·
·
生活·游记
前言
话说回来，初赛没过就真的止步于此了。
# 登场人物介绍
- xzl，指 [XZL_Jerry](/user/375590)，同校大佬
- rym，指 [rym20080301](/user/480495)，同校大佬
- lx，指 [LXGOD](/user/484955)，同校大佬，[他的游记链接](https://www.luogu.com.cn/blog/LXGOD/post-2022-you-ji)
# 省流
- [**CSP-S 2022 S1**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/9/18)
- [**模拟赛**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/9/25)
- [**【LGR-122】洛谷 10 月 CSP-S 模拟赛**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/10/3)
- [**JRKSJ 的比赛 Round 6 Div.2**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/10/4)
- [**「DTOI」Round 2 - The Star**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/10/5)
- [**【LGR-123】洛谷 10 月月赛 I & CoE 挑战编程 V Div.2**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/10/15)
- [**【LGR-124】洛谷 10 月 CSP-J 模拟赛 & JROI R8**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/10/23)
- [**CSP-S 2022 S2**](https://www.luogu.com.cn/blog/501865/csp-s-2022-travel-notes#:~:text=2022/10/28)
# 正文
## 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 组，先摸半天的鱼。
闲话：听说上午 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 组自测 之后的感想：
## 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} ）
打 *船 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} ）
-
树状数组复建
-
Kruskal 复建
-
学了 ODT，做了
-
模板题 CF896C Willem, Chtholly and Seniorious。
-
另一道模板 SP19568 PRMQUER - Prime queries。
-
比上一道还简单的模板 SP13015 CNTPRIME - Counting Primes。
-
rym S1 没过，sad。
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。
## Day -23 （ $\textit{2022/10/5}$ ）
上午打了 **「DTOI」Round 2 - The Star**
花了半小时切了 A，送分送到位好评。
然后开 B。发现 B 似乎有什么神秘的性质，推了半小时什么都没推出来，交了发暴力拿了 [$2 \text{ pts}$](https://www.luogu.com.cn/record/88637460)。然后暴力打了 $1 \sim 100$ 的表，发现 $f(x)$ 在某段区间里都是相同的，然后 $f(x)$ 单调不减。然后就二分搜索 $f(x-1)<f(x)$ 的 $x$，dfs 回溯时统计就行了。拿了 [$30 \text{ pts}$](https://www.luogu.com.cn/record/88652619)。
想了很久，觉得记忆化可能会有用，写了记忆化，艹过了 [$70 \text{ pts.}$](https://www.luogu.com.cn/record/88653240)
代码：
```cpp
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{502\ Bad\ Gateway}$$
$$\rule{100pt}{0.5pt}$$
$$\text{nginx}$$
和
$\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 出两道图论略显离谱。然后
print(1)
# Cheat some pts plz
骗得了 10 \text{ pts.}
D 不会，然后有理数取余也不会。然后
#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}，去做作业了，摆烂。
------------
晚上随便摸了一把 *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。核心代码如下：
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);
}
## Day -2
JS CSP-S 取消了。（$\text{upd}$：最后并没有取消）
$$\text{AFO}$$
# 后记
终究还是错过了这次的 CSP-S 和 NOIp，话说回来，参加了也就抱个 $\text{2= or 3=}$吧（笑）。
半退役状态。
$$\text{semi - AFO}$$
------------
[$\leftarrow$ _**Previous**_](https://www.luogu.com.cn/blog/LByte/post-training-nanjing)
[$\rightarrow$ _**Next**_](https://www.luogu.com.cn/blog/LByte/csp-s-2023-final-verdict)