負け犬にアンコールはいらない - CSP & NOIP 2024 游记

CSP-S 初赛

Day -2

晚上做了下 23 年的卷子，做得有点 yyz，最后 85.5 分。好像也不是很爆。

Day 1

上午不想偷学，开了一上午 chess。

中午吃完饭看了眼 J 组的题，好像全是唐题。

下午带着唐龙玩偶去找 zyz。

面到了诸暨的故人 & Binary。

然后随便聊了聊就进考场了。

发现我们考场有至少 7 个我认识的人……

卷子发下来就直接从前往后做，发现有欧拉图题，乐了。

第 10 题看也看不懂题是啥意思，但是注意到 $\alpha$ 可以取到 $1$，所以直接排除掉 C 选了个 D。

做完 15 题看了眼表，不小心以为两点开始然后以为已经过去 40min 了，几把吓断。

阅读程序 1，把 ~ 当成了 -，爆蛋。

阅读程序 3 没太看懂 solve() 在干嘛，然后瞟到了第 30 题，看懂了。然而没有注意到有个 sort 于是误以为复杂度是 $\Theta(n \log \log n)$，但是题里写的是大 $O$，于是误打误撞选对了。

完善 1 简单题，做完发现我怎么全选 A，但是不管先做 完善 2，然后发现 4 个 A，非常恐慌，但是还是先把前面 skip 的题都写写完，此时刚好过了 1h。

从头开始检查一遍，发现 4 元环数成了 $C(10, 4)$。

重点检查了好几遍完善程序，感觉没啥问题。但是过程中注意到它定义了一个 inf，然后扫了一眼没有看到哪里用了 inf 就没管。电子竞技不需要视力。

出来问 zyz，他说他完善程序没几个 A，害怕，然后又问了下其他人，发现是 zyz 唐了。但是应该是 0x1f，我也唐了。

阅读 1 虽然搞错了但没错几个题。

但是发现我第 4 题 $A_{10}^3 = \frac{10!}{3!7!}$，魅力时刻了。

最后 90.5，感觉每题都错得很唐，已经可以想想高三退役后 whk 各种神秘原因扣分的场景了（

Day ?

zyz 欧拉图那题做对了，他好强。

CSP-S 复赛

虽然很破防，但已经是最后一个赛季了，还是把游记写写完吧。

Day 1

上午和 Lynkcat & 紊莫 duel，写了点板子。

车上复建了几把 Phigros，实力严重下降，然后听了会歌。

然后下午到考场有点迟已经该进场了，但还是面到了 zyz。

右前方是紊莫，看到他第一眼没绷住笑了出来。

监考老师口音严重 GJZ 不分，报 pdf 密码的时候还少爆了一个 T，然后我对面选手问监考老师密码监考老师还很不耐烦的样子，有点幽默。

开场先把 VSCode 配了一下，然后写 T1，马上就过了，思考了一下写了个 selfeval。

然后看 T2，发现是高一物理题，但是推式子推了很久，然后没过样例，开始 debug，调着调着发现是 $> V$ 而不是 $\ge V$，然后大改，最后写完已经 1h15min 了。

然后看 T3，第一眼没啥想法，就把 T4 也看了一下，感觉比较可做，但还是先想想 T3。

首先容易发现每个数要产生贡献一定是和他前面第一个和他相同的数在一起，否则可以调整不劣。然后考虑 $O(n^2)$ 做法即设 $dp_{i, j}$ 表示一个在 $i$ 一个在 $j$ 时的答案。令 $to_i$ 为 $i$ 之后第一个与 $i$ 相同的数的位置，考虑转移，要么 $i$ 产生贡献到 $(to_i, to_i - 1)$，要么 $j$ 产生贡献到 $to_j - 1, to_j$，否则都不产生贡献说明 $i + 1$ 放哪里都无所谓，可以更新到 $(i + 1, i)$，因此可以设 $dp_i$ 表示两个一个在 $i$ 一个在 $i - 1$ 的贡献然后直接转移。会完就想今年 CSP 咋这么简单，然后马上写完调完，此时过去了 1h55min，有点激动。

平复一下心情看 T4 发现 polylog 是简单的，从前往后加点然后维护贡献就好了，但是由于比较亢奋所以过了比较久的时间才总结出一个清晰的单 log 做法，大概就是每次加点的时候更新祖先的信息，维护已知点的答案和未知点可能的取值，然后左边已知点只有 $O(\log n)$ 个，右边可以分成 $O(\log n)$ 段。比较怕写不完所以直接放弃正解去写了，写到一半发现是双 log 的，有点玉玉，但还是先写完了，一测可以过 $T = 16$。

然后想能不能优化，发现瞎几把改改就行了，但是这时已经没多少时间了，最后写完没过样例。

出考场发现大家基本上 T4 都是单 log，有些常数大的和我双 log 一个分，安心了。回去路上开 richup 把手机电用完了。路上 wc 说会不会有人多测不清空因为大样例数据规模是单调不降的，我想了一下我好像都清空了？

最后回家尝试默写 T1T3，然后发现 T3 前缀和没开 long long 并且没有清空 a[n + 1]，这下最低 $0$ 分了！

又是唐完的一场，真写代码不带脑子导致的，场上竟然仅凭瞪眼就调过了大样例实在不可思议，可惜最后还是 FST 了。

该加训代码能力了……

score: $100 + 100 + [0, 100] + [68, 76] = [268, 376]$.

输。

别没得去 WC 啊……

Day 10

出分了，一分没 F，$100+100+100+76=376$，赞美出题人！

NOIP

Day -2

联考，都是套路题，但是 T4 犯唐了不会做。

Day -1

据说是信心场，但是 T3 DP 不会做，T4 数据结构被卡常了，打成了一坨，心态爆炸了。

Day 0

摆了一个上午，随便写了点板子，然后又摆了一个下午……

吃完晚饭上车，在车上开了一把 generals，但是由于操作不便被薄纱了，遂关上电脑开始听歌，听着听着睡过去了，醒来刚好放到的尾奏，太爽了。然后又过了一会才到酒店。

这把又是橘子水晶，已经在橘子水晶爆蛋两回了，真该反思为啥老是订这个风水差酒店。

登记完去牢张房间开 Impart，七个人点了顿炸鸡，人均 12R。建议这种活动要多搞！

然后和牢张开了会 MC，到差不多十点就回去了，接着又小摆一会十一点上床睡觉，祈祷明天不会爆蛋。

Day 1

早上起来精神状态良好，早饭喝了杯咖啡。

进考场，感觉位子好像比 CSP 的时候要小。看了圈周围，好像除了我左边第三个的 lcy 没有熟人。

报密码的时候右前方的老哥好像眼镜断了，难蚌，后来知道原来是 BreakPlus。

开题先看 T1，读完题感觉我草怎么这么难，先上个厕所，回来考虑大胆猜想如果从前往后贪心会怎么样，发现直接就是对的，然后开写，调了一会过大样例了，此时过去了四十多分钟，好像花的时间有点久。

然后看 T2，感觉就简单数数题，显然值不重要，然后考虑啥时候不合法，就是存在相邻两个确定的位置可以推导出来结果不一样，算一下方案数再乘起来就做完了。中间系数不小心写错了调了一下，然后过了，大概花了半小时左右？

然后看 T3，感觉有点复杂，看眼 T4，我去传统数据结构题！还是先做下 T3 吧。先考虑 $k = 1$，发现对于每个点，与其相连的边会形成一条链，然后固定根之后每个点第一个访问的边是确定的，因此方案数就是 $\prod_{i = 1}^n (d_i - 1)!$，然后显然应该考虑容斥，对于两条关键边都会统计的情况，显然是对于他们之间路径上的边都确定首尾，因此这中间的点贡献会变成 $(d_i - 2)!$。然后显然有多条边的时候生成的树要有相同的必须满足这些边能串成一条链，因此直接 DP 就可以了。然后就设 $dp_{u, 0/1}$ 表示 $u$ 子树内，链没有 / 有继续延伸时的方案乘上容斥系数的总和，稍微分讨 $O(1)$ 个转移，应该要维护子树内 $\prod (d_i - 1)!$ 的和，然后就做完了。

我一看这不傻逼题，就是情况有点多，祈祷不会写挂。写完小调一下就把大样例都过了，但是跑得有点慢，于是再处理一下 $\prod (d_i - 1)!$ 的逆元把快速幂的 $\log$ 去掉，跑得飞快。算了一下还剩下 2.5h，这下真优势在我了！感觉好像比去年 NOIP 还简单，不会又 AK 一车吧？

做 T4 的时候打了个哈欠，感觉有点困，没道理啊我不是喝了咖啡吗？算了不管还是想想咋做吧。肯定是树分治之类的东西，于是就考虑 dsu on tree，然后就考虑每次新出现的连续段，要成为答案就需要连续段和询问的区间交大于等于 $k$，感觉不可做，陷入玉玉症。

发现 dsu on tree 不太对劲后尝试考虑区间长度从小到大变化的过程，然后发现对于 $k \ge 2$，从 $[i, i + k - 1], [i + 1, i + k]$ 合并成 $[i, i + k]$ 时，由于中间有交 $[i + 1, i + k - 1]$，因此原来两个区间的 LCA 有祖先关系，然后新的 LCA 就是原来两个点较浅的那个，在深度上就是取 $\min$，于是把问题转化成有一个序列，每次相邻两项取 $\min$，查询做 $k$ 次后区间 $[l, r - k]$ 的 $\max$，显然可以二分然后判断是否存在长度大于等于 $k$ 的连续段，那么整体二分或者主席树就随便做到双 $\log$ 了！算了下分，364？好像有点少。

这个时候应该还没过多久，具体啥时间记不清了，但想了一会怎么优化到一 $\log$，不会做，于是先把双 $\log$ 写了，写完应该还有 1.5h？跑了下大样例，最后一个要 8s，嗯，果然双 $\log$ 什么的还是不可能在 2s 内跑 $5\times10^5$ 吧！

考虑这个东西在笛卡尔树上长啥样，那就是找一个子树大小大于等于 $k$ 的点的权值最大值，但是查询的是区间，所以会裂成若干棵子树和若干个不完整的树，看起来很麻烦。胡了个假做法，忘记是啥了，但是为了保险先把特殊性质 B 拼上，然后保存，然后写到一半发现假了。此时只剩大概 1h 了，开始破防。但题还得做，考虑从前往后扫一遍然后分别求最小值左右两侧的答案，发现还是不可做。

最后半小时多的时候彻底弃疗，回去拍了下 T1，没挂，这是好的，然后默默等待结束。此时的心理预期大概是又有一车人 AK，然后 T4 正解大概和我做法没啥大关系或者我的做法要加上一个比较巧妙的转化。

结束之后马上问 lcy T4 过了没 & 有无 AK，结果他 T4 过了但 T3 没调出来？唉果然还是会有一车人过 T4 吧。

在考场门口碰到了楼阁、张花、Fido_Puppy 和牢张，lcy 说 T4 是变成 $O(n\log n)$ 个区间然后搞搞之类的。啊？支配对啊？咋又是这玩意，咋我又不会做。诶不是等会，你复杂度双 $\log$ 的？啊楼阁你们复杂度也是双 $\log$ 的？不是哥们你们都跑进去了啊？啊？！只有我一个小丑觉得双 $\log$ 过不了啊？！

这下真破防了，原来我离 AK 只差一个常数优化，感觉我只要把整体二分换成主席树或者随便哪里优化一下就铁过了啊！为什么，为什么我不去试一下？到底在想什么？

出来听 cyf 说他是单 $\log$ 的，感觉符合预期，但是问了一圈好像真只有我双 $\log$ 没过。海亮还有个哥三 $\log$ 都过了，真破防。

在出去的路上楼阁问我啥做法，我说我整体二分或主席树，他很问号。稍微给他嘴了一下，他说这玩意能变成笛卡尔树上 $n$ 个区间，然后就是要求区间交大于等于 $k$，我一听好像不太对劲，问他这玩意咋做，他说直接转化成偏序就做完了。原来我一开始就想到正解然后钦定他不可做了……唐完。

问了一圈，绍一+诸中+海亮+镇海已经 8+ AK 了，看来队线又上 400 了，彻底没救。

唉，为什么从 CSP 到 NOIP，总是差一点，最后彻底沦为小丑。

真的无法接受，在题目完全在我优势区间的情况下，以这种方式输掉。

省选，还能翻盘吗？

---

破防实录：

Day 7

出分，没挂。按云斗榜好像刚好 rank 在 $15\sim 18$？

cyf 关同步混用 puts 和 cout，$400 \to 360$，绍一喜提 $0$ AK，难以评价。

还有省选，能进队吗？