餓
(hungry.pas/c/cpp)

【背景描述】

給出?個面值分別為?? 的紙幣，每種紙幣有無限張。另有?次詢問，每次詢問一個價格?，問用若干張紙幣是否可以恰好得到?。

【輸入格式】

第一行兩個整數(shù)?，?。

接下來一行?個整數(shù)，第?個整數(shù)表示?? 。

接下來?行，每行一個整數(shù)?表示詢問。

【輸出格式】
對于每個詢問輸出一行一個整數(shù)表示答案，可行輸出1，無解輸出?1。
【樣例輸入】
2 2
2 3
5
1
【樣例輸出】
1
-1
【數(shù)據(jù)規(guī)模】
對于 30% 的數(shù)據(jù)，? ≤ 100000
對于另外 10% 的數(shù)據(jù)， ? = 2。
對于另外 30% 的數(shù)據(jù)， ? ≤ 5。
對于 100% 的數(shù)據(jù)，1 ≤ ? ≤ 50，1 ≤ ?_i, ? ≤ 100000，1 ≤ ? ≤ 10¹⁸

?

題意：給定n個數(shù)，q個詢問，每個詢問問這個數(shù)能不能被上面n個數(shù)湊出來

考慮對于模a[1]的每一個值，計算出用a[2]~a[n]表示出的最小的數(shù)。

即dist[i]表示最小的模a[1]=i的數(shù)，且dist[i]可以用a[2]~a[n]表示出來，注意不限制每個數(shù)用多少次。

很顯然，對于詢問x,若i = x % a[1],dist[i]存在且小于等于x的話x就可以被表示出來（就是dist[i]不斷加a[1]），而若是存在但是大于x的話一定表示不出來，因為根據(jù)定義dist[i]是最小的的能被a[2]~a[n]表示出來的模a[1]=i的數(shù)。

計算dist[i]就是跑一遍最短路

#include<bits/stdc++.h> using namespace std;typedef long long LL; const int N=1e5+15; int n,Q; int a[N]; LL dis[N]; bool inq[N]; queue <int> q; void Spfa() {memset(dis, -1, sizeof dis) ; dis[0] = 0, q.push(0), inq[0] = 1; while (q.size()) { int cur = q.front() ; q.pop() ; inq[cur] = 0 ; for (int i = 2; i <= n; i ++) {int to = (cur + a[i]) % a[1], w = a[i] ; if (dis[to] < 0 || dis[to] > dis[cur] + w) {dis[to] = dis[cur] + w ; if (!inq[to]) inq[to] = 1, q.push(to) ; }}} } int main() {freopen("hungry.in","r",stdin);freopen("hungry.out","w",stdout);scanf("%d%d", &n, &Q) ; for (int i = 1; i <= n; i ++) scanf("%d", &a[i]) ; sort(a + 1, a + n + 1) ; Spfa() ; while (Q --) { LL x ; scanf("%I64d", &x) ; if (dis[x % a[1]] != -1 && dis[x % a[1]] <= x) puts("1") ;else puts("-1") ; } }

想要數(shù)據(jù)的話Q我，3260540979

轉(zhuǎn)載于:https://www.cnblogs.com/xxzh/p/9372366.html

總結(jié)

以上是生活随笔為你收集整理的[湖南师大集训2018 7 26] hunger 解题报告 (SPFA)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。