Array Queries CodeForces - 797E
2018-06-17 21:55:14来源:未知 阅读 ()
Array Queries CodeForces - 797E
题意:给出一个序列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\n",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\n",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\n",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\n",get(p)); 31 else 32 printf("%d\n",get2(p)); 33 } 34 return 0; 35 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++ 模板类array 2020-05-31
- CodeForces 1326E - Bombs 2020-03-25
- CodeForces 1320D - Reachable Strings 2020-03-20
- CodeForces 1324 - Codeforces Round #627 (Div. 3) 2020-03-13
- CodeForces 710D Two Arithmetic Progressions 2020-03-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash