相关链接
题目传送门：http://codeforces.com/contest/797/problem/E
解题报告
我们发现暴搜加上记忆化的复杂度是$O(n \sqrt{n})$的
于是暴搜就好了
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100009;
struct Query{int p,k,id;}q[N];
int n,m,stp[N],a[N],ans[N];
queue<int> vis;
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline bool cmp(const Query &A, const Query &B) {
return A.k < B.k;
}
inline void init() {
for (;!vis.empty();vis.pop()) {
stp[vis.front()] = 0;
}
}
int DFS(int w, int k) {
if (w > n) return 0;
else if (stp[w] > 0) return stp[w];
else return vis.push(w), stp[w] = DFS(w + a[w] + k, k) + 1;
}
int main() {
n = read(); for (int i=1;i<=n;i++) a[i] = read();
m = read(); for (int i=1;i<=m;i++) q[i].p = read(), q[i].k = read(), q[i].id = i;
sort(q+1, q+1+m, cmp);
for (int i=1;i<=m;i++) {
if (i > 1 && q[i].k != q[i-1].k) init();
ans[q[i].id] = DFS(q[i].p, q[i].k);
}
for (int i=1;i<=m;i++) printf("%d\n",ans[i]);
return 0;
}
哇塞，居然是沙发？留个名
Howdy just wanted to give you a quick heads up and let
you know a few of the images aren’t loading correctly. I’m
not sure why but I think its a linking issue. I’ve tried it
in two different internet browsers and both show the same outcome.
What’s up, I wish for to subscribe for this weblog to take most up-to-date updates, thus
where can i do it please assist.
Marvelous, what a website it is! This web site gives useful information to us, keep it up.
With havin so much content do you ever run into
any problems of plagorism or copyright infringement?
My site has a lot of exclusive content I’ve either
authored myself or outsourced but it appears
a lot of it is popping it up all over the internet without my permission. Do you
know any ways to help protect against content from being stolen?
I’d really appreciate it.
Someone necessarily assist to make severely posts
I might state. That is the first time I frequented your
website page and to this point? I amazed with the research you made to create
this actual publish incredible. Excellent process!
Thanks a bunch for sharing this with all people you actually know what
you are speaking approximately! Bookmarked. Kindly also seek advice from my web
site =). We may have a hyperlink trade arrangement between us
I’m curious to find out what blog system you have been using?
I’m having some minor security issues with my latest blog and I’d like
to find something more secure. Do you have any recommendations?
Hi there colleagues, pleasant piece of writing and nice urging commented
here, I am in fact enjoying by these.
I know this if off topic but I’m looking into starting my own weblog and was curious what all is required to get set up? I’m assuming having a blog like yours would cost a pretty penny? I’m not very web smart so I’m not 100 sure. Any tips or advice would be greatly appreciated. Cheers
I have learn some excellent stuff here. Definitely price
bookmarking for revisiting. I surprise how a lot effort you put to make such a fantastic informative web site.
I’m not that much of a online reader to be honest but your
sites really nice, keep it up! I’ll go ahead and bookmark
your site to come back in the future. Many thanks
It’s very effortless to find out any matter on net as
compared to books, as I found this piece of writing
at this web site.
I have been browsing on-line greater than three hours
as of late, but I by no means discovered any attention-grabbing article like yours.
It is pretty worth sufficient for me. In my view, if all
webmasters and bloggers made excellent content material as you probably did,
the net shall be much more helpful than ever before.
Pretty! This was an incredibly wonderful article.
Thank you for supplying this info.
Pretty element of content. I simply stumbled upon your web
site and in accession capital to say that I acquire in fact enjoyed account your
weblog posts. Any way I’ll be subscribing to your feeds and even I fulfillment you get entry to constantly fast.
Hello, i think that i saw you visited my weblog thus i came to “return the favor”.I am attempting to find things to enhance my website!I suppose its ok to use some of your ideas!!
I read this paragraph completely on the topic
of the comparison of most up-to-date and earlier technologies, it’s amazing
article.
When someone writes an piece of writing he/she
keeps the idea of a user in his/her mind that how a user can be aware of it.
Therefore that’s why this piece of writing is perfect. Thanks!
I am regular reader, how are you everybody? This article posted at this web page is genuinely fastidious.
You’ve made some good points there. I checked on the web to find out more about the
issue and found most individuals will go along with your views
on this website.
I’m more than happy to uncover this page. I need to
to thank you for your time for this particularly wonderful read!!
I definitely enjoyed every bit of it and i also have you saved
as a favorite to look at new stuff in your web site.
Quality content is the important to attract the people to
go to see the web page, that’s what this website is providing.
I went over this internet site and I believe you have a lot of fantastic info , saved to fav (:.