重生之所有人弗洛伊德都写 ijk 而我不变
xu_zhihao
·
·
生活·游记
day0
酒店摆烂嘟嘟嘟。
横着摆竖着摆躺着摆坐着摆。
十点半就睡了，但睡不着。
身体在床垫上均匀翻滚，最后给自己哄睡着了（？）
day1
觅食，觅食，觅食...
随便再看了看若干串串模板。串串！串串！
展示大心脏：
瞟一眼 LA，j 组四个电源板？
觅食，觅食，觅食...
然后就前往考场了。
---
紧张，紧张，紧张...
遇到了 inf 个熟人。
206 考场没有广播，没有循环播放考生守则。
提前 $3$ 分钟解压压缩包，密码输错两次。
``Oct 31==Dec 25``
---
:::align{center}
【14:29】
:::
开题。
大致浏览题目，T1 特别短，T2 特别长，T3 特别短，T4特别绕（咋全是图论）。
:::align{center}
【14:32】
:::
详细浏览 T1，感觉不太会做？深度思考三分钟后，重新读了一次题目，发现：
我把“每次操作可以任选一颗水晶，将其能量值增加 $1$”
读成了“每次操作可以任选一颗水晶，将其能量值增加 $1$ 或减少 $1$”。
（给了自己一个巴掌）
不敢相信 T1 这么简单，强迫自己再读了两次题目。然后就是写写写。
> 升序排序，设 $s_i=\sum\limits_{j=1}^i a_j$，那我们要求的就是 $\max \{ R-\min \{ L \mid\ a_R(R-L)-(s_R-s_L)\} \mid R \in [1,n]\}$。所以就是前缀和，枚举右端点，二分/双指针。鉴于双指针容易错，所以就写二分了。
:::align{center}
【14:40】
:::
开 T2，感觉好困难。
这 $w_i$ 咋这么幽默。
站厅，站台，地铁口（脑子好乱啊喂。
什么鬼，这地铁运行速度是个滚木？
读了大概 $10$ 分钟，完全搞懂了。
然后我注意到了一条地铁线内的点两两可达且从 $a_{i,d_1}$ 到 $a_{i,d_2}$ 的代价为 $t_{i,d_1}+t_{i,d_2}$，感觉很有用！
大脑随机游走...
想到最朴素的按地铁站的全源最短路，用 Floyd 复杂度是 $O(m^3)$，期望得分 $32$ 分。因为稀疏图，所以用Johnson 的复杂度是 $O(m^2 \log m)$ 的，期望得分 $44$ 分。因为感觉太劣，所以不实现了嘟嘟嘟。
发现就只有 $500$ 条地铁线，感觉很有用，然后就图论建模了一下...
大概就是分成两种点，一种是 $1\sim m$ 地铁站，另一种是 $(m+1) \sim (m+n-1)$ 的地铁线。$i+m$ 和 $a_{i,j}$ 之间建双向边，边权为 $t_{i,j}$。
手模了下第二个样例：
那么站 $x$ 到站 $y$ 的最小总步行时间就是 $(w_x+w_y)+\operatorname{dist}(x,y)$。
然后我发现，好像这样写和上面暴力是等价的。
感觉脑子有点乱，遂上个厕所缓解下。
:::align{center}
【15:05】
:::
关键突破！
发现可以只对 $n$ 个表示地铁线的点跑单源最短路，然后对于第 $x$ 个地铁站包含若干条地铁线，枚举它，最后答案是三部分代价相加，因为每个地铁站的地铁线数量都不超过 $d$，所以这档复杂度 $O(nm \log m+qd)$，期望得分 $60$ 分。
思考片刻之后：
“我咋这么蠢？”
对于 $x$ 到 $y$ 的答案不就是 $\min \{(w_x+w_y)+(t_{a,i}+t_{b,j})+\operatorname{dist}(a,b) \mid t_{a,i}=x,t_{b,j}=y\}$吗？并且显然有 $\# \{(a,b) \mid \ t_{a,i}=x,t_{b,j}=y \} \le d^2$ 地铁线之间的最短距离可以用 Floyd 求，$a,b$ 可以在 $q$ 次询问里面直接暴力枚举。故复杂度为 $O(n^3+qd^2+(\sum k)d)$，期望得分 $100$ 分。
“k 要放在最外层，记住了没有？”
“Floyd,kij,kij,kij...”
慌神间，脑海在回放三年前模拟赛的神秘挂分点。
然后就敲完代码了，大样例一遍过。
:::align{center}
【15:35】
:::
有点激动，感觉是胜类了。
赛前策略本来是 All in T2 然后后面拼满暴力的，但没想到一个小时 T2 就冲过去了，有种一拳打在棉花上的感觉（
稍作休整，吃点巧克力，感觉这个时候有点放松了。
转念一想，不会今年是 csp2023 状物吧，那不得把 T3 过了？
开 T3，题面这么短，感觉真的是 color 状物 dp 了。
:::align{center}
【15:45】
:::
第一感觉是先搞个差分数组 $b_i=a_{i+1}-a_i$。
然后一直在想什么时候有且仅有 $2$ 条最短路径。
然后就联想到了如何刻画一个区间的最短路径。
然后发现刻画区间的最短路径是一个经典贪心，其等价于将区间切最少的段数，使得每一段里的 $\sum b_i \le d$，那我考虑把每个区间的最短路径都先预处理出来，复杂度是 $O(n^2)$ 的。
到这里的目标还是冲出 $O(n^2)$ 部分分以及 A,B,C 三个特殊性质的 $72$ 分。
:::align{center}
【16:10】
:::
感觉脑子有点转不过来了，补点吃的。
想到了一种非常曼妙的双指针写法，遂写。
若干分钟后通过样例，真感觉我赢了。
万恶之源：``freopen("migrate3.in","r",stdin)``
定睛一看，有 inf 个对不上的答案，感觉天塌了。
调调调！
对着大样例手模，if-else 加加加。
然后，拆东墙补西墙，一整个绝望了...
头越来越沉，感觉状态非常不对。
脑子，想不动了...
:::align{center}
【17:00】
:::
有点急了，隐约感觉时间不够用。
经过不知道多久的折磨，剩下答案是 8e3 的那个大样例没过....
……&*@！#（）*（）@*#！@……（#&）！@
喜报：找到了一个小 Hack。
悲报：做法假了。
:::align{center}
【17:30】
:::
“时间，不多了哟~”
隔壁大哥，感觉已经过 T3 了。
大脑无法思考，胸口有点闷...
Ctrl A，Delete....
结束了...吗？
特殊性质 A，似乎特别可做。
考虑若 $\frac{d}{b_1} < 2$，答案为 $0$。
否则记 $p=\lfloor \frac{d}{b_1} \rfloor$，答案为 $\max(0,n-(2p-1))$。
:::align{center}
【17:50】
:::
放弃 $O(n^2)$ 做法，转向 $O(n^3)$ 做法。
然后发现令 $dp_{i,j}$ 表示 $b_i$ 到 $b_j$ 的最小操作次数，这个认为 $O(n^2)$ 预处理是朴素的。
考虑什么时候 $b_i$ 到 $b_j$ 最短的路径恰好有两条。简单分析可得当且仅当
$$
\# \{k\in [i,j) \mid dp_{i,k}+dp_{k_1,j}=dp_{i,j}\}-(dp_{i,j}-1)=1
$$
。所以可以类似 Floyd， $O(n^3)$ 暴力写。
想到之后立马就写写写，写完之后虚空调试了几分钟/yun。
期望得分 $24+8=32$ 分。
:::align{center}
【18:15】
:::
没错，非常神奇，我花了 $160$ 分钟拼了 $32$ 分。
光速看 T4，用了这辈子最快的速度写暴力，最后 $4$ 分钟写完了。
然后...
咋全都输出 $10^9$。
慌了，确切的来说是——放弃了。
光速抄写字节数，并结束了这场罪恶的比赛。
终究是错付了，终究还是败类。
:::align{center}
【18:31】
:::
出考场，咋一车 $260+$。
然后就是，inf 个人臭骂 T2 出题人（幽默到最后半小时刊误）。
然后就是一坨 T2 受害者包括不限于 inf=INT_MAX，ijk，读错题...
咋都说 T2 简单，我感觉不然，随机区分后会和去年差不多叭（
【20:30】
复现代码，出现转机？！
T3 $O(n^3)$ 过 $5000$？确实我代码常数约为 $\frac{1}{10}$，经过测算，只要 $t \ge 3$ 我就能卡过。
估分：
$100+100+[32,48]+0=[232,248]$。
被若干个学弟单调队列了。
我是区。