CSP2023复赛游记
allenchoi
·
·
生活·游记
超级大 FW 的游记...（初赛游记点这里）
Day -???:
学校运动会结束就开始中秋国庆，从那时开始停课，基本就是每天模拟赛，中午摸大鱼，下午改题然后打球，校内 whk 只卷了些数学（其实还有一些特殊原因？）。
Day -??:
被叫回学校体检。
Day -?:
得知体测不在 10 月。
Day 0:
早上先水了几道期望 DP 简单题，再看了看去年提高组 T4 正解。这个时候高中生体检完回来了，于是一起颓大废。中午吃完饭后又颓了一阵，然后回家（怕太晚走堵车）。一边颓废一边复习真题 & 板子，睡觉前听了 《那些年》，《海阔天空》，《不再犹豫》。
Day 1:
上午打 J 。本部初三的只有 hyt 去，我因为一些奇怪的原因没拿过一等所以也去打。考前聚了一些人在六中门口相互膜拜，并发现和 yhj 一个考场。看见 lxy,lln（ts） 和 ts 一个不认识的初三女生在一个考场。
T1 光速切。 T2 感觉是个贪心，就是每次找下一个油价更小的，打了个单调栈（超纲？），然后用 double 维护剩余油量 调了半个钟。
看了眼 T3 ，然后感觉是良心打磨你，于是再去看 T4。
T4 似乎是个套路题，建反图，拆点，二分答案然后 BFS 最短路。很快写完，然后发现过不了样例，看了很久，甚至向监考员发问是不是题目错误，结果发现原来进入和离开时间都要是 k 的整数倍。改了马上就过了。
T4 就照着题意乱打，没啥好说的。
打完还剩 2h ，随便 check 一下，然后睡大觉、玩小恐龙、在注释中默写歌词。
中午就在附近的快餐店随便吃点，然后在附近找了个地方睡午觉。
———————————————————————分割线—————————————————————
下午打 S ，一点半多一点起床，考前和各队互拜。
T1 好水啊，像普及题。
T2 看起来很典，然后一点思路都没有。
过了一阵子看出是一个栈，又过了一阵子想出了一个基于栈的优化过的算法：
把左端点从有往左扫，每次初始令 $j=i$ ，当 $s_{j+1} \ne s_i$ 时就一直跳到 $p_{j+1}$ ，最后 $p_i=j+1,f_i=f_{j+2}+1$ 。
$O(?)$ ，应该能过特殊性质，结果打完后竟然把大样例过了?（赛后才知道这样复杂度是对的...）
想了下如何改进：每次跳实际上是走一条链，那么令 $l_{i,j}$ ，表示以 $i$ 为起点的一条链上是否存在 $s_{j+1}=s_i$ ，存在则记录 $\min{j+1}$ 。
每次把 $l_i$ 从 $l_{p_{i+1}}$ 处复制过来，然后把 $s_{i+1}$ 加进去。
则 $p_i=l_{i,s_i},f_i=f_{p_i+1}+1$ 。
$O(n\sum)$ 可过！！！但是不知道 5e7 的空间开不开的下，于是用 vector （伏笔）。
T3 又是打磨你，做了 1h 样例都过不了， wssb ，T4 随便打了个暴力，目测 0pts 。然后时间还剩一丁点，开摆了。
———————————————————————分割线—————————————————————
考完后，听到好多人说差点调处 T3 （[若干天后发现我也是其中之一](https://www.luogu.com.cn/record/list?pid=P9754&user=298037)），还说 T2 是哈希、回文串啥的，怕...
[夏姐姐](https://www.luogu.com.cn/user/614527) 说自己 300+ ！！！
照惯例合了张照，回家。
老爸把车停在单位楼下，于是坐地铁到珠江新城，随便找了个地方吃了饭，然后在花城广场散步，看到许冠杰的演唱会！！！
8 点多开车回家。
回家后光速默写出 T2 代码，结果跑样例输出完直接卡死了！！！
但是交到洛谷 A 了？？？
检查了一下发现是加 $s_{i+1}$ 的时候没判 $i<n$ ，导致访问到了负数（ $i+1=n+1$ 时），悲愤，怒骂 windows 环境，哭泣嘤嘤嘤，感觉要 200->100 了...
在群里发问，结果有大佬说用 vector 还开 O2 多半没问题，而且过了一会，小图灵跑出来是 RE95 ，上云斗交甚至 100 ？？？
跟 lq 立个 flag ，如果 7 级勾就晚自习开演唱会（~~反正他也不在，我唱不唱他都不知道~~）。
太累了，睡大觉。
# Day 2:
哪里有 Day2 ？记录一下白兰时刻而已了。
一天都在看视频（有个元首怒骂 CSP-S2023 的）、打游戏，然后群里有人发了不知道谁跑出来的榜（听说云斗，但自己交是 200 ）， 205 ，省排 175 ？？？震惊...
结果中午（下午？）饮茶的时候小图灵跑完了， 195 省排 201 ？？？
据说 7 级线 170 多（...）
吃完就回家睡大觉，口胡一下 T4 （二分乱搞啥的），晚上请个假 10 点后再回去，走之前没事干就写下了这篇游记。
# 总结：
这次可能是策略有问题了，可能是模拟赛不大注重这方面。没有仔细 check ，而且在 T3 上浪费了大量时间，导致 T4 一道较为简单的题（而且好像在模拟赛做过有点相似的？）一分没骗到。最最重要的还是要进一步提高自身的实力，认真练习。
回去学 whk 咯
### upd: 1029 GD出分了
J400，S200（不过 JT2 在 lg 上是 95 的）
全种上，养护员！
### upd: 出分推到 11.20（NOIP）之后
### upd: 11.15 出分数线
GD J1= 210,S1=150，喜
sunny 大佬 S 组极端压线，牛的。