相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2118
神犇题解:https://blog.sengxian.com/solutions/bzoj-2118
解题报告
先来看一道简单的题目:
给定$a,b,c(a,b,c \le 10^5)$,规定$x,y,z \in \mathbb{N}$
问$ax+by+cz$不能表示出的正整数中,最大的那一个是多少
我们不妨在$\bmod c$的意义下做,这样就可以只考虑$0 \sim c-1$
于是暴力用$a,b$连边,跑一边最短路
这样就可以求出在$\bmod c$的剩余系中,每一个等价类最早出现的位置
于是扫一遍,取一个$\max$就可以了
然后再看看这个题,也就是多连几条边的事吧?
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 500009; const int M = N * 12; const LL INF = 1e17; int n,a[N],done[N]; int nxt[M],to[M],cost[M],head[N]; LL dis[N],bmn,bmx,mn=INF; priority_queue<pair<LL,int> > que; inline void AddEdge(int u, int v, int c) { static int E = 1; cost[++E] = c; to[E] = v; nxt[E] = head[u]; head[u] = E; } 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 void Dijkstra() { for (int i=0;i<mn;i++) dis[i] = INF; dis[0] = 0; que.push(make_pair(0, 0)); while (!que.empty()) { int w = que.top().second; que.pop(); if (done[w]) continue; else done[w] = 1; for (int i=head[w];i;i=nxt[i]) { if (dis[to[i]] > dis[w] + cost[i]) { dis[to[i]] = dis[w] + cost[i]; que.push(make_pair(-dis[to[i]], to[i])); } } } } inline LL cal(LL lim) { LL ret = 0, tmp; for (int i=0;i<mn;i++) { if (lim < dis[i]) continue; ret += (lim - dis[i]) / mn + 1; } return ret; } int main() { n = read(); cin>>bmn>>bmx; for (int i=1;i<=n;i++) { a[i] = read(); if (a[i]) mn = min(mn, (LL)a[i]); } for (int i=1;i<=n;i++) { if (a[i] == mn) continue; for (int j=0;j<mn;j++) { AddEdge(j, (j+a[i])%mn, a[i]); } } Dijkstra(); printf("%lld\n",cal(bmx)-cal(bmn-1)); return 0; }
Thanks a lot for sharing this with all folks you actually recognise what you’re talking about!
Bookmarked. Kindly additionally seek advice from my website =).
We could have a hyperlink exchange arrangement
between us
Hi, I do believe this is a great site. I stumbledupon it 😉
I am going to revisit yet again since i have saved
as a favorite it. Money and freedom is the greatest way to change, may
you be rich and continue to guide others.
It’s very trouble-free to find out any topic on web as compared to books, as I found this piece of writing at this web page.
Spot on with this write-up, I honestly believe that this website needs far more attention. I’ll probably be
returning to read more, thanks for the advice!
Howdy! This is my first visit to your blog! We are a team of volunteers and
starting a new initiative in a community in the same niche.
Your blog provided us valuable information to work on. You have done a outstanding job!
Awesome article.
Thanks to my father who shared with me concerning this web site,
this webpage is in fact remarkable.
Greetings from Colorado! I’m bored at work so I decided to browse your website on my iphone during lunch break.
I enjoy the knowledge you present here and can’t wait
to take a look when I get home. I’m amazed at how fast your blog loaded on my
mobile .. I’m not even using WIFI, just 3G .. Anyways, very
good blog!
Thanks a lot for sharing this with all people you actually realize what you’re talking about!
Bookmarked. Please also consult with my web site =).
We can have a hyperlink exchange agreement between us
I was pretty pleased to find this page. I want to to thank you for ones time for this fantastic read!!
I definitely really liked every little bit of it and
i also have you saved as a favorite to look at new things in your site.
Hello there, just became alert to your blog through Google, and found that it’s really informative.
I am gonna watch out for brussels. I will be grateful if you continue
this in future. Many people will be benefited from your writing.
Cheers!
Hi there! Someone in my Facebook group shared this website with us so I came to give it a look.
I’m definitely loving the information. I’m bookmarking and will be tweeting this to
my followers! Outstanding blog and great design.
Amazing! This blog looks exactly like my old one! It’s
on a completely different topic but it has pretty much the same layout and design. Wonderful choice of colors!
Great article.
Thanks in favor of sharing such a pleasant thinking, post is pleasant,
thats why i have read it completely
hello!,I really like your writing so a lot!
percentage we communicate more about your post on AOL? I
need a specialist on this area to unravel my problem.
May be that’s you! Taking a look ahead to see you.
Excellent blog you have here but I was wondering if you knew of any forums that
cover the same topics discussed here? I’d
really love to be a part of community where I can get advice from other knowledgeable individuals that share the same interest.
If you have any suggestions, please let me know. Bless you!
What i do not realize is in fact how you are no
longer actually much more neatly-preferred than you may be now.
You are very intelligent. You realize therefore significantly in relation to
this matter, made me personally believe it from a lot of numerous angles.
Its like men and women aren’t interested
until it’s something to do with Girl gaga! Your personal stuffs nice.
Always take care of it up! natalielise plenty
of fish
Very quickly this site will be famous amid all blogging and site-building
people, due to it’s fastidious articles
I feel this is one of the so much vital information for me.
And i’m happy reading your article. But wanna statement on few common issues, The website taste
is ideal, the articles is really great : D. Excellent task, cheers
It’s awesome for me to have a web site, which is useful designed for
my knowledge. thanks admin
An outstanding share! I have just forwarded this onto
a coworker who has been doing a little homework on this.
And he in fact bought me lunch because I stumbled upon it
for him… lol. So let me reword this…. Thank YOU for the meal!!
But yeah, thanx for spending time to talk about this subject here on your website.
natalielise pof
We stumbled over here from a different web address and thought I might as well check things out.
I like what I see so now i’m following you. Look forward to looking into your web page again.
I am in fact glad to read this website posts which contains plenty
of helpful facts, thanks for providing these information.
Hello to every one, since I am actually keen of reading this web
site’s post to be updated regularly. It consists of nice stuff.
I relish, cause I found exactly what I used to be having a look for.
You have ended my 4 day lengthy hunt! God Bless you man. Have a
great day. Bye
Excellent blog right here! Also your website quite a bit up fast!
What web host are you the usage of? Can I get your associate hyperlink for your host?
I wish my web site loaded up as quickly as yours lol
Thanks for sharing your thoughts on descargar facebook.
Regards
Hi, Neat post. There is an issue along with your web site in web explorer, may check this?
IE still is the marketplace chief and a large component of other
people will miss your fantastic writing due to
this problem.
Nice blog here! Additionally your website lots up very fast!
What host are you using? Can I am getting your associate link to your host?
I wish my website loaded up as quickly as yours lol
Thank you for sharing your thoughts. I truly appreciate your efforts
and I am waiting for your next post thanks once again.
Hurrah, that’s what I was exploring for, what a
material! existing here at this weblog, thanks admin of this
website.
My spouse and I stumbled over here from a different page and thought I might as well check things out.
I like what I see so now i’m following you. Look forward to
going over your web page for a second time.
Hi there colleagues, how is the whole thing, and what you would like to say regarding this post, in my view its in fact remarkable in favor of me.
Hello I am so thrilled I found your blog page, I really
found you by error, while I was looking on Yahoo for something
else, Nonetheless I am here now and would just like to say kudos
for a tremendous post and a all round interesting blog (I also love the theme/design), I don’t have time to go through it all at
the minute but I have bookmarked it and also added
your RSS feeds, so when I have time I will be back to
read a great deal more, Please do keep up the superb jo.
certainly like your website but you need to test the spelling on quite a few
of your posts. Many of them are rife with spelling
problems and I to find it very troublesome to tell the truth
on the other hand I will surely come again again.
Highly descriptive article, I liked that bit. Will there be a part 2?
Magnificent beat ! I wish to apprentice while you amend your website,
how can i subscribe for a blog web site? The account helped me a acceptable deal.
I had been a little bit acquainted of this your broadcast offered bright clear concept
Hey would you mind letting me know which hosting company you’re using?
I’ve loaded your blog in 3 completely different web browsers and
I must say this blog loads a lot quicker then most. Can you suggest a good
hosting provider at a honest price? Cheers, I appreciate it!
Quality content is the key to be a focus for the viewers to
visit the web page, that’s what this web site is providing.
What’s up Dear, are you truly visiting this site daily, if so then you will definitely
take nice know-how.
This is very interesting, You are a very skilled blogger.
I’ve joined your feed and look forward to seeking more
of your great post. Also, I have shared your web site in my social networks!
Awesome blog! Is your theme custom made or did you download
it from somewhere? A theme like yours with a few simple tweeks would really make my blog shine.
Please let me know where you got your design. Thanks
It’s awesome in favor of me to have a web page, which is
beneficial for my know-how. thanks admin
This paragraph is in fact a fastidious one it helps new web users, who are wishing for blogging.
If some one wants to be updated with latest technologies then he must be
visit this web site and be up to date all the time.
First off I would like to say terrific blog!
I had a quick question in which I’d like to ask if you do not mind.
I was curious to know how you center yourself and clear your mind before writing.
I have had a tough time clearing my mind in getting my thoughts out there.
I truly do enjoy writing however it just seems like the first 10 to 15 minutes
tend to be wasted just trying to figure out how to begin. Any recommendations or
hints? Thank you!
Howdy! I know this is sort of off-topic but I needed to ask.
Does managing a well-established website such as yours take a large amount of work?
I’m brand new to blogging but I do write in my journal daily.
I’d like to start a blog so I can share my own experience
and views online. Please let me know if you have any ideas or tips for new aspiring bloggers.
Appreciate it!
Highly energetic blog, I loved that bit. Will there be a part 2?
Excellent post. I was checking continuously this blog and I am impressed!
Very helpful info specifically the last part 🙂 I
care for such info a lot. I was looking for this
particular information for a very long time. Thank you and best of luck.
Hi! I know this is somewhat off topic but I
was wondering if you knew where I could find a captcha plugin for my comment form?
I’m using the same blog platform as yours and I’m having difficulty finding one?
Thanks a lot!
I am really thankful to the holder of this web
page who has shared this fantastic piece of writing
at at this time.
Wonderful goods from you, man. I’ve understand your stuff previous to and you
are just too magnificent. I actually like what you
have acquired here, really like what you’re stating and the way in which
you say it. You make it entertaining and you still take care
of to keep it smart. I cant wait to read much more from
you. This is really a wonderful web site.
Thank you for sharing your info. I really appreciate your efforts and I am waiting for your further write ups thank you
once again.
Definitely consider that that you stated. Your favorite justification appeared
to be at the web the easiest factor to take into account of.
I say to you, I definitely get annoyed even as other people consider issues that they plainly don’t know about.
You controlled to hit the nail upon the highest and outlined out the whole
thing without having side effect , other folks can take a signal.
Will probably be back to get more. Thanks
Good day! This is kind of off topic but I need some help from an established blog.
Is it tough to set up your own blog? I’m not very techincal but I can figure things out pretty fast.
I’m thinking about setting up my own but I’m not sure where to begin.
Do you have any tips or suggestions? With thanks
Hi friends, fastidious paragraph and nice arguments commented at this place,
I am in fact enjoying by these.
Hello! Would you mind if I share your blog with my facebook group?
There’s a lot of folks that I think would
really appreciate your content. Please let
me know. Many thanks
Wonderful blog! I found it while surfing around on Yahoo News.
Do you have any suggestions on how to get listed in Yahoo News?
I’ve been trying for a while but I never seem
to get there! Thank you
Excellent pieces. Keep posting such kind of info on your blog.
Im really impressed by your blog.
Hello there, You have performed a fantastic job.
I’ll certainly digg it and in my view recommend to my friends.
I’m confident they’ll be benefited from this site.
Heya fantastic blog! Does running a blog such as this
take a massive amount work? I’ve very little expertise in coding
but I was hoping to start my own blog in the near future.
Anyway, if you have any ideas or tips for new blog owners please share.
I understand this is off subject however I simply wanted to ask.
Cheers!
I always spent my half an hour to read this blog’s articles or reviews
every day along with a cup of coffee.
Today, I went to the beach front with my kids. I found a sea shell and gave it to
my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed.
There was a hermit crab inside and it pinched her ear. She never wants to go back!
LoL I know this is totally off topic but I had to tell someone!
Its not my first time to pay a visit this site,
i am browsing this web site dailly and get pleasant data
from here daily.
Really when someone doesn’t understand then its
up to other people that they will assist, so here it happens.
Hi my loved one! I wish to say that this post is awesome, great written and come with approximately all vital infos. I?¦d like to peer more posts like this .
I love what you guys are usually up too.
This sort of clever work and reporting! Keep up
the superb works guys I’ve you guys to my blogroll.
Do you have a spam problem on this site; I also am
a blogger, and I was wanting to know your situation;
we have developed some nice methods and we are looking to trade techniques with others, please shoot me an e-mail if interested.
I simply could not leave your web site prior to
suggesting that I actually enjoyed the usual information a person supply in your guests?
Is gonna be again continuously in order to inspect new posts
I have been surfing online more than three hours today, yet I never found any
interesting article like yours. It is pretty worth enough for
me. Personally, if all site owners and bloggers made good content as you did, the net
will be a lot more useful than ever before.
Awesome issues here. I’m very happy to look your post. Thanks so much and I am having a look
ahead to contact you. Will you please drop me a e-mail?
Hi, the whole thing is going sound here and ofcourse every one is sharing information, that’s in fact fine, keep up writing.
It’s very trouble-free to find out any topic on web as compared to books, as I found this
piece of writing at this website.
Great blog here! Also your web site loads up fast! What host are you using?
Can I get your affiliate link to your host? I wish my web site loaded up as fast as yours lol
Hello colleagues, its impressive piece of writing on the topic of tutoringand entirely explained, keep it up all the time.
I used to be recommended this web site by means of my cousin. I am no longer sure whether this put up is written by him as no one else understand such targeted about my problem. You are amazing! Thanks!
I think this is a real great post.Thanks Again.
Awesome article post.Much thanks again. Really Cool.