【bzoj2118】 墨墨的等式

时间：2021-03-30 20:37:11

http://www.lydsy.com/JudgeOnline/problem.php?id=2118 (题目链接)

题意

　　给出${B}$的取值范围${[Bmin,Bmax]}$，求方程${a_{1}*x_{1}+a_{2}*b_{2}+~~+a_{n}*b_{n}=B}$有多少${B}$可以使等式存在非负整数解。

Solution

　　问题很容易就被转化为：用${a_{1},a_{2},a_{3},······a_{n}}$能组成多少个在范围${[Bmin,Bmax]}$内的数。这是一类经典的图论问题。

　　我们假设${a}$中最小的元素为${T}$，可以考虑用${n}$个数能够组成的数对${T}$的模的情况。用${dis[i]}$表示构成的一个数${Q}$，且${Q mod T=i}$，${Q}$是满足上述两个条件的最小值。我们在这里将题目中的区间改为具体的询问，更好的进行讨论，对于询问${X}$，设${X mod T=i}$，则有以下三种情况：

  1. ${dis[i]>x}$。由于用这${n}$个数构成的一个模${T}$为${i}$的数，这个数的最小值为${dis[i]}$，而${dis[i]>x}$，说明${X}$是无法构成的。
  2. ${dis[i]=x}$。由于用这${n}$个数构成的一个模${T}$为${i}$的数，这个数的最小值为${dis[i]}$，而${dis[i]=x}$，说明${X}$可以构成，且是能构成的模${T}$等于${i}$的最小的数。
  3. ${dis[i]<x}$。由于用这${n}$个数构成的一个比${X}$更小的${~mod~T}$为${i}$的数${Q}$，则${X~mod~T=Q~mod~T}$，且${X}$必定可以由${Q}$加上若干个${T}$得到，因此，${X}$也是可以构成的。

　　由上述三点可知，当${dis[i]<=X}$时，${X}$是可以被构成的，否则则不能。

　　现在的问题是如何求解${dis}$数组？

　　相信各位看官已经发现${dis}$数组的命名有点诡异，没错就是用最短路求解。由于${dis[i]~mod~T=i}$，${i}$的范围在${0~T-1}$内，因此可以建立${T}$个点${0,1,2,······,T-1}$。对于点${i}$和任意一个数${a[j]}$，设${k=(i+a[j])~mod~T}$，可以认为从${i}$到${k}$连条边权为${a[j]}$的边，表示可以从${~mod~T=i}$这个点，通过加上边权${a[j]}$，到达${~mod~T=k}$的点。由于${T~mod~T=0}$，即可设${T}$为数字编号为0的点。要求${X}$是否能由${n}$个数构成，就要求出${dis[X~mod~T]}$的最小值了；当${X}$大于等于${dis[X~mod~T]}$，它就能够由着${n}$个数构成，设${X~mod~T=j}$，${dis[j]}$即为${j}$这个点到达${0}$点的最短距离，它可以由0点直接加边权${a[j]}$得到，也可以经过其他中间点到达。转换后，它就是个最短路问题了。

　　再回到这个问题上。于是我们先建图，跑一遍最短路，预处理出${dis}$数组，然后枚举${i=0}$~${T-1}$，计算模${T}$为${i}$的数在区间${[Bmin,Bmax]}$中有多少个，统计答案即可。

细节

　　堆里面又忘记开long long了，尴尬。

代码

// bzoj2118

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstring>

#include<cstdio>

#include<cmath>

#include<queue>

#define LL long long

#define MOD 10007

#define inf (1ll<<60)

#define Pi acos(-1.0)

#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);

using namespace std;

const int maxn=500010;

struct edge {int to,next,w;}e[maxn*10];

struct data {

	LL num,w;

	friend bool operator < (const data a,const data b) {

		return a.w>b.w;

	}

};

int head[maxn],a[maxn],vis[maxn];

int n,cnt;

LL L,dis[maxn],R;

void link(int u,int v,int w) {

	e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].w=w;

}

void Dijkstra() {

	priority_queue<data> q;

	for (int i=0;i<a[1];i++) dis[i]=inf;

	data x=(data){0,0},y;

	dis[0]=0;

	q.push(x);

	while (!q.empty()) {

		x=q.top();q.pop();

		if (vis[x.num]) continue;

		vis[x.num]=1;

		for (int i=head[x.num];i;i=e[i].next)

			if (dis[e[i].to]>x.w+e[i].w) {

				y.w=dis[e[i].to]=x.w+e[i].w;

				y.num=e[i].to;

				q.push(y);

			}

	}

}

int main() {

	scanf("%d%lld%lld",&n,&L,&R);

	for (int i=1;i<=n;i++) scanf("%d",&a[i]);

	sort(a+1,a+1+n);

	if (!a[n]) return printf("0"),0;

	for (int i=0;i<a[1];i++)

		for (int j=2;j<=n;j++) link(i,(a[j]+i)%a[1],a[j]);

	Dijkstra();

	LL ans=0;

	for (int i=0;i<a[1];i++) if (dis[i]<=R) {

			LL l=max(0ll,(L-dis[i])/a[1]);

			if (l*a[1]+dis[i]<L) l++;

			LL r=(R-dis[i])/a[1];

			if (r*a[1]+dis[i]>R) r--;

			ans+=r-l+1;

		}

	printf("%lld\n",ans);

	return 0;

}

　　

相关文章