Luogu – P3509 – [POI2010]ZAB-Frog

题意

数轴上有 $n$ 个点,坐标分别为 $p_1, p_2, \cdots, p_n$ 在这些点上按照某些规则跳。

规则是:每次向距当前点第 $k$ 小的点跳,如果有相同距离则向下标较小的跳;

求从每个点出发跳了 $m$ 次后在哪里.

$1\leq k < n\leq 10^6, 1\leq m\leq 10^{18}, 1\leq p_i\leq 10^{18}$.

$\rm{Part}$ $\rm{1}$

首先,注意到 $k$ 是固定的,所以可以先预处理,对于每个点 $i$,跳一次之后的位置$\operatorname{next}_i$.

这部分使用单调队列处理。

我们知道,对于每个点,距离其前 $k$ 小的点分布在其两侧,可以用一段完整区间覆盖。

所以我们想到,当单调队列枚举到 $i$ 时,单调队列中维护的区间,就是覆盖距离 $i$ 前 $k$ 小的点的区间。这样找到区间内距离最大的点就是我们要求的 $\operatorname{next}_i$,下面考虑考虑如何维护。

对于区间 $[l, r]$ 中的一个点 $i$,距离他最远的点一定是 $l$ 和 $r$ 这两个点中的一个。如果 $r+1$ 到 $i$ 的距离小于了 $l$ 到 $i$ 的距离,说明区间应当向右滑动,如下图,$n=7, k=3$ 的例子:

绿色区间是距离点 $C$ 前 $k$ 小的点,考虑距离点 $D$ 前 $k$ 小的点。

$\rm{Dis(D, F)<Dis(d, a)}$,所以区间要右移一个单位,变成:

又因为 $\rm{Dis(D, E)<Dis(d, b)}$,所以区间要再右移一个单位,变成:

至此,我们能够求出每个点,距离其第 $k$ 小的点的下标。

head = 1, tail = k + 1;
for(int i = 1; i <= n; i++) {
	while(tail + 1 <= n && x[tail + 1] - x[i] < x[i] - x[head]) head++, tail++;
	if(x[tail] - x[i] > x[i] - x[head]) nxt[i] = tail;
	else nxt[i] = head;
}

$\rm{Part}$ $\rm{2}$

题目要求跳 $m$ 次之后的答案,我们使用类似快速幂的方法,倍增处理即可。

for(int i = 1; i <= n; i++) pos[i] = i;
while(m) {
	if(m & 1) {
		for(int i = 1; i <= n; i++) pos[i] = next[pos[i]];
	}
	m >>= 1;
	for(int i = 1; i <= n; i++) next2[i] = next[i];
	for(int i = 1; i <= n; i++) next[i] = next2[next2[i]];
}

代码

最终代码在上面两部分的基础上加上 $\rm{I/O}$ 即可。

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();