P8060 [POI2003] Sums

henhen_ · 2023-07-20 20:36:51 · 题解

好像没有用 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;
}