CSP 2021 退役记

· · 个人记录

\texttt{2021.9.19}

初赛日。

早上是提高组。

拿到卷子：

  • 再一看，是四毛子，没学过/kk

好，果断选择靠人品。

除了考场，果然自测只有 50+ 但是看到大部分人说分数线会低，我又有了希望（，要退役了/kk

下午是普及组，就随便考了几下（）

由于考得很差，个人觉得要退役了/kk，没救了。

\texttt{2021.9.28}

苦苦等待了 10 天，CCF 的不断咕咕咕终于是出了成绩（

结果——

怎么说，积攒了千年的人品终于爆发了（

退役先暂告一段落（

准备复赛了。

复赛的主要目标就是拿提高一等奖，以及获得 NOIP 的资格 awa，但是去年因为一些奇怪的原因（/fn）导致连绿勾都没有/kk，所以今年的普及组可不能再翻车了（

\texttt{2021.10.21}

去做核酸。

有亿点小风波（

然后就做完了。一路上十分担心会因为健康码导致今年又参加不了 CSP。

综上所述，是老天眷顾我。话说老天应该会给我个 tg1= 吧（雾

\texttt{2021.10.23}

早上打 J 组。

首先大概看了一眼题，A 大概知道怎么做了，B 一时间还没思路，C 一眼大模拟，D 链表（但是我忘了链表怎么写啊！！！）。

果断先开 A 题。

看到 r-l \leq 10^9，就不能 \text{O}(r-l) 了。容易发现，最大的可能奖励值为 n-1，然后就看 [l,r] 这个区间有没有跨过 kn-1 了。比较一下 \dfrac{l}{n} 和 \dfrac{r}{n} 的大小，如果相等则取 r \%n，否则是 n-1。5 min 就打完了。

然后看 B，一开始写了个 \text{O}(qn) 的代码，知道复杂度过不了，但是想了 20 分钟还是不会，然后就跳过了。

做 C。C 就是一个大模拟，大概 30 分钟写完了代码。然后开始对大样例。

然后肉眼对拍 n=1000 的数据，拍了可能有一个小时（？），中间遇到了各种各样奇奇怪怪的问题，一点一点修改着代码。最后对了 1000 组数据中的 700 \sim 800 组数据，没发现问题后就跳过了，转回去想 B 题了。

B 题分析大概的复杂度是 \text{O}(5000n+q)，然后就想怎么在每次修改时得知其他值对应的位置。然后就想到了预处理答案 ans[]，先 n^2 求出修改前每个数的位置。然后每次修改的时候 \text{O}(n) 推出更改这个数后给其他数带来的贡献。花了 20 分钟打完了。

然后对第二个样例时，发现有个答案是 10 我输出了 0，很慌，以为是哪里推错了。后来发现是快读中的 if(x>=10) write(x/10); 写成了 if(x>10) write(x/10);，改完就对了。然后又对了大数据，没发现问题。

至此估分 100+100+100+0=300。

最后 30 分钟才正式去做 D。由于时间不够了，就没认真打，于是打了个 \text{O}(n^2) 的代码就交了。大概有 70 分？

出了考场，估分 100+100+100+70=370，感觉良好。

中午去吃了麦当劳，写了会儿作业，睡了会儿觉，感觉还行。然而事实并非如此。

下午打 S 组。

还是大概看了一眼题，发现 D 题十分不可做，暴力都可能没分。于是不打算做 D 题了。

去做 A 题，马上写了个 \text{O}(n^2\log n) 的奇妙做法，后来将近 2h 专门想怎么写优化。然后没想出来/kk

看到时间过半，果断开下一题 B，看出来是个很 sb 的 dp，但是设计状态设计错了，推了半天没推出来。f[i][j][k] 表示前 i 个字符种有 j 个 *，k 个 ) 的方案数。没推出来，果断写了个 dfs，但是发现 dfs 的 check 写错了，但是懒得改了（

看了眼 C，发现很鬼畜（赛后就切了啊啊啊！！），盲猜了一波性质：如果一个串是符合条件的，那么这个串反过来后也是符合条件的。但是这个条件是错的。于是我傻傻地默认第一位为 L，然后 dfs 找答案。就在自己的迷惑下写出了十分迷惑的代码（），赛后测的一分没有（如果我好好写 dfs 也有 28 分啊！！）。

D 不会，直接输出随机数（

以下内容为 GD 出代码后的经历：

J 组：A 没问题。

B：

long long write(long long x){
    if(x>=10) write(x/10);
    putchar(x%10+'0');
}

没错这就是我的迷惑快写。据说 无 void + 无 return + O2 = UB。还我 100 分！！！！！！

C 题洛谷上测的是 100 分，但是我知道数据水了。

D 题：

原本写了个数组 L[],R[] 维护第 i 块水果的左右端点，后来写暴力时发现这些没用，然后就删去了 int L[],R[]。

但是，我在主函数里还是用了 L 和 R。

自然也是 0 分了。。

J 组：370 \to 200，挂大分/kk

S 组就别说了，40 分顶天。（或者 C 题的 dfs 和 D 题的 rand 能救我一命？）

基本退役了。

希望还能打 NOIP。