Array Queries CodeForces

题意：给出一个序列a[1],...,a[n](其中数不超过n)和q个查询，对于每个查询(p,k)，每次操作将p变为p+a[p]+k，要求对于每个查询输出将p变为大于n的数所需操作数。

WATLERE之路：分析：

很显然的一道dp题，如果p不超过n，则dp[p][k]=dp[p+a[p]+k][k]+1，否则dp[p][k]=0.我有一个想法就是将所有查询按照k排序，然后对相同的k去dp一次，然后输出。

于是我妄想着通过时间O(n^2)的dp把它A掉，然后，我就走上了WATLERE之路.....

第一次，递归，RE

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int ans[100100];
 6 int a[100100];
 7 int n,k,q;
 8 int ans2[100100];//曾经忘记将排序后的查询按原序输出
 9 struct Q
10 {
11     int p,k,num;
12     bool operator<(const Q& b) const
13     {
14         return k<b.k||(k==b.k&&p<b.p);
15     }
16 }q2[100100];
17 int get(int x)
18 {
19     if(ans[x])    return ans[x];
20     if(x>n)
21         return ans[x]=0;
22     else
23         return ans[x]=get(x+a[x]+k)+1;
24 }
25 int main()
26 {
27     int i;
28     scanf("%d",&n);
29     for(i=1;i<=n;i++)
30         scanf("%d",&a[i]);
31     scanf("%d",&q);
32     for(i=1;i<=q;i++)
33     {
34         scanf("%d%d",&q2[i].p,&q2[i].k);
35         q2[i].num=i;
36     }
37     sort(q2+1,q2+q+1);
38     k=q2[1].k;
39     for(i=1;i<=q;i++)
40     {
41         if(q2[i].k!=k)
42         {
43             memset(ans,0,sizeof(ans));
44             k=q2[i].k;
45         }
46         ans2[q2[i].num]=get(q2[i].p);
47     }
48     for(i=1;i<=q;i++)
49         printf("%d
",ans2[i]);
50     return 0;
51 }

第二次，非递归，RE

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int ans[100100],last[100100];
 6 int a[100100];
 7 int n,k,q;
 8 int ans2[100100];//曾经忘记将排序后的查询按原序输出
 9 struct Q
10 {
11     int p,k,num;
12     bool operator<(const Q& b) const
13     {
14         return k<b.k||(k==b.k&&p<b.p);
15     }
16 }q2[100100];
17 int get(int x)
18 {
19     int x1=x;
20     if(ans[x])    return ans[x];
21 //    if(x>n)
22 //        return ans[x]=0;
23 //    else
24 //        return ans[x]=get(x+a[x]+k)+1;
25     while(x<=n)
26     {
27         last[x+a[x]+k]=x;
28         x=x+a[x]+k;
29     }
30     while(x!=x1)
31     {
32         ans[last[x]]=ans[x]+1;
33         x=last[x];
34     }
35     return ans[x];//曾经忘记return
36 }
37 int main()
38 {
39     int i;
40     scanf("%d",&n);
41     for(i=1;i<=n;i++)
42         scanf("%d",&a[i]);
43     scanf("%d",&q);
44     for(i=1;i<=q;i++)
45     {
46         scanf("%d%d",&q2[i].p,&q2[i].k);
47         q2[i].num=i;
48     }
49     sort(q2+1,q2+q+1);
50     k=q2[1].k;
51     for(i=1;i<=q;i++)
52     {
53         if(q2[i].k!=k)
54         {
55             memset(ans,0,sizeof(ans));
56             memset(last,0,sizeof(last));
57             k=q2[i].k;
58         }
59         ans2[q2[i].num]=get(q2[i].p);
60     }
61     for(i=1;i<=q;i++)
62         printf("%d
",ans2[i]);
63     return 0;
64 }

第三次，发现第一、第二次的做法会导致访问超过100000的数组，改掉，TLE

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 int ans[500100];
 6 int a[100100];
 7 int n,k,q;
 8 int ans2[500100];//曾经忘记将排序后的查询按原序输出
 9 struct Q
10 {
11     int p,k,num;
12     bool operator<(const Q& b) const
13     {
14         return k<b.k||(k==b.k&&p<b.p);
15     }
16 }q2[100100];
17 int get(int x)
18 {
19     if(ans[x])    return ans[x];
20     if(x>n)
21         return ans[x]=0;
22     else
23         return ans[x]=get(x+a[x]+k)+1;
24 }
25 int main()
26 {
27     int i;
28     scanf("%d",&n);
29     for(i=1;i<=n;i++)
30         scanf("%d",&a[i]);
31     scanf("%d",&q);
32     for(i=1;i<=q;i++)
33     {
34         scanf("%d%d",&q2[i].p,&q2[i].k);
35         q2[i].num=i;
36     }
37     sort(q2+1,q2+q+1);
38     k=q2[1].k;
39     for(i=1;i<=q;i++)
40     {
41         if(q2[i].k!=k)
42         {
43             memset(ans,0,sizeof(ans));
44             k=q2[i].k;
45         }
46         ans2[q2[i].num]=get(q2[i].p);
47     }
48     for(i=1;i<=q;i++)
49         printf("%d
",ans2[i]);
50     return 0;
51 }

至此，我丧失了信仰相信了这是道假dp...

然后，经过查资料，我找到了一种民民是早就想到过的但是却忘了用的方法...

就是将k在500以下的记录下来，500以上的直接算，不记忆化。

然后呢，又有的5次错中错误点：

1.直接算500以上的时候忘记在x>n时返回0 少了if(x>n) return 0;

2.直接算500以上的时候在不是x>n时错误地返回了get2(x+a[x]+k)+1，返回了get2(x+a[x]+k)

AC代码：

 1 #include<cstdio>
 2 int ans[100100][501];
 3 int a[100100];
 4 int k,n,q,p;
 5 int get(int x)
 6 {
 7     if(x>n)
 8         return 0;
 9     if(ans[x][k])    return ans[x][k];
10     return ans[x][k]=get(x+a[x]+k)+1;
11 }
12 int get2(int x)
13 {
14     if(x>n)
15         return 0;
16     else
17         return get2(x+a[x]+k)+1;
18 }
19 int main()
20 {
21     int i;
22     scanf("%d",&n);
23     for(i=1;i<=n;i++)
24         scanf("%d",&a[i]);
25     scanf("%d",&q);
26     for(i=1;i<=q;i++)
27     {
28         scanf("%d%d",&p,&k);
29         if(k<=500)
30             printf("%d
",get(p));
31         else
32             printf("%d
",get2(p));
33     }
34     return 0;
35 }