bzoj 2118: 墨墨的等式 最短路

缘起

一道有脑洞的题目~

bzoj 2118: 墨墨的等式

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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。

Time Limit: 10 Sec  Memory Limit: 259 MB

本题咋一看以为是完全背包~ 但是完全不能这么做~ 因为B太大了~ 耻（真）辱（香）的看了题解, 真是学到了，还能这么玩儿~

令 t 是 {a1,..,an} 中最小的那个. 令 0<=r<t, 则如果 k*t+r 能被表示的话, 则对于任何k1>=k, k1t+r 也能被表示. 所以如果我们知道对每个r（0<=r<t）能被表示成 kt+r的最小的那个正整数的话, 比如对于 r = 1, 我们知道能被a1,…,an 表示的最小的形如 kt+1的正整数的话, 令k0\t+1是这个数, 则 {k*t+1 | k>=k0} 就都能被表示出来. 即本题其实是这个样子的.

一旦我们知道了上面直方图的每个直方顶部的纵坐标Y的话, 对于给定的B范围[lo,hi], 则就可以非常方便的计算出[max(lo,Y),hi] 中能被a1,…,an表示的形如kt+r的数的个数了. 即问题化归为

1
给你一个范围 [lo, hi] 问里面形如 kt+r 的数有多少个? 其中k和r是固定的.

这是一道简单的小学数学问题而已. 所以我们集中注意力在怎么求出Y来? 这里的思路真的是学到了. 将 0,1,…,t-1 视作t个点, 这是模掉a1,…,an中最小的那个整数的余数. 然后做下面的事情

1
2
3
4
5
6
7
8
for(int i = 0;i<t;i++)
{
	for(int j = 1;j<=n; j++)
	{
		int k = (i+a[j])%t;
		则构建一条 i->k的 弧, 弧长是 a[j];
	}
}

因为上面的图中每个点其实代表状态. 而状态转移就是通过加上 a[1,..,n]中的某些个数来实现的. 所以这就自然得到了一张有向图. 然后我们从0出发（因为显然能表示为kt+r, r=0 的最小非负整数是0, 代价也是0），求出单源最短路. 即得到了要到达各个顶点的最小代价, 所以我们就求出了上面直方图的各个直方的顶部纵坐标.

都说到这里了,剩下的就是打代码了~ 对于下面代码的dijkstra有疑惑的话，参见【1】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
//#define LOCAL
typedef long long LL;
typedef pair<LL,LL> P;
const LL maxn = 500005, inf = 1ll<<60;
LL n,nn,lo,hi, a[15], mmin, cnt, head[maxn],d[maxn]; // nn是a[0,..,n-1]中正整数的个数
bool v[maxn];

struct Arc
{
	LL from,to,nxt,len;
}g[5000005];

void addarc(LL from, LL to,LL len)
{
	g[cnt].from = from, g[cnt].to = to, g[cnt].nxt = head[from], g[cnt].len = len;
	head[from] = cnt++;
}

void dijkstra()
{
	for (LL i = 1;i<mmin;i++)
	{
		d[i] = inf;
	}
	d[0] = 0;
	priority_queue<P, vector<P>, greater<P> > pq;
	pq.push(P(0,0));
	while(!pq.empty())
	{
		P top = pq.top();
		pq.pop();
		LL h = top.second;
		if (v[h])
		{
			continue;
		}
		v[h] = true;
		for (LL i = head[h],to,t;~i; i = g[i].nxt)
		{
			to = g[i].to;
			t = d[h]+g[i].len;
			if (!v[to] && d[to]>t)
			{
				d[to] = t;
				pq.push(P(t,to));
			}
		}
	}
}

inline LL kk(LL begin, LL end, LL m, LL r) // [begin,end]中模掉m余数为r的个数
{
	LL r1 = begin%m;
	begin += r1<=r?(r-r1):(m+r-r1); // begin 模掉 m 余 r了
	r1 = end%m;
	end-=r1>=r?(r1-r):(m+r1-r); // end 模掉m余r了
	if (begin>end)
	{
		return 0; // 注意判断, wa了一发~
	}
	return (end-begin)/m+1;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	memset(head,-1,sizeof(head));
	mmin = inf;
	scanf("%lld%lld%lld", &n, &lo, &hi);
	for (LL i = 0;i<n;)
	{
		scanf("%lld", a+i);
		if (a[i]) // 0就不需要考虑了
		{
			mmin = min(mmin, a[i]);
			++nn;
			++i;
		}
	} // 最后 a[0,...,nn-1]就是正整数
	for (LL i = 0;i<mmin; i++)
	{
		for (LL j = 0,t;j<nn; j++)
		{
			t = (i+a[j])%mmin;
			addarc(i,t,a[j]);
		}
	}
	dijkstra(); // 跑完最短路得到d[0]、d[1]、...d[mmin-1]的最小值
	LL ans = 0;
	for (LL i = 0;i<mmin;i++)
	{
		ans+=kk(max(lo,d[i]),hi, mmin,i);
	}
	printf("%lld\n", ans);
	return 0;
}

ac情况

3390569 yfsyfs1 2118 Accepted 168452 kb 4568 ms C++/Edit 2257 B 2019-10-30 19:21:04

最后还是想说一句——算法牛逼！！！

参考

【1】https://yfsyfs.github.io/2019/08/22/hdu-2544-dijkstra%E6%A8%A1%E6%9D%BF/