游记 - CSP 2021

友情链接

CSP-S 2021 游记 - lzqy_

CSP2021 J/S复赛游记 - mod998244353

CSP2021游记 - fffngzzh

---

初赛篇

---

DAY -1

2021.9.18.

历史步步高砸了，但是换回了一个小憩，哈哈。

---

DAY 0

2021.9.19.

和 一个外校神仙OIer 和 一个同校OIer 同车去。

MORNING: SENIOR

做题有感

《计算几何》

《手动编码》

《Four Russians》

《笛卡尔树》

发出恶臭的声音。

画外音

估分 70.5。悬。

---

AFTERNOON: JUNIOR

做题有感

$61 \times 3$ 算成 186 可以卡多久……

字符串编码跟上午相似，简单一些。

“c.s.q.n.”

画外音

估分 90.5。要没。

上午的分赛区写了“广州”，下午写了“广东”，应该不影响。嗯。

黑笔居然没水，把我急的。还好老师有借我一支笔。老师真好。

和 一个外校神仙OIer 和 一个同校OIer 同车回。

---

DAY +N

2021.9.22.

Junior: 93.5

Senior: 70.5

广州市 Junior 初赛 第一？

---

复赛篇

---

DAY -1

2021.10.22.

开了个赛前的会儿，合了个照，A了个树形DP，比较轻松。

据说我长得比一些高一的还高？

---

DAY 0

2021.10.23.

MORNING: JUNIOR

策略第一，先断顺序：

1,3,4,2.

T1

发现结果最大是 $K - 1$。 如果不可能是 $K - 1$，那必然是 $R \bmod K$，因为 $L \le R$。

核实一下结论，差不多，写完代码，下一题。

T3

轻松地模拟。按他的定义，一项一项来，先看整体格式（是不是 %d.%d.%d.%d:%d 的格式，有没有不该有的符号），再看值在不在范围内，最后看前导0，完事。

测了大样例，没问题，就不管了。

T4 想到链表/并查集，但是怎么推都太乱了，暂时搁置。

T2

一直在想应该用什么数据结构，后来打了个 $O(NQ)$，碰到一个2操作就暴力求排名。

期间明明想过 $O(5000N + Q + N \log N)$ 的正解（碰到一个1操作就暴力插入排序，2操作变成 $O(1)$），然后没写……

T4

定义 $T_i$ 为第 $i$ 个数死亡时刻。初始化 $T_i$ 为在块中的位置。

它只有两种方式推到：要么是初始化，要么就是找到 $j <= i$ 满足

$color_i = color_j$,

设有 $j + 1 <= k <= i - 1$, 则

$T_i > \max{T_k}$, $T_j > \max{T_k}$.

此时，$T_i = \max(T_i, T_j + 1)$.

可以用单调栈维护，但是没调出来，最后打了一个 $O(N^2)$。

要结束了，慌乱地删了checker，很怕不小心把自己代码删了。

估：$100 + 76 + 100 + 30 = 316$。

---

AFTERNOON: SENIOR

看了一遍题，打算顺序：

1,2,3,4.

笑死，一个都不会。

T1

感觉像单峰/双峰函数，随后写了一个类似于模拟退火的鬼东西，调了 1.5h，样例都过了，溜了。

T2

就偷偷拿个全问号的DP部分分，按照他给的每一条性质一个个来，连判重都没判，也不知道怎么核对，先溜了，又不会。

T3

性质没看懂，拿了一个回文的部分分，溜了。

T4

看 $K <= 2$ 的部分分：网络流。

调了个 Dinic。差点写挂。

一测大样例，忽然发现怎么数据那么大，部分分都不让我好好拿？？？$O(N^3M^3)$ 的网络流被卡死。$N,M \le 18$ 都很危。

上了个厕所，然后发现，还是不会啊……

估：$100 + 0 + 4 + 15 = 119$。

---

画外音

这次跟上次一个学校，但是走不同的门。

这次 DP 少的可怜，而且还都挺烦的。

洛谷估分：

Junior: $100 + 76 + 100 + 70 = 346$.

Senior: $20 + 0 + 0 + 0 = 20$.

能力不行。

Junior T4 那么高分吗？乱搞做法大胜利。

再接再厉。

外校神仙OIer，洛谷自测，AK Junior， Senior 128，%%%。

---

DAY +1

2021.10.24.

看了初三学长的博客，跟他们聊一聊。

好心痛。

这是他们初中OI的句号。

我不知道6月31号是什么特殊的日子，但是我希望你好起来。

我不知道128分能不能拿到 Senior 1=，但是我希望你好起来。

溜去做作业力。

---

DAY +N

2021.10.30.

Junior: $100 + 76 + 100 + 60 = 336$。

Senior: $30 + 0 + 20 + 5 = 55$。

现在全部高于洛谷分了。

看到学长主要也是高于洛谷分，也很开心。

上午打了把 NOIP 模拟赛，$40 + 100 + 30 + 25 = 195$。

接下来，就是为 期中，NOIP，CCPC 奋斗。

加油！

---