BZOJ2118: 墨墨的等式
? 解题记录 ? ? BZOJ ? ? 最短路 ?    2017-10-20 16:29:35    468    0    0

2118: 墨墨的等式

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 2271  Solved: 893
[Submit][Status][Discuss]

Description

墨墨突然对等式很感兴趣,他正在研究a1x1+a2y2+…+anxn=B存在非负整数解的条件,他要求你编写一个程序,给定N、{an}、以及B的取值范围,求出有多少B可以使等式存在非负整数解。

Input

输入的第一行包含3个正整数,分别表示N、BMin、BMax分别表示数列的长度、B的下界、B的上界。输入的第二行包含N个整数,即数列{an}的值。

Output

输出一个整数,表示有多少b可以使等式存在非负整数解。

Sample Input

2 5 10
3 5

Sample Output

5

HINT

 

对于100%的数据,N≤12,0≤ai≤5*10^5,1≤BMin≤BMax≤10^12。

 

Source

一波骚操作图论建模加最短路,原理很玄妙啊。鄙人不才(其实是懒(~ ̄▽ ̄)~ ),这篇博客就讲的比较清楚  我是“这篇博客”

#include<cstdio>
#include<cstring>
#include<queue>
#define For(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
const int maxn = 5e5 + 5;
const int inf = 0x3f3f3f3f;
struct edge {
	int v, w, next;
}e[maxn * 13];
int head[maxn], cnt, n, a[15], ax, vis[maxn];
long long dis[maxn], ans, D, U;
void adde(const int & u, const int & v, const int & w) {
	e[cnt] = (edge){v, w, head[u]};
	head[u] = cnt++;
}
void SPFA() {
	memset(dis, inf, sizeof(dis));
	deque<int > q;
	q.push_back(0);
	dis[0] = 0;
	while(!q.empty()) {
		int u = q.front();
		q.pop_front(), vis[u] = 0;
		for(register int i = head[u]; ~i; i = e[i].next) {
			if(dis[u] + e[i].w <= dis[e[i].v]) {
				dis[e[i].v] = dis[u] + e[i].w;
				if(vis[e[i].v]) continue;
				if(!q.empty() && dis[e[i].v] <= dis[q.front()]) q.push_front(e[i].v);
				else q.push_back(e[i].v);
				vis[e[i].v] = 1;
			}
		}
	}
}
int main() {
	memset(head, -1, sizeof(head));
	scanf("%d%lld%lld", &n, &D, &U);
	ax = inf;
	For(i, 1, n) scanf("%d", &a[i]), ax = min(ax, a[i]);
	For(i, 0, ax - 1)
		For(j, 1, n) adde(i, (i + a[j]) % ax, a[j]);
	SPFA();
	--D;
	For(i, 0, ax - 1) {
		if(dis[i] <= U) ans += (U - dis[i])/ax + 1;
		if(dis[i] <= D) ans -= (D - dis[i])/ax + 1;
	}
	printf("%lld", ans);
	return 0;
}

上一篇: HDU5434 Peace small elephant

下一篇: BZOJ1231: [Usaco2008 Nov]mixup2 混乱的奶牛

468 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航