洛谷P8060 [POI2003] Sums 题解

题目链接：P8060 [POI2003] Sums

题目描述：

我们给定一个整数集合 $A$。考虑一个非负整数集合 $A’$，所有属于 $A’$ 的集合的数 $x$ 满足当且仅当能被表示成一些属于 $A$ 的元素的和（数字可重复）。

比如，当 $A = \{2,5,7\}$，属于 $A’$ 的数为：$0$（$0$ 个元素的和），$2$，$4$（$2 + 2$）和 $12$（$5 + 7$ or $7 + 5$ or $2 + 2 + 2 + 2 + 2 + 2$）；但是元素 $1$ 和 $3$ 不属于 $A’$。

输入格式：

第一行有一个整数 $n$，代表集合 $A$ 的元素个数。接下来每行一个数 $a_i$ 描述一个元素。$A = \{a_1,a_2,…,a_n\}$。

接下来一个整数 $k$，然后每行一个整数，分别代表 $b_1,b_2,…,b_k$。

输出格式：

输出 $k$ 行。如果 $b_i$ 属于 $A’$，第 $i$ 行打印 TAK，否则打印 NIE。

数据范围：

对于所有数据，$1 \le n \le 5 \times 10^3$，$1 \le k \le 10^4$，$1 \le a_1 < a_2 < … < a_n \le 5 \times 10^4$，$0 \le b_i \le 10^9$。

考虑随便取一个模数 $a_i$ ，建议从小到大排序后选 $a_1$

然后求出 凑出每个 $x \in [0,a_1)$ 的所需的最小代价

或者说，用最少的 $a_i$ 凑出一个模 $a_1$ 意义下的 $x$ ，记这个数为 $d_x$

而同余最短路干的事情就是：求模 $M$ 余 $x$ 的最小基数 $d_x$

这样对于每个询问，我们只要看看 $d_{k\,\bmod\, a_1}$ 是不是小于 $k$ 就可以了

时间复杂度 $O(n a_i \log a_i)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(5e4+15)
#define M (int)(5e5+15)
int n,Q,a[N],d[M];
struct node{int u,dis;};
bool operator<(node a,node b){return a.dis>b.dis;}
priority_queue<node> q;
void dijkstra()
{
    for(int i=0; i<a[1]; i++) d[i]=INF;
    d[0]=0; q.push({0,0});
    while(!q.empty())
    {
        int u=q.top().u,dis=q.top().dis; q.pop();
        if(dis!=d[u]) continue; // 一个点可能被入队多次
        for(int i=2; i<=n; i++)
        {
            int v=(u+a[i])%a[1];
            if(d[v]>d[u]+a[i])
            {
                d[v]=d[u]+a[i];
                q.push({v,d[v]});
            }
        }
            
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    sort(a+1,a+1+n); dijkstra();
    cin >> Q;
    for(int x; Q--;)
    {
        cin >> x;
        if(d[x%a[1]]<=x) cout << "TAK\n";
        else cout << "NIE\n";
    }
    return 0;
}