首页 > 代码库 > 跳石头
跳石头
题意:
在一条水平线上有n( <= 1e6)个石头,已有一个起点(最左边),给出每个石头到起点的距离(保证升序),现在有一只青蛙开始跳石头,每次跳向距离它第k( <= n)近的那块石头(如果左右距离相等它会跳向靠近原点的石头),问它从每个点开始跳m(<= 1e18)次后所在的石头的编号。
题解:
0.首先m太大需要log级别的算法,点和点之间是具有转移关系的,那么会想到倍增。
1.anc[k][u]表示由u开始跳2^k次方次后达到的石头编号,那是k会达到60左右,内存是不够的,但是可以注意到可以 边计算答案边更新,因此第一维是可以滚动的。
2.现在的问题是得到anc[0][u],就直接维护一个区间往后推。
代码:
#include <cstdio> #include <iostream> #include <algorithm> using namespace std; #define LL long long const int N = 1e6 + 7; LL m, x[N]; int anc[2][N], n, k, cur[N], F; LL readLL(){ LL K = 0; char c = getchar(); while (c < ‘0‘ || c > ‘9‘) c = getchar(); while (c >= ‘0‘ && c <= ‘9‘) K = K * 10 + c - ‘0‘, c = getchar(); return K; } int main(){ scanf("%d%d%I64d", &n, &k, &m); for (int i = 1; i <= n; ++i) { x[i] = readLL(), cur[i] = i; } int l = 1, r = k + 1; anc[F][1] = k + 1; anc[F][n] = n - k; for (int i = 2; i < n; ++i) { while (r < n && x[r+1] - x[i] < x[i] - x[l]) l++, r++; if(x[i] - x[l] >= x[r] - x[i]) anc[F][i] = l; else anc[F][i] = r; } for (int i = 0; i <= 60; ++i) { if (m & (1LL << i)) { for (int j = 1; j <= n; ++j) cur[j] = anc[F][cur[j]]; } F ^= 1; for (int j = 1; j <= n; ++j) anc[F][j] = anc[F ^ 1][anc[F ^ 1][j]]; } for (int i = 1; i <= n; ++i) printf("%d ", cur[i]); return 0; }
跳石头
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。