联合省选 2025 游记

· · 生活·游记

前情提要：NOIP 138 没去省选。

Day -7

cf 上面看到有人要打个 ICPC 制的比赛，但是三缺一，招人。一看比赛时间，居然就在省选 D1 20:00-25:00。看到两个 specialist 本人欣然前往。那两个人一个是 A 国的（某五字国家，忘了），一个是中国的。我们互加了 discord，我还用中文联系那个中国的，但是他好像不回。

Day -6

开 skype 讨论了一下大概的策略，然后发现那个中国的其实是 A 国的，跟打 LOL 填韩国一个道理。

Day -2

vp 了一场 cf 的 icpc mirror。2000*没切。

Day 1

正赛开始，花了一个小时把全部题看了一遍，发现 D 题是个给平面上的散点，求一个固定半径的圆能覆盖多少个。好像模拟退火可做，但是三次没过，丢掉了。一看榜 D 是过的最多的，A 是第二多的，先看 A。具体是啥忘了，反正挺简单，切了。一看 dc 队友一句话不说，难道是跑路了。发现 I 题是个树剖模板（点权 \{0,1\}，维护 x 到 y 上点权排序和子树反转），写到只剩半个小时了发现样例过但 WA，紧急呼叫队友帮忙对拍。然后队友表示暴力写不出来。一题遗憾立场。

Day 2

我妈开透视看到我打 florr，然后一整天都没用上电脑。不过晚上心情好转，给我打了会 adx。宙天二见 100.8，天文钟 2 粉。

Day 3

到学校问省选考了啥题，这 D1T1 怎么这么简单，\Omicron(nV) 对每个数检验，然后检验的结果只变 \Omicron(n) 次所以离散化 \Omicron(n^2)，然后扫描 + 动态维护即可 \Omicron(n\log n)。D2T1 教练说比 D1 简单，但是目前只想到 \Omicron(n^2)，回家再想想。

哦应该是口胡出来了。从左边到右边依次解决。开两个数据结构，一个维护所有箱子的当前位置，一个维护哪些时间已经被安排操作不能用了（即时间轴）。先说时间轴，定义操作 (a,t) 为选 a 为止的最右边的 t 个没被占用的节点进行占用，返回能否成功。动态开点，维护线段底下被占用了多少个节点，\Omicron(n\log t)。再看箱子位置。如果最左边的 a 到 b 没有障碍物，那么直接移动，操作 (t_i,\lvert b_i-a_i\rvert)。否则二分出来一个点 k，使得 [a_i,b_i+k] 上有最多 k+1 个箱子（包括自己），然后把这 k+1 个箱子依次挪到 [b_i,b_i+k]。至于挪动的时间和箱子位置的更新，由于每个箱子都是左到右挪动，所以线段树很好维护，带上二分，复杂度 \Omicron(n\log^2 n)。感觉正解不是这个？但应该能过？明天写写。

Day 4

那个二分好像可以线段树上做？

为什么我写的 FFT 常数那么大。

D1T1 这么卡常，妈批发的？请问 6e5 是在卡什么呢，这题有 \Omicron(n^{\frac32}) 做法？就算有 3e5 卡不住？

FFT 蝶形优化这么牛的。

Day 6

同学分数出来了，疑似我是全班压力最大的。

D2T1 两个线段树写不出来。