P8646 [蓝桥杯 2017 省 AB] 包子凑数 题解

· · 题解

来一些不一样的做法。同余最短路。

以模 a_1 的同余类为点集建图，有边 [u]\xrightarrow{w}[v] 当且仅当 u+w\equiv v\pmod{a_1}。

则 [0] 到 [x] 的一条长度为 d 的路径对应一种凑出 d 的方案。

求出 [0] 到其他同余类的最短路 d_x，则每个 [x] 中能凑出的最小数为 d_x。

注意到能凑出 d_x 就可以凑出 d_x+ka_1|k\ge 0，也就可以凑出 [x] 中所有大于等于 d_x 的数。

则每个 x 中只有 \lfloor\dfrac{d_x}{a_1}\rfloor 个小于 d_x 的数凑不出来，答案为 \sum\limits_{x=0}^{a_1-1}\lfloor\dfrac{d_x}{a_1}\rfloor。

特别地，若 d_x 不存在，则 [x] 中所有数都凑不出，答案为 INF。

复杂度 O(na_i\log(na_i))。

#include <queue>
#include <cstdio>
#include <cstring>
#define P pair<int, int>
using namespace std;
struct E
{
    int v, w, t;
} e[10050];
int n, c, z, a[150], d[150], h[150];
bool b[150];
priority_queue<P, vector<P>, greater<P>> q;
void A(int u, int v, int w)
{
    e[++c] = {v, w, h[u]};
    h[u] = c;
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    for (int i = 0; i < a[1]; ++i)
        for (int j = 2; j <= n; ++j)
            A(i, (i + a[j]) % a[1], a[j]);
    memset(d, 0x3f, sizeof d);
    q.emplace(d[0] = 0, 0);
    while (!q.empty())
    {
        int u = q.top().second;
        q.pop();
        if (!b[u])
        {
            b[u] = 1;
            for (int i = h[u], v; i; i = e[i].t)
                if (d[v = e[i].v] > d[u] + e[i].w)
                    q.emplace(d[v] = d[u] + e[i].w, v);
        }
    }
    for (int i = 0; i < a[1]; ++i)
    {
        if (d[i] == 0x3f3f3f3f)
            return !puts("INF");
        z += d[i] / a[1];
    }
    printf("%d", z);
    return 0;
}