CSP -J/S 游记

提前一个月开坑 rp++

srds 为什么大家都考了 GESP 啊，只有我还得打初赛 QwQ

初赛

J 组 1h ak了，在准考证上写了遍题解，出来后发现算内存的题没有是求 byte 而不是字节。

S 的二分跟我平时写法一模一样，但为什么会错 3 道呢？

J: 96.5 S: 69.5

-Day -7

在 hjj 打模拟赛，成功做到口糊 ak，但是成功的在这场信心赛得了 20pts 的高分，成功垫底！

然后就停了一周课，练 tree 和 dp。

-Day 1

应老师要求考了 J 组。

上午买了一堆吃的然后就进考场了，在 JX 考点。那里分国际部和小学部，都是考点，然后我成功走反 QwQ。

8:30 开题，准备一道一道看，T1 手写了个哈希（为什么我傻到不用 STL 呢？）3min。

8:33 开 T2，按照题意模拟即可，写了个 dfs 一遍过，7min

8:40 看到隔壁小朋友疯狂调试 T1，还挺有样子的开虚拟机测样例。

8:42 T3 显然有位数越小越好的结论，所以先全填 8，剩余的部分分类讨论一下就好。但因为没有大脑，写了个 100 以内的 dp 找规律，发现还要在 20 以内特判，反正简单，16 min 写完。

8:58 不是啊，三个小时写 T4 能不会？先摆一会看看隔壁小朋友写的怎么样。

9:30 看 T4，首先有个一眼的 O(Trn^3) 的 dp，但是好似只有 10 pts，和暴力一个分？不管了写了再说。

9:40 快速注意到同一个字母结尾在不同人里出现两次以上就可以覆盖掉所有情况，所以优化成 O(Trn^2)。

10:00 发现时间瓶颈在接龙长度为 k 的区间加，直接写一个线段树上去（埋下伏笔），优化成 (Trn\log n)，15 min 写完，一测大样例要 10s 好好好好好好，又要卡常了。

10:20 发现每次遍历完整个 vector 很笨，可以直接给每个字母单独开一个 vector，在随机数据下能有个 \frac{1}{26} 的常数。可是因为每次要清空，所以实际影响不大，但还是变成了 7.8s。

10:40 发现处理相同位置大于两次的时候，要对整个桶 memset，选择用 vector 存下修改过的位置，时间 6.9s

11:15 哦哦哦哦哦，想起来 yijan 交过标记永久化减小常数，改改改，时间 3.1s。

11:45 写了个快读发现根本没用，遂放弃。

11:50 把 #define int long long删了，但因为 dp 数组是 bool，所以也没什么用，时间 2.8s

剩下半个小时对线段树的 query，update 一通瞎改，比如但单结点修改不下传，子树信息合并上传，都用处不大，最后时间 2.6s。

因为线段树可以用 bool，但是树状数组只能用 int，所以实测上两者在本题常数差不多。

出来面了所有 qzyc 的同学 wjr 好像会不带 log 的 T4，但没调出来比较可惜，但还是 %%%%%%

wxt,lyc,lzj,zqn 都会 3 到，但好像 T4 的 O(Trn^2) 都没写出来？感觉不符合大佬的实力啊。

最后估分 100+100+100+[60,100]，可惜没有 ak。

下午跟 wjr 交流做法发现他用的前缀和，然后我就发现：

为什么离线区间加，单点查我不用差分？

为什么离线区间加，单点查我不用差分？

为什么离线区间加，单点查我不用差分？

为什么离线区间加，单点查我不用差分？

为什么离线区间加，单点查我不用差分？

线段树改差分就 O(Trn) 不带 log 能轻松 A 了，为什么想不起来，为什么想不起来，为什么想不起来，为什么想不起来，为什么想不起来，为什么想不起来，为什么想不起来，为什么想不起来！

痛失 ak 了呀。

luogu 群上说难度 红红红橙？？？？？？

个人感觉 红橙橙绿 比较合适吧，但最后 T4 能评到蓝比较抽象，感觉不难啊？

- Day 1.5

去年 T3 的爆炸已经让我失去了一些自信，今年考的也只能说很一般，简单题不会正解，暴力又打不出来，再加上会线段树优化 dp 的 T3 没调出来，在初评前就先不写 S 的游记了。

upd：出了

14:26 可以看下发文件了，旁边做的事高贵的走读生 hzr 同学，与之讨论了下样例，猜了猜题目，发现并没有 tree （

14:30 开题，这个 T1 不是求最小链覆盖？一个网络流直接冲就好了，欸不对，怎么 n \le 10^5，哦哦哦原来攻击力和防御力一样，直接求区间众数就好了。这道题甚至不需要离散化 QwQ。

14:33 开 T2，注意到一个在点 P 的车，如果加速度为正且会超速，一定是在 [l,n] 中产生，二分 l 即可。如果加速度为负，则在 [P,r] 中产生，二分 r 即可。求出每一段区间后就是经典问题，按照区间右端点排序贪心即可，简单题。

14:55 写完，测大样例怎么 2.1s ? 先读入优化然后在把对 pair 用 upper_bound 二分改成手写就行了，0.3s。

15:07 开 T3，这不是一眼 O(n^2)，这就 50pts 了？怎么输！

15:31 写完过拍，顺便滚动数组优化一维。

15:59 好像会正解了，具体的，设 dp_{i,j} 表示枚举到第 i 个位置，j 位置是第一个颜色与其不同的位置。显然可以贪心的从最大值，且有 a_i=a_j 的元组转移，写一个线段树动态维护即可。

......

有 300pts 了吗？并没有，到最后也没有调出来，n \le 15 的数据半个小时拍不出问题，n=2000 又检查不了。

那 T4 呢？有白给的 28pts，写了吗？并没有，最后的一个半小时手一直发抖，最后 18:25 写完了代码，但显然没有时间调了，遗憾离场。

估分： 100+100+[50,65]+0

upd：赛后再用了 1h 就写到 100+100+100+28 了.

滚回去学 whk

-Day 8

上完无聊的whk（晚自习数据删除还骂人）回到家，打开成绩表，尘埃落地。

J: 100+100+100+60=360

S: 100+100+50+0=250

差吗？并不差，与我出场估分一模一样，一分没挂。

好吗？并不好，J 组并没有冲过极限数据，失掉了 AK 的机会。S 没有调出 T3 没有写 T4 暴力。甚至没有一些低年级的小朋友高。

考场上的心态，策略依旧值得反思。去年爆炸的阴影并没有散去，最后的时间依旧没有拿到分数。你比的是分数，而不是会做几道题。

当然，实力因素也占很大部分，刷题量不够导致并没有想到线性 T3 做法。分数自然在全省初中生排名也不是最拔尖的。

可是，这就一定是坏消息吗？

我今年并没有辜负老师的期待，尽管有一点点遗憾。在不少高水平出现挂分时，我稳住了。拿下了今年的一等奖，可以去参加 NOIP。

前路漫漫亦灿灿，我会全力准备 NOIP，不辜负老师亲友，不辜时间，不辜负自己。

\color{#2CA9E1}\mathsf{『末日时在做什么？有没有空？可以来拯救吗？』}\\\scriptsize\mathsf{—\ What\ is\ the\ end\ of\ the\ day?\ Is\ there\ any\ availability?\ Can\ I\ come\ to\ the\ rescue?\ —} ′ s\ Dream\ —} \color{#2CA9E1}\mathsf{『等这场战争结束之后』}\\\scriptsize\mathsf{—\ StarryRoad\ To\ Tomorrow\ —} \color{#2CA9E1}\mathsf{『不归之人与望眼欲穿的人们』}\\\scriptsize\mathsf{—\ Dice\ In\ Pot\ —} \color{#2CA9E1}\mathsf{『人人本着正义之名』}\\\scriptsize\mathsf{—\ From\ Down\ Till\ Dusk\ —} \color{#E4671E}\mathsf{『长存不灭的过去，逐渐消逝的未来』}\\\scriptsize\mathsf{—\ No\ News\ Was\ Good\ News\ —} \color{#E4671E}\mathsf{『我回来了』}\\\scriptsize\mathsf{—\ Home\ ,\ Sweet\ Home\ —} \color{#E4671E}\mathsf{『纵使日薄西山』}\\\scriptsize\mathsf{—\ Slight\ Light\ ,\ Slight\ Hope\ —} \color{#E4671E}\mathsf{『即使看不到未来』}\\\scriptsize\mathsf{—\ Moonlight\ Sorcery\ —} \color{#E4671E}\mathsf{『此时此刻的光辉』}\\\scriptsize\mathsf{—\ My \ Happiness\ —} \color{#E4671E}\mathsf{『盼君勿忘』}\\\scriptsize\mathsf{—\ Evidence\ of\ Existance\ —}