联合省选2025游记

· · 生活·游记

Day -?

怎么还有一个星期就省选了？

虽然 NOIP T1 看错题目爆炸了，这个赛季没救了，但是去省选积累一下经验嘛。

UPD：事实证明，打得确实有问题。

Day -2

HB 省选模拟强制使用 NOI Linux 作为系统，然后我在 T1 使用了一个叫做 y2 的数组 CE 了，如果用的是 Windows，我就光荣保龄了，再也不敢用 Windows 了。

Day 1

进考场，先睡一会。睁开眼睛，欸怎么 8:35 了，开 T1。

中位数问题有个经典的赋值 1 或 -1 的 trick，离散化枚举一下，预处理 6 个前缀和数组就解决了。离散化有一些边界情况，9:50 过了所有大样例。

然后在 T2 和 T3 之间横跳。T2 感觉非常的不可做，推了一会发现需要一个 DAG 上数据结构，这不是寄了吗？T3 好像是什神秘计数，想不太清楚。

然后感觉 T2 应该有办法去掉一些边造一棵树出来，但是处理不了。注意到图是不变的，考虑预处理图上连通性的信息。但是我记得这个是 O(n^2) 最多 bitset 优化一下，应该没有前途(伏笔 1)。

考察 T2 的特殊性质，发现可以 Tarjan+线段树合并获得高达 4 分，赚翻了，谁爱写谁写去。然后一直考虑如何扩展，扩展不了。

晚上复习了询问分块(伏笔 $2$)和李超线段树。 估分 $[100,100]+[20,20]+[8,8]=128$，大众分。如果想 Day 2 翻盘的话是不是得切 T1 和 T2？ 做了一个很长的梦，没睡好。 ### Day 2 进考场，先睡一会。睁开眼睛，哇塞我居然 $8:00$ 准时醒了，好好好。开 T1。 $8:32$ 想好了 T1，应该就是贪心加上线段树维护区间和区间推平为等差数列，很容易啊(伏笔 $3$)。T2 好像是状压计数，前几天才做了 [P11714 [清华集训 2014] 主旋律](https://www.luogu.com.cn/problem/P11714) 和 [P10221 [省选联考 2024] 重塑时光](https://www.luogu.com.cn/problem/P10221)，感觉优势在我啊！ 肚子疼，先去上个厕所，盯着厕所的地板分析了一会性质，想出来 T2 $O(4^n)$ 感觉有 $60pts$ 的做法，打算写完 T1 就写(伏笔 $4$)。回来大概 $9:32$，又想了一会 T1 的细节，写写写。 $10:37$ 写完了，一发通过小样例，大样例挂了。找锅，找锅，找锅。调了一会，发现自己写错了至少 $5$ 个地方，是不是没睡醒啊。 >区间中元素数量为 $l-r+1

排序之后忘记映射下标

二分边界写挂 ……

大约 11:12 修完了这些杂七杂八的锅，测大样例惊喜的发现答案没有变化！哦好像有变化，所有小数据都过了，就是说再也没有数据帮我调试了，破防。(回收伏笔 3)

找锅，找锅，找锅。把线段树换成暴力，答案不一样？百思不得其解，还是找不到锅。手造了几组数据，都过了。破防。找锅，找锅，找锅。

找锅，找锅，找锅。$12:39$ 意识到再不打暴力就真的完蛋了，看 T2 和 T3 的暴力，怎么都不好写？决策一会后 $15$ 分钟速通 Prim T2 $12pts$，$12:58$ 放弃挣扎(回收伏笔 $4$)。 估分 $[0,100]+[12,12]+[0,0]=[12,112]$，烂完了，向 CCF 祈祷数据水吧。总分 $[128,128]+[12,112]=[140,240]$，但是分数分布应该是不均匀的，可能更接近 $140$ 吧。 回家路上听到昨天 T2 要用 bitset？(回收伏笔 $1$)算了一下，啊好像真能存得下？回家后扫了一眼题解，询问分块？(回收伏笔 $2$)我得庆幸我没有心脏病。 吃饭的时候好像知道 T1 哪里挂了，我真是个唐氏。 ### 闲话 ~~太史公曰：~~ 失误有点大啊。Day 1 懒得说了，这个 Day 2 打得是不是有点太抽象了。T1 一直漏了一种情况直到结束都没调出来，T2 $60pts$ 没时间写，T3 连暴力都没写。 考虑为什么会漏一种情况，就是没考虑到如果已经不需要推的箱子在我的算法中还是会产生贡献。我的思维还是太跳跃了，很多推导过程都是没有写前提条件的。这导致我无论是数学中还是 OI 中都经常犯一些很唐氏的错误。过程还是要写清楚。教练说我有灵性，但是灵性是建立在有足够严谨的推导能力的基础上才能进行创新的。菜就多练，多练习推导能力。还要加训一些 DS，不然代码能力太菜了。 明年得好好打了，起码不能像 Day 1 一样睡过头了。