P3509 [POI 2010] ZAB-Frog[单调队列+倍增快速幂思想]

P3509 [POI 2010] ZAB-Frog

时间限制: 1.00s 内存限制: 125.00MB

复制 Markdown

中文

退出 IDE 模式

题目描述

在一个特别长且笔直的 Byteotian 小溪的河床上，有 n 块石头露出水面。它们距离小溪源头的距离分别为 p1​<p2​<⋯<pn​。一只小青蛙正坐在其中一块石头上，准备开始它的跳跃训练。每次青蛙跳跃到距离它所在石头第 k 近的石头上。具体来说，如果青蛙坐在位置 pi​ 的石头上，那么它将跳到这样的 pj​ 上，使得：

∣{pa​:∣pa​−pi​∣<∣pj​−pi​∣}∣≤k and ∣{pa​:∣pa​−pi​∣≤∣pj​−pi​∣}∣>k

如果 pj​ 不是唯一的，那么青蛙在其中选择距离源头最近的石头。对于每一块石头分别计算，若青蛙从这块石头开始跳跃，经过 m 次跳跃后最终会停留在哪一块石头上？

输入格式

标准输入的第一行包含三个整数 n、k 和 m（1≤k<n≤1000000,1≤m≤1018），用空格分隔，分别表示石头的数量、参数 k 和计划跳跃的次数。第二行包含 n 个整数 pj​（1≤p1​<p2​<⋯<pn​≤1018），用空格分隔，表示小溪河床上连续石头的位置。

输出格式

你的程序应在标准输出上打印一行，包含 n 个整数 r1​,r2​,⋯,rn​，用空格分隔。数字 ri​ 表示从输入顺序中的第 i 块石头开始跳跃 m 次后，青蛙最终停留的石头编号。

显示翻译

题意翻译

输入输出样例

输入 #1复制运行

5 2 4 1 2 4 7 10

输出 #1复制运行

1 1 3 1 1

说明/提示

样例 #1 解释：

图中展示了青蛙从每块石头跳跃（单次跳跃）到的位置。

题面翻译由 ChatGPT-4o 提供

首先单调队列维护第k大的 首先维护一个长度为k的窗口 我们只需要比较左端右端 如果右端+1 的位置小于左端 那么窗口右滑 直到划不动 然后比较左右的大小 确定跳跃一步的位置

然后根据m开始倍增跳越 类似于快速幂的做法 如果是奇数 那么先跳一次 偶数的话那就令步长连续跳跃两次 也就是步长翻倍 可以类比快速幂理解；

#include <bits/stdc++.h> using namespace std; const int N=1e6+5; #define int long long int net[N],net2[N],ans[N],a[N]; long long n,k,m; signed main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>k>>m; for(int i=1;i<=n;i++)cin>>a[i],ans[i]=i; int l=1,r=k+1; for(int i=1;i<=n;i++){ while(r+1<=n&&a[r+1]-a[i]<a[i]-a[l])l++,r++; int disr=a[r]-a[i],disl=a[i]-a[l]; if(disl>=disr)net[i]=l; else net[i]=r; } while(m){ if(m&1) for(int i=1;i<=n;i++)ans[i]=net[ans[i]]; for(int i=1;i<=n;i++)net2[i]=net[i]; for(int i=1;i<=n;i++)net[i]=net2[net2[i]]; m>>=1; } for(int i=1;i<=n;i++) cout<<ans[i]<<' '; return 0; }