// 同余最短路 Dijkstra 算法 O(NlogN)
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;

const int N=5e4+5,inf=1e18;
int n,a[N],mi,k,b;
int d[N],vis[N];

void dijkstra(){
  for(int i=0;i<mi;++i) d[i]=inf; d[0]=0;
  priority_queue<pii,vector<pii>,greater<pii> > q; 
  q.push({0,0});
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(vis[u]) continue; vis[u]=1;
    for(int i=2; i<=n; i++){ //枚举数
      int v=(u+a[i])%mi;
      if(d[v]>d[u]+a[i]){
        d[v]=d[u]+a[i]; //最短路
        q.push({d[v],v});
      }
    }
  }
}
signed main(){
  scanf("%lld",&n);
  for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
  sort(a+1,a+n+1); mi=a[1]; //最小整数

  dijkstra();
  scanf("%lld",&k);
  while(k--){
    scanf("%lld",&b);
    printf("%s\n",d[b%mi]<=b?"TAK":"NIE");
  }
}

好像没有用 spfa 写的题解 （spfa，它死了）。

题目大意

给定一个集合 $A$，询问 $k$ 次，每次询问一个整数 $b$，问 $b$ 是否能被表示成一些属于 $A$ 集合的和（$0$ 也属于 $A$）。

思路

需要具备的知识点：同余最短路。

如果是初学者可以先做这道题。

其实这道题就是跳楼机的升级版，先在 $A$ 中取最小值 $minn$，然后对 $a_i$ 中的其他值进行扩展。$dis_i$ 的意义是模 $k$ 意义下等于 $i$ 的最小值。

用最短路跑出 $dis_i$ 的值，对于每次询问，我们只判断 $dis_{x\bmod a}$ 与 $x$ 的关系即可。

附上代码

#include<bits/stdc++.h>
#define int long long //记得开long long 
using namespace std;
const int N=5e6+10;
int head[N],cnt,vis[N],tot,a[N],dis[N];
int n,l,r,minn=0x3f3f3f3f3f3f3f3f; 
queue<int>q;
inline void spfa(){//裸spfa暴力求最短路 
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	q.push(0);
	vis[0]=1;
	dis[0]=0;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=1;i<=n;i++){
			if(a[i]==minn)continue;
			int y=(x+a[i])%minn;
			if(dis[y]>dis[x]+a[i]){
				dis[y]=dis[x]+a[i];
				if(!vis[y]){
					q.push(y);
					vis[y]=1;
				}
			}
		}
	}
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		minn=min(minn,a[i]);
	}
	spfa();
	int k;
	scanf("%lld",&k);
	while(k--){
		int c;
		scanf("%lld",&c);
		printf("%s\n",dis[c%minn]<=c ?"TAK":"NIE");//不要把输出打错，不然会像我一样调试半天（orz） 
	}
	return 0;
}