CSP-S 2021 游记

Day -35

提高组初赛。

竟然只有一道 Linux 命令题。(巴不得全考 Linux 命令)

base64 其实不难理解,然而自己实在是不想模拟解码 (实际忘了 ASCII 码表),随便蒙答案。

从来没接触过笛卡尔树,然而还是勉强看懂了。

Day -3?

出成绩了。89.5pts。

Day 0

wyz,gc,Eason 打摆被抓(默哀)。

我不会说是 wyz 问我 super mario 在哪里能玩的

幸好只是看了些文字类的东西,幸免于难。

高情商:看学术文章 低情商:看知乎娱乐

Day 1

睡得还不错。

下午来到湖大。

在候考室打量了一下机器,Pentium CPU,2013年(跟我家 G630 有得一拼),难道这就是我们要用的机器?/jk

然而,到了四楼,竟然是工作站!虽然比较老了 (E3-1220v2 (4C4T),8GB),但显示器竟然是 1080p 的(比我们学校机房好不知道多少倍)

顿时信心十足。

14:30 ~ 15:30

先看 T1。一个单增,一个单降,加起来应该是个凸函数。

30min 码完三分,对拍,成功 WA on 1。

后来仔细想了想发现这貌似不能三分,好像不是凸的。

然后有点慌了,通过告诉自己“这是 T1,不会那么难”稳住心态(忘记儒略日了吗)。

自己手动模拟,猜了个结论,然后居然过了样例,对拍 \(10^4\) 也没出错。

总算 100pts 了。

15:30 ~ 17:00

看到括号序列,再看数据范围,显然是区间 DP。

但是它的定义比较复杂,于是直接设 \(f(l,r)\) 开干。

发现是 \(O(n^4)\),但好像可以后缀和优化,先写了再说。

写写写,发现第二个样例过不去。

发现 \(\texttt{()()()}\) 会重复算,于是枚举第一个括号配对的哪一个括号。

发现还是过不去,貌似还要设个 \(g(l,r)\)。

调调调,总算把 \(O(n^4)\) 调了出来。

最后加了个后缀和优化。

17:00 ~ 17:45

T3 一开始没什么思路,但后来发现似乎有些性质。

假设选出了最终在 \(i\) 和 \(2n-i+1\) 位置上的数,那么要求 \(i+1\) 和 \(2n-i\) 位置上的数与前一个数在 \(a\) 序列中相邻。

然后貌似是会被卡的,但还是好写。

预计 \(O(2^n)\),最多也就 40pts 吧。

17:45 ~ 18:20

T4 这个模型,一开始以为是贪心什么的,但越看越感觉是文理分科。

手玩了一个网络流模型,这最小割不是 \(0\) 吗?好像哪里不对……

结果发现没有附加点时本来答案就是 \(0\)…… (喷血)

赶快码码码,有前人的事迹激励(指 wyz 模拟考激情 10min 网络流),一测,\(\texttt{global-buffer-overflow}\)…… 哦没有初始化,那没事了。

样例一遍过,还好,虽然最后一个样例跑了 18s

18:20 ~ 18:30

检查文件,又测了一遍样例。

结束了。

Day 2

心血来潮,测一波代码。

幸好这次没有像上次一样重蹈覆辙,(似乎)没有挂分。

估分:\(100+100+40+60=300\)
InfOJ:\(100+100+88+80=368\)
洛谷(民间):\(100+100+92+60=352\)
CCF:\(?+?+?+?=?\)

(我 T3 怎么骗了这么多分?感觉 rp 被提前用光,NOIP 危)

等官方成绩出来了再更。

上一篇:CSP-2021 游记


下一篇:【说句闲话】CSP 2021 的总结与反思