给你n个数\(a_{1...n}\)，问你这n个数用加法组成的所有数中∈[1，p]的数的个数。
询问有m次。每次询问给定一个\(p_i\)
$ n <13,m<1e6,p_i<1e18,a_i<5e5$
大家可以先去看一下这道题(本题的前一部分) 传送门
设Min为\(a_i\)中的最小值。
所以，我们对于任意数x，若x可以被表示，\(x+a_i×k\)均可以被表示。
所以我们要求出余数\(x∈[0,Min)\)被表示所需的最小值。
考虑最短路
对于\(x∈[0,Min),连接x与x+a_i\),边权为\(a_i\)
然后就可以跑dijkstra。
对于每一个询问.\[ ans_i = \sum _{j = 1}^{dis_j \leq p_i} \frac{p_i - dis_j}{Min} \]
然后就可以愉快的拿到50分了。
打成这样竟然只给50,这部分分给的
好了，现在要考虑询问之间的转移。
第一个想到前缀和优化。
但是，怎么优化呢？
给p数组和dis数组从小到大排个序。
然后将p表示成\(s×Min+t\)的形式，\(dis_i\)表示成\(d×Min+c\)的形式。
这样的话\[ ans_i=\sum_{j = 1}^{dis_j \leq p_i} (a_i − b_j) − (c_i < d_j) \] 好啦，这样就可以用前缀和+树状数组优化了。
#include <bits/stdc++.h> using namespace std; #define DEBUG(...) fprintf(stderr, __VA_ARGS__) #define mp make_pair #define fst first #define snd second template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } inline int read(){ int res = 0, fl = 1; char r = getchar(); for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1; for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48; return res * fl; } typedef long long LL; inline LL Lread(){ LL res = 0, fl = 1; char r = getchar(); for (; !isdigit(r); r = getchar()) if(r == '-') fl = -1; for (; isdigit(r); r = getchar()) res = (res << 3) + (res << 1) + r - 48; return res * fl; } typedef pair<LL, int> pii; const int Maxn = 5e5 + 10; struct MAP{ LL to, v; }; LL mod; LL a[Maxn], Min; LL dis[Maxn]; bool vis[Maxn]; pii ASK[Maxn << 1]; LL ans[Maxn << 1]; vector<MAP> g[Maxn]; namespace BIT{ LL tre[Maxn]; inline int lowbit(int x) { return x & -x;} inline void Add(int pos){for ( ++pos; pos <= mod; pos += lowbit(pos)) ++tre[pos];} inline LL Query(int pos){ LL sum = 0; for ( ++pos; pos >= 1; pos -= lowbit(pos)) sum += tre[pos]; return sum; } } void dijstra(int s){ priority_queue<pii> Q; memset(dis, 0x3f, sizeof dis); Q.push(mp(0,0)); dis[s] = 0; while(!Q.empty()){ int now = Q.top().snd; Q.pop(); if(vis[now]) continue; vis[now] = 1; for (int i = g[now].size() - 1; i >= 0; --i){ int nxt = g[now][i].to; if(vis[nxt]) continue; if(dis[nxt] > dis[now] + g[now][i].v){ dis[nxt] = dis[now] + g[now][i].v; Q.push(mp(-dis[nxt],nxt)); } } } } int main() { freopen("couplet.in", "r", stdin); freopen("couplet.out", "w", stdout); LL n = read(), m = read(); Min = 1e9 + 10; for (int i = 1; i <= n; ++i) { a[i] = read(); chkmin(Min, a[i]); } mod = Min; for (int i = 0; i < Min; ++i) for (int j = 1; j <= n; ++j){ int nxt = (i + a[j]) % mod; if(nxt == i) continue; g[i].push_back((MAP){nxt, a[j]}); } dijstra(0); sort(dis + 1, dis + 1 + Min); for (int i = 1; i <= m; ++i) ASK[i].fst = Lread(),ASK[i].snd = i; sort(ASK + 1, ASK + 1 + m); LL top = 0; LL sum = 0; BIT::Add(dis[0]); for (int i = 1; i <= m; ++i){ LL p = ASK[i].fst; while(top < (Min - 1) && dis[top + 1] <= p){ ++top; BIT :: Add(dis[top] % mod); sum += 1ll * dis[top] / Min; } ans[ASK[i].snd] = 1ll * (p / Min) * (top + 1) - sum; ans[ASK[i].snd] += 1ll * BIT :: Query(p % mod); } for (int i = 1; i <= m; ++i) printf("%lld\n",ans[i] - 1); return 0; }转载于:https://www.cnblogs.com/LZYcaiji/p/10397821.html
相关资源：JAVA上百实例源码以及开源项目