1 条题解
-
1
题目大意： 1~n 每个点上各有一只青蛙，每次它们会跳到距离自己第 k 远的点上。求跳 m 次之后，每只青蛙的位置
思路
第一步，预处理出每个点上的青蛙跳一次之后的位置，可以用双指针来求
第二步，用倍增处理出第 i 个点上的青蛙跳 2^j 次之后的位置
第三步，利用第二步算出的结果，计算每只青蛙跳 m 次之后的位置
参考代码
int l = 1, r = 1 + k; //双指针求跳一次的位置 for (int i = 1; i <= n; ++i) { while(r < n && abs(p[l] - p[i]) > abs(p[r+1] - p[i])) r++; if(abs(p[l] - p[i]) < abs(p[r] - p[i])) f[i][0] = r; else f[i][0] = l; }
- 1