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

· · 题解

解析

P3403 跳楼机 升级版。

我们可以仿照那题的经典做法，使用同余最短路解决问题。

对于所有的 a_i，我们先将值为 0 的元素去掉，然后找到最小值，设为 base。

之后我们枚举所有的剩余类 [\ i\ ] 和给定数组 a_i，按照如下方式建图。

for(int i=0;i<base;i++)
{
    for(int j=1;j<=n;j++)
        add(i,(i+a[i])%base,a[i]);
}

然后在这个图上跑最短路。

这样之后，我们跑出来的最短路数组 f[x] 表示的就是我们能够拼出来的最小的在剩余系 [x] 中的数。

现在我们考虑如何计算 [l,r] 中满足条件的数。

首先我们能够轻易计算出 [1,x] 中满足条件的数：\sum_{i=1}^{base-1}(\frac{x-f[i]}{base}+1)。

显然的是区间满足条件的数是类型与有前缀和性质的。

所以我们只需要计算：[1,r] 中满足条件的数 - [1,l-1] 中满足条件的数。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> PII;

const int N=5e6+10;

int n;
ll l,r,base=1e9;
vector<ll> a;
int head[N],ver[N<<1],nxt[N<<1],tot=0;
ll edg[N<<1];
void add(int x,int y,ll z)
{
    ver[++tot]=y; edg[tot]=z; nxt[tot]=head[x]; head[x]=tot;
}
bool vis[N];
ll f[N];
priority_queue<PII, vector<PII>,greater<PII> > q;

void dijkstra()
{
    memset(f,0x42,sizeof f);
    memset(vis,0,sizeof vis);
    f[0]=0; q.push({0,0});
    while(q.size())
    {
        int x=q.top().second;
        q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i];
            if(f[y]>f[x]+edg[i])
            {
                f[y]=f[x]+edg[i];
                q.push({f[y],y});
            }
        }
    }
}

int main()
{
    scanf("%d%lld%lld",&n,&l,&r);
    for(int i=1;i<=n;i++)
    {
        int x;
        scanf("%d",&x);
        if(x) a.push_back((ll)x),base=min(base,(ll)x);
    }
    for(int i=0;i<base;i++)
    {
        for(int j=0;j<a.size();j++)
            add(i,(i+a[j])%base,a[j]);
    }
    dijkstra();
    ll ansl=0,ansr=0;
    for(int i=0;i<base;i++)
    {
        if(r>=f[i]) ansr+=(r-f[i])/base+1LL;
        if(l-1>=f[i]) ansl+=(l-1-f[i])/base+1LL;]);
    }
    printf("%lld",ansr-ansl);
    return 0;
}