codeforces-797E-Array Queries-乱搞-打表

题目链接

题意：给定一个长度小于1e5的数列a，q(1<=1e5)次询问，每次给出一个数p与一个数k,每次操作可以将p变为p+a[p]+k,问多少次操作后p会大于n。

思路：这题是智商题……像我这样智商86的果然不适合做……暴力肯定会T，他的tag里还有个dp,但是dp肯定又T又MLE……然后开始抄题解……题解给出的是打部分表……可以证明，当k>=sqrt(n)时，每个询问暴力的复杂度为sqrt(n)，当kn时，dp[p][k]=1，否则，dp[p][k]=dp[p+a[p]+k]+1。这时的打表时间与空间复杂度都为nsqrt(n)……所以，两者相结合，是一个既不T也不MLE的做法……orz……

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
using namespace std;
int a[100005];
int dp[100005][400];
int main()
{
	int n,q;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	for(int i=n;i>=1;i--)
	 for(int k=1;k<=399;k++)
	  {
	  	if(i+a[i]+k>n)dp[i][k]=1;
	  	 else dp[i][k]=dp[i+a[i]+k][k]+1;
	  }
	scanf("%d",&q);
 	while(q--)
 	{
 		int p,k;
 		scanf("%d%d",&p,&k);
 		int ans=0;
 		if(k>=sqrt(n))
		while(p<=n)
		 {
		  p=p+a[p]+k;
 		  ans++;
		 }
		else
		{
			ans=dp[p][k];
		}
		printf("%d\n",ans);
	 }
	 return 0;
 }