797-E 题目大意
给定一个长为\(n\)序列\(a\),有\(q\)次询问:
- 给定\(p,k\),你需要反复执行操作\(p = p + a_p + k\),直到\(p > n\)为止,问你要执行多少次操作。
Solution
考虑两种思路:
1、暴力回答询问,每次反复模拟操作,直到\(p>n\)为止,时间复杂度\(O(q·\frac{n}{k})\)。
2、预处理出所有的\(p,k\)对应的操作次数,直接\(O(1)\)回答询问,时间复杂度\(O(nk)\)。
两个算法单独使用任何一个复杂度都过高,因此考虑结合使用,预处理出所有\(k \le \sqrt{n}\)的情形,回答询问时:
- 如果\(k \le \sqrt{n}\),则直接用预处理的值回答询问。
- 如果\(k > \sqrt{n}\),则暴力模拟。
时间复杂度:\(O((n+q) \sqrt{n})\),空间复杂度:\(O(n \sqrt{n})\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
const int M=350;
int pre[N][M];
int a[N];
int main(){
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int n;
cin>>n;
int B=sqrt(n);
for(int i=1;i<=n;i++){
cin>>a[i];
}
for(int i=n;i;i--){
for(int j=1;j<=B;j++){
if(i+a[i]+j>n) pre[i][j]=1;
else pre[i][j]=pre[i+a[i]+j][j]+1;
}
}
int q;
cin>>q;
while(q--){
int p,k;
cin>>p>>k;
if(k<=B){
cout<<pre[p][k]<<'\n';
}else{
int res=0;
while(p<=n){
res++;
p+=a[p]+k;
}
cout<<res<<'\n';
}
}
return 0;
}
标签:797,pre,int,复杂度,CF,sqrt,cin,根号
From: https://www.cnblogs.com/fengxue-K/p/18172151