首页 > 其他 > 详细

P5151 HKE与他的小朋友

时间:2020-02-23 20:57:44      阅读:32      评论:0      收藏:0      [点我收藏+]

标签:line   吓死我了   c++   con   倍增   n)   

原题链接:https://www.luogu.org/problem/P5151

这题我一开始是从赛后总结里过来的,看到置换乘法啥的,吓死我了。然后瞄了一眼题解,原来倍增也能过,但是比较坑的是,他这个边界压的很恶心,2^31,多了不行,少了也不行,多了估计会int爆掉,少了会WA几个点。我提交了好几次才调整好这个边界,可能是我太菜了。

#include<bits/stdc++.h>
using namespace std;
inline long long read() {
    char ch = getchar(); long long x = 0;short f = 1;
    while(ch < 0 || ch > 9) {
        if(ch == -) f = -1;
        ch = getchar();
    } while(0 <= ch && ch <= 9) {
        x = x * 10 + ch - 0;
        ch = getchar();
    } return x * f;
}
int f [1000001][33];
inline int query (int x,int k) {
    unsigned long long now = 0;
    for (int i = 31;i >= 0;-- i) {
        if (now + (1 << i) > k) {
            continue ;
        }
        now += 1 << i;
        x = f [x][i];
    }
    return x;
}
int tong [1000005];
int main() {
    int n = read (),k = read ();
    for (int i = 1;i <= n;++ i) {
        f [i][0] = read ();
    }
    //开始倍增
    for (int rk = 1;rk <= 32;++ rk) {
        for (int i = 1;i <= n;++ i) {
            f [i][rk] = f [f [i][rk - 1]][rk - 1];
        }
    } 
    //开始查询
    for (int i = 1;i <= n;++ i) {
        int temp = query (i,k);
        tong [temp] = i;
    }
    for (int i = 1;i <= n;++ i) {
        cout << tong [i];
        if (i != n) {
            cout << " ";
        }
    }
    return 0;
}
 

 

P5151 HKE与他的小朋友

标签:line   吓死我了   c++   con   倍增   n)   

原文:https://www.cnblogs.com/dorbmon/p/12353985.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号