TheSky233's Blog

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

0%

CSP-S 2023 游记 / Final Verdict.

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

CSP-S 2023 游记 / Final Verdict.

真的是最后一次了。

四年的 OI，也该有个终点。

又有一位同机房好友与 OI 渐行渐远了。

还有好多想说的 先写到这里吧。

怎么好像把游记写成日记了。

Day -48 / Day -13 $^\texttt{2023/9/2}$

  • 开坑。

Day -47 / Day -12 $^\texttt{2023/9/3}$

  • 下午开学，怎么会是呢。

  • 决定每天晚上刷一套初赛卷。

  • CSP-S 2020 ✔ $\quad \text{64 pts.}$ $\quad$ 其中快速排序的那题复杂度全错，废了。 $\quad$ $^\texttt{2023/9/3}$

  • Amnéhilesie 怎么这么好听。

Day -46 / Day -11 $^\texttt{2023/9/4}$

  • 看了眼初赛书从组合数学到离散数学的那部分。

Day -45 / Day -10 $^\texttt{2023/9/5}$

  • 做了份初赛卷，感觉还行啊。

  • 阅读程序居然是数位 dp，一眼没学过 /fn

Day -44 / Day -9 $^\texttt{2023/9/6}$

Day -43 / Day -8 $^\texttt{2023/9/7}$

  • 做了一套 S 组初赛模拟卷，$90 \text{pts}$，怎么会是呢？

Day -38 / Day -3 $^\texttt{2023/9/12}$

  • 做了套初赛卷。$86.5\text{pts}$。

Day -36 / Day -1 $^\texttt{2023/9/14}$

  • 花了一个晚自习的时间复习了一下有关「主定理」「组合数学」「计算机基础知识」的部分。RP++。

Day -35 / Day 0 $^\texttt{2023/9/15}$

  • 祈祷能过初赛。

Day -34 $^\texttt{2023/9/16}$

  • 初赛。

  • 上午学校请了半天假，用来放松一下心情，还和同学玩了会 Wordle 和 Numberle。

  • 下午去考初赛，刚去就没绷住。

  • 开考。

开幕雷击。怎么一开始就是个 Linux 命令，还好开考前看了一眼，mkdir。

然后组合数学也给我气笑了。$4 \times 4 \times 3 \times 2$ 真的好难。

然后染色那题脑抽了。一时没想到树形结构都能染色，后悔的要死。

快速幂那题是真没想到。合着主定理出现在这。

$T(n)=2T\left(\frac{n}{2}\right)+O(1)$。$\log_ab=1>c_{crit}$。复杂度 $O(n^{\log_ab})=O(n)$ 的快速幂诚不欺我。

然后接下来的阅读程序做的挺顺的，也没考字符串。

T1 是个位运算。手算即可。unsigned 别忘溢出。

T2 是个神奇的埃筛。$f_n$ 是 $n$ 的最小质因数，$g_n$ 没看懂。但是不影响做题。手模一下然后就不难了。问时间复杂度更是重量级。此项全对。

T3 是个神奇的二分。好像是在求子段之和 $\le p$ 的子段数量不少于 $k$ 的最小 $p$，手模。

完善程序第一题是个挺典的 DAG 计数。$4 / 5$，还错了一个空，怎么会是呢？

第二题是个分治求子序列最大值之和。$0 / 5$，我也有点佩服我自己。

话说我最后一分钟改了两题。一题 $-2$，一题 $+3$，不亏。

小图灵估分 $63.5$，大抵是能过的了吧。

Day -29 $^\texttt{2023/9/21}$

  • 凌晨补习 whk 内容，总之在复赛之前 whk 别出什么问题。

工业制氯气：

实验室制氯气：

氧化钠：

  • 银白色。
  • 与水反应生成氢氧化钠，与二氧化碳反应生成碳酸钠。

过氧化钠：

  • 淡黄色，与 $\text{AgBr}$ 和 $\text{S}$ 一个颜色。
  • 与水和二氧化碳反应都生成氧气。$2\text{Na}_2\text{O}_2+2\text{CO}_2\xlongequal{}2\text{Na}_2\text{CO}_3+\text{O}_2$

溴：

  • 卤素，易挥发。
  • 氧化性：$\text{Cl}_2>\text{Br}_2>\text{I}_2$
  • 海水提纯：
    • 母液通氯气。$\text{2Br}^-+\text{Cl}_2\xlongequal{}2\text{Cl}^-+\text{Br}_2$
      • 热空气吹出（易挥发）。
      • 用含 $\text{SO}_2$ 吸收液吸收溴蒸汽（富集）。$\text{Br}_2+2\text{H}_2\text{O}+\text{SO}_2\xlongequal{}\text{H}_2\text{SO}_4+2\text{HBr}$
      • 再通氯气，四氯化碳萃取，蒸馏。
      • 用碳酸钠吸收的太逆天了，Click here to learn more。

Day -28 $^\texttt{2023/9/22}$

偶然又点开了群青，真的很感慨啊。

去年的新年打 「Cnoi2021」Cirno’s Easy Round II（也是印象最深的一场 lgr） 的时候就是在听着这首歌，打了 rk#44 的成绩，现在再也没打过这么高的 rk 了。

下午教练把我们喊过去了。知道能过线但是没想到没想到分数线才 $52.5$，这下得认真搞复赛了。

Day -27 $^\texttt{2023/9/23}$

Arcaea 的 ptt 到 11.8 了。

$\text{Aphasia - Team Grimoire}$ 的 Phigros 自制也写到差不多 $40\%$ 了，头大。

Day -14 $^\texttt{2023/10/6}$

这期间摘星了。

  • 打算速速写完所有学过的东西的模板
  • 学习 Linux 对拍命令

Day -5 $^\texttt{2023/10/15}$

写模板。

$\textsf{\textbf{Link}}$

https://githubfast.com/argvchs/algorithm

Day -1 $^\texttt{2023/10/19}$

  • 调了一个晚上的 Splay 代码竟是因为查后继的时候 < 打成 <=，我的评价是不会 Splay 可以不写。

Day 1$^\texttt{2023/10/21}$

下午一点半进场，两点试机。试机的时候把缺省源打了，然后 NOI Linux 上的 Code::Blocks 还死了一次，用 pkill codeblocks 才退掉的，难绷。

然后两点半发了解压密码，开题。

先把第一题看了，第一题 lock 看着题面感觉为什么这么难，搞不好又是数学什么的，一大堆，想了十分钟之后想通了，去看了眼数据范围骗分，然后惊讶地发现 $n \le 8$，这下 $\Theta(10^5 \times n)$ 暴力直接上了。写完大概过去了半个小时。

接着我看了下剩余的三题想看看哪一题更好拿分，发现 game 一眼是个 $O(n^3)$ 的区间 dp，发现能过 $n \le 8000$ 的 $35$ 分，这下直接上 dp。然后 dp 写挂还调了大概二十分钟。写完大概是 3:45 了。

然后看了眼 T3 struct，发现是个大模拟，当时直接想吐口血在键盘上。CSP-S 出大模拟搞区分度是吧。先开 T4 tree。

发现 T4 完全没有思路啊。有点像个树形 dp。不管怎么样先把链的 $10$ 分拿了。然后写链又写了半个小时。回头看 game。

觉得 $O(n^2)$ 的外层循环和 $O(n)$ 的内层枚举中间点不能再少了啊，看来正解应该不是区间 dp 了。开大模拟。

先开了性质 A。如果没有结构体的话就会非常简单。来一个变量就 push_back 进 vector 即可。

然后看性质 B。觉得 B 也很好写啊。如果定义了一个结构体 a 里面成员有 e f 然后定义了 a b 那就直接把名字命名为 b.e b.f 就行了。然后我以为定义结构体也占空间，考试结束之前 45 分钟才看出来，wssb。

最后看性质 C。其实就是在 B 的基础上加了可以定义结构体，并且保证不会出现结构体套结构体的情况。改了几行就调过了。

然后手造了几组小样例，跑的都没什么问题。去看看 tree 还有什么能骗的了。发现 $c=0$ 似乎能骗。然后发现根本骗不了。输。

考试结束 5 分钟的时候记了字节数。发现代码长度 T1 + T2 + T4 < T3 难绷。

估分：$100+35+[0,65]+[0,10]=[135,210]$。

实际：$100+35+0+0=135$

sb T3 题目读错了，nm。