Description

从一个点到达与他距离第 \(k\) 小的点,问从每个点跳 \(m\) 次到达那个点.

Sol

队列+倍增.

保持队列里的元素个数为 \(k\) ,从前往后扫不难发现左右端点都是单调的.

求跳 \(m\) 次就是倍增了,滚一下数组.

Code

/**************************************************************
Problem: 2093
User: BeiYu
Language: C++
Result: Accepted
Time:7256 ms
Memory:20832 kb
****************************************************************/ #include <bits/stdc++.h>
using namespace std; typedef long long LL;
const int N = 1e6+50;
const int M = 65; LL n,k,m,l,r,lm;
LL a[N],pow2[M];
int f[2][N],g[N]; inline LL in(LL x=0,char ch=getchar()) { while(ch>'9' || ch<'0') ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x; }
int main() {
n=in(),k=in(),m=in(),lm=log2(m)+1;
for(int i=1;i<=n;i++) a[i]=in(); l=1,r=k+1; for(int i=1;i<=n;i++) {
while(r<n && a[r+1]-a[i] < a[i]-a[l]) r++,l++;
f[0][i]=(a[r]-a[i] > a[i]-a[l] ? r : l);
} pow2[0]=1;for(int i=1;i<=lm;i++) pow2[i]=pow2[i-1]<<1;
if(m&1) for(int i=1;i<=n;i++) g[i]=f[0][i];
else for(int i=1;i<=n;i++) g[i]=i;
r=1;
for(int j=1;j<=lm;j++) {
for(int i=1;i<=n;i++) f[r][i]=f[r^1][f[r^1][i]];
if(m&pow2[j]) for(int i=1;i<=n;i++) g[i]=f[r][g[i]];
r^=1;
}
for(int i=1;i<=n;i++) printf("%d%c",g[i]," \n"[i==n]);
return 0;
}

最新文章

  1. POJ2942:Knights of the Round Table
  2. Win10 UI入门窗口由默认500px to 320px
  3. QT中的C/S通信问题:关于服务器端readyread()信号不发射
  4. Redis 事务总结
  5. sql语句感想
  6. 使用hibernate更新数据库记录的信息的相关学习记录
  7. 使用FileSystemWatcher捕获系统文件状态
  8. hadoop笔记之Hive的数据存储(外部表)
  9. Python 第七篇:异步IO\数据库\队列\缓存
  10. EXchange导出通讯录提取url纯文本
  11. Mapper 动态代理方式
  12. spring+springmvc+mybatis+oracle+atomikos+jta实现多数据源事务管理
  13. 网络传输数据封装详解(IP,UDP,TCP)
  14. linux 定时下载github最新代码
  15. 可迭代对象 TO 迭代器
  16. luogu4269 Snow Boots G (并查集)
  17. create-react-app 搭建的项目中,使用 CSS Modules
  18. iOS - 实现语言本地化/国际化
  19. 怎样解决VMware虚拟机无法连接外网问题
  20. 第6章—渲染web视图—SpringMVC+Thymeleaf 处理表单提交

热门文章

  1. [LeetCode] Perfect Rectangle 完美矩形
  2. [LeetCode] Design Snake Game 设计贪吃蛇游戏
  3. js封装的三级联动菜单(使用时只需要一行js代码)
  4. CF719E(线段树+矩阵快速幂)
  5. 工作邮件loop的用法
  6. SSM集成(一):Mybatis3测试
  7. mvn-打jar运行包(含环境变量配置)
  8. Python3 面向对象(基础篇)
  9. thusc2016游记&amp;&amp;滚粗记&amp;&amp;酱油记
  10. Beta阶段第八次Scrum Meeting