【根号分治+DP】CF797E

女爷i 2024-03-16 10:53 51阅读 0赞

[Problem - 797E - Codeforces][]

题意：

![23760ea9c7e445d99782af22385a6467.png][]

思路：

如果不关注数据范围，不难看出是个简单DP，比较好写

但是N和Q都是1e5，怎么办呢

考虑根号分治

即对于每次询问，<=sqrt(N)和>sqrt(N)的部分分开考虑

如果K>sqrt(N)，那么操作次数不会超过sqrt(N)

否则就暴力预处理DP数组，这样DP的空间和时间复杂度也不会爆

总复杂度为O((N+Q)sqrt(N))，不会超时

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=1e5+10;
    const int mxv=321;
    const int mxe=2e5+10;
    const int Inf=1e18;
    
    int N,Q,p,k;
    int a[mxn];
    int dp[mxn][mxv];
    
    void solve(){
        cin>>N;
        for(int i=1;i<=N;i++) cin>>a[i];
        int M=(int)sqrt(N);
        for(int i=N;i>=1;i--){
            for(int j=1;j<=M;j++){
                if(i+a[i]+j>N) dp[i][j]=1;
                else dp[i][j]=dp[i+a[i]+j][j]+1;
            }
        }
        cin>>Q;
        while(Q--){
            cin>>p>>k;
            if(k<=M){
                cout<<dp[p][k]<<'\n';
            }else{
                int cnt=0;
                while(p<=N){
                    p+=a[p]+k;
                    cnt++;
                }
                cout<<cnt<<'\n';
            }
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - 797E - Codeforces]: https://codeforces.com/problemset/problem/797/E
[23760ea9c7e445d99782af22385a6467.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/a9a08cae44b54955b2c9c103d8473abd.png

发表评论取消回复

表情：

评论列表（有 0 条评论，51人围观）

还没有评论，来说两句吧...

相关阅读

相关【根号分治】CF1790 F

[Problem - F - Codeforces][] 题意： ![d39e51cdfd9b4fc1a390989f342b113c.png][] 思路： ![880

浅浅的花香味﹌/ 2024年03月22日 20:21/ 0 赞/ 71 阅读

相关【根号分治】ABC230 E - Fraction Floor Sum

[E - Fraction Floor Sum (atcoder.jp)][E - Fraction Floor Sum _atcoder.jp] 题意： ![86e990

矫情吗；*/ 2024年03月22日 15:06/ 0 赞/ 84 阅读

相关【根号分治+DP】CF797E

[Problem - 797E - Codeforces][] 题意： ![23760ea9c7e445d99782af22385a6467.png][] 思路：如果

女爷i/ 2024年03月16日 10:53/ 0 赞/ 52 阅读

相关分治维护dp——19南昌网络赛C/cf750E

南昌网络赛，是cf的原题第一次做到这种题，所以认真想了下，每次给一个询问\[L，R\],要求出这个区间里有2017子序列，但是不能有2016子序列需要删掉的最少元素个数

桃扇骨/ 2023年10月11日 07:49/ 0 赞/ 10 阅读

相关 797. 差分(有图解)

输入一个长度为 n 的整数序列。接下来输入 m 个操作，每个操作包含三个整数 l,r,c，表示将序列中 \[l,r\] 之间的每个数加上 c。请你输出进行完所有操作后的

素颜马尾好姑娘i/ 2023年09月30日 12:16/ 0 赞/ 14 阅读

相关 LeetCode 797. 所有可能的路径

给一个有 n 个结点的有向无环图，找到所有从 0 到 n-1 的路径并输出（不要求按顺序）二维数组的第 i 个数组中的单元都表示有向图中 i 号结点所能到达的下一些结点（译

偏执的太偏执、/ 2022年10月27日 12:07/ 0 赞/ 139 阅读

相关 1至10根号计算机,根号1到10分别约等于多少

满意答案 ![dcebd7a0de6265b6ccae5ead692f1eab.png][] Ever天赐 2017.03.17 ![dcebd7a0de6265b6c

àì夳堔傛蜴生んèń/ 2022年08月31日 14:19/ 0 赞/ 268 阅读

相关函数计算机怎么算开根号,excel开根号公式怎么计算（详解excel开根号公式函数）...

作为我们平时经常会使用到的办公软件之一的Excel，我们除了会在其中录入一些简单的、基本的数据信息之外，还会对其中的数据进行一些运算，比如求和、求平均值等等。而如果我们在需

短命女/ 2022年08月31日 14:17/ 0 赞/ 252 阅读

相关 codeforces-797A-k-Factorization

A. k-Factorization time limit per test 2 seconds memory limit per test 256 megabytes

蔚落/ 2022年05月24日 11:08/ 0 赞/ 15 阅读

相关 codeforces 914E 树上点分治

https://codeforc.es/contest/914/problem/E 题解: 首先,这个是一个可减的信息,需要容斥去做对于信息而言,显然是状压保存,然后用

r囧r小猫/ 2021年12月17日 12:19/ 0 赞/ 243 阅读