【根号分治+DP】CF797E

女爷i 2024-03-16 10:53 38阅读 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 条评论，38人围观）

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

相关阅读

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

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

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

相关【根号分治+DP】CF797E

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

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

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

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

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

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

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

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

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

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

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

相关 12、计算机如何实现开根号？

如何求一个数字的算术平方根（又叫开根号，或者开方）？大家普遍都是用计算器直接计算的，对于程序员来说，就是调用sqrt()方法。但是其内部又是怎么实现的呢？方法一：迭代法

待我称王封你为后i/ 2022年05月27日 10:26/ 0 赞/ 203 阅读

相关 797. All Paths From Source to Target

/\ Given a directed, acyclic graph of N nodes. Find all possible paths from node 0 to

川长思鸟来/ 2022年05月24日 13:42/ 0 赞/ 176 阅读

相关 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 赞/ 10 阅读

相关浅谈基础根号算法——分块

[https://www.luogu.org/blog/48265/qian-tan-ji-chu-gen-hao-suan-fa-fen-kuai][https_www.lu

你的名字/ 2022年05月09日 08:08/ 0 赞/ 259 阅读

相关 codeforces 914E 树上点分治

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

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