【倍增】魔力小球

傷城~ 2024-03-29 16:21 71阅读 0赞

**今天最后一篇，该睡了，怕猝死QwQ**

**学校OJ上的一道模板题，去年不会做，今年还是不会做嘻嘻，还好最后调出来了，错的原因竟然是题目有歧义**

**这个小球i的i是他喵的小球编号，不是id！**

**出题人是懂出题的**

![8174721265e2b84088b81aa6a491d031.png][]

题意：

![e9cdfc9aba81f54b26851f79a15f9060.png][]

思路：

一格一格跳肯定T飞，因此考虑倍增地跳

倍增嘛，就是特殊的DP

设dp\[i\]\[j\]为从i位置开始跳，跳(1<<j)距离后的位置

先去预处理一下dp\[i\]\[0\]

然后转移方程很典吧

f[i][j]=f[f[i][j-1]][j-1];

最后怎么跳呢，其实就是去枚举二进制位，因为它的贡献是**按位分布**的，对于每一位去倍增地跳就好了，如果发现跳出去了得及时break

Code：

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    const int mxn=1e5+10;
    int n,q,p,K;
    int a[mxn],m[mxn],f[mxn][33];//跳(1<<j)步后的id
    int id[mxn];
    void solve(){
        cin>>n>>q;
        for(int i=1;i<=n;i++) cin>>a[i],id[a[i]]=i;
        for(int i=1;i<=n;i++) cin>>m[i];
        for(int i=1;i<=n;i++) f[i][0]=i+m[a[i]];
        for(int j=1;j<=30;j++){
            for(int i=1;i<=n;i++){
                if(f[i][j-1]>n) f[i][j]=1e18;
                else f[i][j]=f[f[i][j-1]][j-1];
            }
        }
        /*for(int j=0;j<=30;j++){
            for(int i=1;i<=n;i++) cout<<f[i][j]<<" \n"[i==n];
        }*/
        while(q--){
            cin>>p>>K;
            p=id[p];
            int ans=0;
            for(int j=30;j>=0;j--){
                if((K>>j)&1){
                    if(p>n){
                        break;
                    }else{
                        p=f[p][j];
                    }
                }
            }
            if(p>n) cout<<-1<<'\n';
            else cout<<a[p]<<'\n';
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

**总结：**

**感觉倍增之所以能优化是因为它的贡献是按位分布的，所以能枚举二进制位去倍增统计贡献**

**关于倍增的做法，感觉把它当做DP做就行了，就统计贡献的时候按位统计**

[8174721265e2b84088b81aa6a491d031.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/b4b0a388be1149eb966209ad3b3a93e1.png
[e9cdfc9aba81f54b26851f79a15f9060.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/edf91d9294694218a1bcd61eee3e0694.png