【BZOJ 2118】墨墨的等式

相关链接

题目传送门: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;
}

77 thoughts to “【BZOJ 2118】墨墨的等式”

  1. 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.

  2. 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!

  3. 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

  4. 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.

  5. 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!

  6. 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.

  7. 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!

  8. 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

  9. 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

  10. 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

  11. 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

  12. 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.

  13. 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

  14. 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.

  15. 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.

  16. 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.

  17. 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

  18. 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!

  19. 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

  20. 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!

  21. 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!

  22. 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.

  23. 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!

  24. 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.

  25. 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

  26. 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

  27. 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

  28. 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

  29. 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.

  30. 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!

  31. 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!

  32. 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

  33. 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.

  34. 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?

  35. 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!

发表评论

电子邮件地址不会被公开。 必填项已用*标注