BZOJ2118 墨墨的等式【最短路】

题目链接

题解

orz竟然是最短路

我们去\(0\)后取出最小的\(a[i]\)，记为\(p\)，然后考虑模\(p\)下的\(B\)

一个数\(i\)能被凑出，那么\(i + p\)也能被凑出

所以我们只需找出最小的凑出\(i\)的代价

我们如果将同余下的和看作点，那么加上一个数就相当于在点间转移的边

所以我们只需跑最短路即可求出每个\(i\)的最小代价，然后就可以计算\(Bmin\)和\(Bmax\)以内分别有多少个\(i\)

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#include<queue>

#include<cmath>

#include<map>

#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)

#define REP(i,n) for (int i = 1; i <= (n); i++)

#define mp(a,b) make_pair<int,int>(a,b)

#define cls(s) memset(s,0,sizeof(s))

#define cp pair<int,int>

#define LL long long int

using namespace std;

const int maxn = 500005,maxm = 5000005;

const LL INF = 100000000000000001ll;

inline LL read(){

	LL out = 0,flag = 1; char c = getchar();

	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}

	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}

	return out * flag;

}

struct node{

	int u; LL d;

};

inline bool operator <(const node& a,const node& b){

	return a.d > b.d;

}

inline bool operator ==(const node& a,const node& b){

	return a.u == b.u && a.d == b.d;

}

struct Heap{

	priority_queue<node> a,b;

	void ck(){while (!b.empty() && a.top() == b.top()) a.pop(),b.pop();}

	int size(){return a.size() - b.size();}

	node top(){ck(); node x = a.top(); a.pop(); return x;}

	void del(node x){ck(); b.push(x);}

	void ins(node x){ck(); a.push(x);}

}H;

int N,a[maxn],P;

LL d[maxn]; int vis[maxn];

int h[maxn],ne;

struct EDGE{int to,nxt,w;}ed[maxm];

inline void build(int u,int v,int w){

	ed[++ne] = (EDGE){v,h[u],w}; h[u] = ne;

}

void work(){

	for (int i = 0; i < P; i++){

		for (int j = 1; j <= N; j++)

			build(i,(i + a[j]) % P,a[j]);

	}

	for (int i = 1; i < P; i++) d[i] = INF;

	d[0] = 0; H.ins((node){0,d[0]}); vis[0] = true;

	node u;

	while (H.size()){

		u = H.top();

		Redge(u.u) if (!vis[to = ed[k].to] && d[to] > d[u.u] + ed[k].w){

			if (d[to] != INF) H.del((node){to,d[to]});

			d[to] = d[u.u] + ed[k].w;

			H.ins((node){to,d[to]});

		}

	}

}

int main(){

	N = read(); LL L = read(),R = read(); P = INF;

	REP(i,N){

		a[i] = read();

		if (!a[i]) i--,N--;

	}

	if (!N){

		if (L) puts("0");

		else puts("1");

		return 0;

	}

	REP(i,N) P = min(P,a[i]);

	work();

	L--;

	LL ansl = 0,ansr = 0;

	for (int i = 0; i < P; i++){

		if (d[i] <= L){

			ansl++;

			ansl += (L - d[i]) / P;

		}

		if (d[i] <= R){

			ansr++;

			ansr += (R - d[i]) / P;

		}

	}

	printf("%lld\n",ansr - ansl);

	return 0;

}

巴特西

BZOJ2118 墨墨的等式【最短路】

题目链接

题解

最新文章

热门文章

巴特西

BZOJ2118 墨墨的等式 【最短路】

题目链接

题解

最新文章

热门文章

BZOJ2118 墨墨的等式【最短路】