26.9.9 比赛记录

更新于 2026年9月26日约 2 分钟阅读

数据结构专题?但第一题不是图论吗?

A P7991

处理出所有连通块,然后预处理出各点距离起点所在连通块和终点所在连通块的最小距离。然后分别遍历每个连通块,计算出这个连通块中的点距离起点和终点的最小距离。

然后题目说了,只能修两条路,也就是最多包含 33 个连通块。起点和终点的连通块肯定包含,枚举剩下的一个中间连通块,计算出修路的代价,取最小即可。

B P8188

又是模拟。

维护 33 个 set,一个存屏幕上能看到的邮件,一个存还没归档的邮件,一个存屏幕上能看到的邮件(但是按照 f[i] 排序)。

每次找屏幕上是否有能够归档的邮件,如果有就归档,没有就把邮件列表往下滚。如果滚不了,就把文件夹列表往下滚。如果有一个文件夹还有未归档的邮件,并且即将离开屏幕,那么就无解。

C P6278

只要你学过树状数组求逆序对,那么这题的思路就差不多。

把头发看成每时每刻都在长,如果一个头发停止生长了,那么它对答案的贡献就是排在它前面的仍在生长的头发个数,用树状数组的单点修改和区间求和即可。

D P10134

这题感觉是思维题。维护一个数组 bb,bi=−1,0,1b_i=-1,0,1 分别表示这个位置的数禁止创新高、无所谓、必须创新高(其中创新高是指成为前缀最大值)。那么如何计算 bb 呢?初始 bib_i 都为 00,对于每一个限制 (x,y)(x,y),可以知道 by=1b_y=1,bi=−1(x<i<y)b_i=-1(x<i<y)。如果一个位置的 bib_i 既是 11 又是 −1-1,那么无解。

然后开始逐位赋值,并且维护一个 pp 指针,指向上一个 cic_i 不确定的位置。如果 bi=−1b_i=-1,并且不确定,那么赋值为 11。否则如果创了新高,就把 cpc_p 改成 cic_i。如果 bi=0b_i=0 且 cic_i 不确定,就把 cic_i 设置成 11。如果 bi=1b_i=1 且 cic_i 不确定,就把 cic_i 设置成当前前缀最大值 +1+1。

Vector Log · 算法竞赛学习笔记

Built with Nuxt UI & Nuxt MDC