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

ttwyzz · 2021-07-19 10:44:57 · 题解

不愧是国家集训队的题

写这道题呢，也算是有点缘分？随机跳题跳到了。

这道题

一道板子题，然后从此我就学会了 同余最短路

废话不多说，上正题

所谓同余最短路，就是解决类似于这样的问题 （就是上面那一道题啦）。

Q\,:有\,n\,个数,问在一定数值下可能组成的数的个数?

栗子:比如 n = 3 ，那给出的数是 \,x\,，\,y\, ， z\,，求满足\,ax + by + cz = k中\,k\,的个数。（在一定范围内

这种题在数据允许的范围内，我们一般使用背包或者直接暴力，但是很可惜，这道题我们无法用这两种方法AC ， 那么我们来引入一个新的定义，就是我们今天的主角。

同余最短路

试想一个问题，如果说，我们只加 \,y\,，\,z\,，在允许范围内，能达到的数再加若干 个\,x\,都是能达到的，那么就以\bmod \,x\,的值做分类。

换句话来说就是，要能用若干个 \,y\,，\,z\,达到的一定能再加上\,x\,而达到。

那么我们就把这类题抽象成了图论题，就是以\,n\,个数中最小的一个作为模数（最优）。

for(int i = 0; i < x; ++i)
{
    add(i, (i+y) % x , y);
    add(i, (i+z) % x , z);
}

我们在这个图里面跑一遍最短路，样我们就求出了最小的余数为 i 的能达到的数。h 指上限，从 1 到 h。

最后统计答案。

for(int i = 0; i < x; ++i)
{
    if(d[i] <= h)
    {
        ans += (h-d[i])/x + 1;// 注意这里是有+1的
    }
}

那么我们抽象到这题上就是将\,h\,变为 \,l\,和\,r\,，是闭区间那我们就在最后统计的时候做点手脚。

for(ll i = 0; i < w[1]; ++i)
{
    if(d[i] <= r) // 如果小于r ，就加答案 
    {
        ans += (r - d[i])/w[1] + 1;
    }
    if(d[i] < l) // 如果小于l ，说明不合法，减去这一部分 
    {
        ans -= (l - 1 - d[i])/w[1] + 1;
    }
}

最后，你们最爱的全套代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e6 + 20;

int n;
ll w[15];
ll h,ans;
ll d[maxn];
ll l,r; 
bool v[maxn];

struct N{
    int to,net,va;
}a[maxn << 2];
int head[maxn];
int cnt;

void add(int x,int y,int w)
{
    a[++cnt].to = y;
    a[cnt].net = head[x];
    a[cnt].va = w;
    head[x] = cnt;
}

void SPFA()
{
    memset(v,0,sizeof v);
    memset(d,0x3f3f3f3f,sizeof d);
    queue<int> q;
    q.push(0);
    v[0] = 1;
    d[0] = 0;// 注意从0开始，因为基数为 0，换句话说就是，余数从0开始算 
    while(!q.empty())
    {
        int from = q.front(); q.pop();
        v[from] = 0;
        for(int i = head[from]; i; i = a[i].net)
        {
            int to = a[i].to;
            int va = a[i].va;
            if(d[to] > d[from] + va)
            {
                d[to] = d[from] + va;
                if(!v[to])
                {
                    v[to] = 1;
                    q.push(to);
                }
            }
        }
    }
}

int main()
{
    scanf("%d%lld%lld",&n,&l,&r);
    for(int i = 1; i <= n; ++i) scanf("%lld",&w[i]);
    sort(w+1,w+n+1);
    for(ll i = 0; i < w[1]; ++i)
    {
        for(int j = 2; j <= n; ++j)
        {
            add(i, (i+w[j]) % w[1] , w[j]);
        }
    }
    SPFA();
    for(ll i = 0; i < w[1]; ++i)
    {
        if(d[i] <= r) // 如果小于r ，就加答案 
        {
            ans += (r - d[i])/w[1] + 1;
        }
        if(d[i] < l) // 如果小于l ，说明不合法，减去这一部分 
        {
            ans -= (l - 1 - d[i])/w[1] + 1;
        }
    }
    printf("%lld\n",ans);
    return 0;
}

完结撒花！