相关链接
题目传送门:http://codeforces.com/contest/788/problem/C
官方题解:http://codeforces.com/blog/entry/51312
解题报告
假设取$x$个物品的时候原问题有解,且第$i$个物品的编号为$b_i$
那么此时满足这个等式:$\sum\limits_{i=1}^{x}{a_{b_i}}=nx$
这个看起来既不满足单调性,又不能方便地$DP$
但如果我们把$n$给减到$a_i$里去,那么就是$\sum\limits_{i=1}^{x}{a_{b_i}}=0$
这个就好办了,直接搞一个$O(n^2)$的那个$BFS$
这个技巧应用较为广泛,还有一些升级版本
比如这个题:http://oi.cyo.ng/?p=3069
Code
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 2009;
const int M = 2000009;
const int BAS = 1000;
int n,m,tot,dis[N],head[N];
int nxt[M],to[M],_hash[M];
queue<int> que;
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;
}
int main() {
n = read(); m = read();
for (int i=1;i<=m;i++) _hash[++tot] = read() - n;
sort(_hash+1, _hash+1+tot);
tot = unique(_hash+1, _hash+1+tot) - _hash - 1;
for (int i=1;i<=tot;i++) {
dis[_hash[i] + BAS] = 1;
que.push(_hash[i] + BAS);
}
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=1,t;t=w+_hash[i],i<=tot;i++) {
if (t < 0 || t > BAS*2 || dis[t]) continue;
dis[t] = dis[w] + 1; que.push(t);
}
}
cout<<(dis[BAS]?dis[BAS]:-1);
return 0;
}
Hiya very nice blog!! Man .. Excellent .. Amazing ..
I will bookmark your site and take the feeds also? I am glad
to find numerous helpful information here in the put up, we
want work out more strategies in this regard, thank you for sharing.
. . . . .
Thanks a lot for sharing this with all folks you really know what you’re speaking about!
Bookmarked. Please also discuss with my site =).
We may have a link change arrangement among us
I don’t even know how I ended up here, but I thought this post was great.
I do not know who you are but certainly you are going
to a famous blogger if you aren’t already 😉 Cheers!
Hi to all, the contents existing at this web site are actually amazing for people knowledge, well, keep up the nice work fellows.
Spot on with this write-up, I really think this amazing site needs a great
deal more attention. I’ll probably be returning to see more,
thanks for the info!
What’s up mates, its enormous post about teachingand fully explained, keep it up all the time.
Hi, I do think this is a great website. I stumbledupon it ;
) I will revisit once again since I saved as a favorite
it. Money and freedom is the greatest way to change, may you be rich and continue to help others.
It’s an awesome article in favor of all the online visitors; they will take advantage from it I
am sure.
Can I simply just say what a comfort to discover somebody who really understands what they’re talking
about on the net. You definitely know how to bring an issue to light and make it important.
More people ought to check this out and understand this side of your story.
I can’t believe you aren’t more popular given that you most certainly have the gift.
That is really attention-grabbing, You’re an overly professional blogger.
I have joined your feed and look forward to searching for extra of your great
post. Also, I have shared your site in my social networks
889826 417670Hey. Neat post. There is actually a difficulty together with your web site in firefox, and you may want to check this The browser could be the market chief and a large component of other folks will omit your exceptional writing because of this issue. 840506
666353 568864Could it be okay to write several of this on my small internet web site only incorporate a 1 way link towards the internet site? 739791
171981 511543This design is spectacular! You definitely know how to keep a reader amused. Between your wit and your videos, I was almost moved to start my own blog (well, almost…HaHa!) Fantastic job. I really loved what you had to say, and more than that, how you presented it. Too cool! 801433
Hi my loved one! I wish to say that this post is awesome,
nice written and come with almost all important infos.
I’d like to see extra posts like this .
As a Newbie, I am always exploring online for articles that can be of assistance to me. Thank you
Good day! This is my first visit to your blog! We are a collection of volunteers and starting a new project in a community
in the same niche. Your blog provided us useful information to work
on. You have done a extraordinary job!
Please let me know if you’re looking for a article writer
for your site. You have some really great articles and
I believe I would be a good asset. If you ever want to
take some of the load off, I’d really like to write some content for your blog in exchange for a link back to mine.
Please shoot me an email if interested. Cheers!
Very good post. I am experiencing many of these issues as well..
Good day! I know this is kinda off topic but I was wondering which
blog platform are you using for this site? I’m getting tired of WordPress because I’ve had issues with hackers and I’m looking at alternatives for another platform.
I would be awesome if you could point me in the direction of a good platform.
Good article. I’m dealing with some of these issues as well..
Have you ever thought about including a little bit more than just your articles?
I mean, what you say is important and all. Nevertheless imagine if you added some great visuals or
video clips to give your posts more, “pop”! Your content is
excellent but with pics and clips, this website could certainly be one of the
best in its field. Good blog!
Right here is the perfect web site for everyone who hopes to find out about this topic.
You realize so much its almost tough to argue with you (not
that I really will need to…HaHa). You definitely put a fresh spin on a subject
that’s been written about for many years. Wonderful stuff, just excellent!
Hiya! Quick question that’s entirely off topic.
Do you know how to make your site mobile friendly?
My site looks weird when viewing from my iphone4. I’m trying to find a theme or plugin that might be able to correct this issue.
If you have any recommendations, please share. Appreciate it!
I am curious to find out what blog system you’re
working with? I’m having some minor security problems with my latest blog
and I would like to find something more safe.
Do you have any suggestions?
Everything published made a bunch of sense.
But, what about this? suppose you typed a catchier title?
I mean, I don’t wish to tell you how to run your website, but suppose you added something that grabbed a person’s attention? I mean 【Codeforces 788C】The Great
Mixing – Qizy's Database is kinda plain. You could
peek at Yahoo’s front page and watch how they
write news headlines to get people to click.
You might add a related video or a picture or two to grab readers interested about everything’ve got to say.
Just my opinion, it would make your posts a little livelier.
My programmer is trying to convince me to move to .net from PHP.
I have always disliked the idea because of the costs.
But he’s tryiong none the less. I’ve been using WordPress on a number of websites for
about a year and am anxious about switching to another platform.
I have heard great things about blogengine.net. Is there a way I can import all my wordpress
content into it? Any help would be really appreciated!
When I originally commented I appear to have clicked the -Notify me when new
comments are added- checkbox and now each time a comment is
added I receive 4 emails with the exact same comment.
Perhaps there is an easy method you are able to remove me from that service?
Kudos!
Thanks for the auspicious writeup. It actually was a enjoyment account it. Glance advanced to more brought agreeable from you! By the way, how can we keep in touch?