【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;
}

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

发表评论

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