题解 P2371 【[国家集训队]墨墨的等式】

· · 题解

首先，本题我们发现B很大(≤10的12次方)，N很小(≤12)。

那么，我们可以暴力吗？

好像只有20分的样子啊...

...

...

所以我们要想优化(废话)

对于40%的数据，

我们想到背包。

这不是完全背包裸题吗！

所以我们用O(Bn)的复杂度拿到了40分。

... ...

对于100%的数据：

我们对a[]数组找到一个最小值,把它存入mn (srf很懒，排了个序QAQ)

可以发现，如果式子的值可以达到 k * mn + t

那么这个式子的值也一定可以达到 (k + i) * mn + t.

因此，我们可以对每个余数t建一个点，(0 ≤ t ≤ mn)

在 t 和 (t + a[i]) % mn 之间连一条有向边

用SPFA求一下从0开始的最短路。

求得最短路后，我们对于每个余数统计答案即可。

代码：

#include <bits/stdc++.h>
#define N 15
#define M 500005
#define LL long long

using namespace std;

LL INF = (LL)1 << 62; //INF开大！！！
LL n,l,r,a[N];
LL k,dis[M];

LL ans,ll,rr,t1,t2;

queue<int>Q; int x,now;
bool vis[M];

int main(){
    ios::sync_with_stdio(false); //卡常专用
    cin >> n >> l >> r;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    sort(a+1,a+n+1);
    k = a[1];

    //SPFA
    dis[0] = 0;
    for (int i = 1; i < k; ++i) dis[i] = INF;

    while (!Q.empty()) Q.pop();
    Q.push(0);

    memset(vis,0,sizeof(vis));
    vis[0] = 1;

    while (!Q.empty()){
        x = Q.front(); Q.pop();
        for (int i = 1; i <= n; ++i){
            now = (x + a[i]) % k;
            if (dis[now] > dis[x] + a[i]){
                dis[now] = dis[x] + a[i];
                if (!vis[now]) Q.push(now);
                vis[now] = 1;
            }
        }
        vis[x] = 0;
    }

    ans = 0;
    for (int i = 0; i < k; ++i)
        if (dis[i] != INF) dis[i] -= i,dis[i] /= k;

    //统计ans
    for (int i = 0; i < k; ++i)
        if (dis[i] != INF){
            ll = (l - 1 - i) / k;
            rr = (r - i) / k;
            t1 = ll - dis[i] + 1;
            t2 = rr - dis[i] + 1;
            t1 = max((LL)0,t1);
            t2 = max((LL)0,t2);
            ans = ans - t1 + t2;
        }
    //收工
    cout << ans << endl;
    return 0;
}