CodeForces 797E: Array Queries 分段处理

本文主要是介绍CodeForces 797E: Array Queries 分段处理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

题目描述

a 是一个长度为 n 的正整数数列，每一项的值都不超过 n.
现在有 q 组询问。每组询问包含两个参数 p 和 k。一个操作被重复进行：将 p 变成 p + ap + k。这个操作会一直进行直到 p 大于 n。这个询问的答案就是操作的次数。

分析

我们可以通过n^2的复杂度把结果预处理，但是DP预处理的话需要N * N的空间，明显开不下，怎么办呢
我们可以把k的范围分段，大于sqrt(n)的范围我们可以去暴力，因为基本上跳一次就可以了，小于sqrt(n)的范围我们去预处理出来即可

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <cstring>
#define debug(x) cout<<#x<<":"<<x<<endl;
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 100010;
int a[N];
int f[N][500];
int n,q;int main(){scanf("%d",&n);for(int i = 1;i <= n;i++) scanf("%d",&a[i]);int maxv = (int)(sqrt(n) + 0.5);for(int i = n;i;i--)for(int j = 1;j <= maxv;j++)if(i + a[i] + j > n) f[i][j] = 1;else f[i][j] = f[i + a[i] + j][j] + 1;scanf("%d",&q);while(q--){int x,y;scanf("%d%d",&x,&y);if(y <= maxv) printf("%d\n",f[x][y]);else{int ans = 0;while(x <= n){x = x + a[x] + y;ans++;}printf("%d\n",ans);}}return 0;
}/**
*　　┏┓　　　┏┓+ +
*　┏┛┻━━━┛┻┓ + +
*　┃　　　　　　　┃
*　┃　　　━　　　┃ ++ + + +
*  ████━████+
*  ◥██◤　◥██◤ +
*　┃　　　┻　　　┃
*　┃　　　　　　　┃ + +
*　┗━┓　　　┏━┛
*　　　┃　　　┃ + + + +Code is far away from 　
*　　　┃　　　┃ + bug with the animal protecting
*　　　┃　 　 ┗━━━┓ 神兽保佑,代码无bug　
*　　　┃ 　　　　　　 ┣┓
*　　  ┃ 　　　　　 　┏┛
*　    ┗┓┓┏━┳┓┏┛ + + + +
*　　　　┃┫┫　┃┫┫
*　　　　┗┻┛　┗┻┛+ + + +
*/