洛谷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;
}