题目
题解
当出现形如“给定 (n) 个整数，求这 (n) 个整数能拼凑出多少的其他整数（(n) 个整数可以重复取）”，以及“给定 (n) 个整数，求这 (n) 个整数不能拼凑出的最小（最大）的整数”的问题时可以使用同余最短路的方法。
引自 OI-wiki。
不妨设 (x < y < z)。（为了减少状态）
设 (dist[i]) 为最小的 (p=ay+bz) 且 (p equiv i pmod {x})
则可以对于每个 (i)，连一条 (i->(i+y)\%x) 的边，边权为 (y)，连一条 (i->(i+z)\%x) 的的边，边权为 (z)。在以 (1) 为起点这个图上跑最短路，就可以求出 (dist[i]) 了。
注意 (x,y,z le 10^5)，所以 (x) 和 (y) 的最小公倍数最大是 (xy le 10^{10}) 不会爆 long long ，也就是说 (dist[i]) （如果不为 (INF) 的话）不会超过 (10^{10})。
求出 (dist[i]) 后，可以发现 (dist[i]+kx,k in Z) 都可以到达（这就是设计同余状态的意义），于是就可以算出可以到多少个楼层了。
时间复杂度 (O(n log n))。
代码
#include<bits/stdc++.h>
#define int long long
#define mp make_pair
#define fi first
#define se second
using namespace std;
inline int read() {
int x = 0, f = 1; char ch = getchar();
while(ch<'0' || ch>'9') { if(ch=='-') f=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') { x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); }
return x * f;
}
typedef pair<int,int> PII;
const int N = 1e5+7;
int h,x,y,z,cnt;
int head[N],dist[N];
struct Edge {
int next,to,w;
}edge[N<<1];
inline void add(int u,int v,int w) {
edge[++cnt] = (Edge)<%head[u],v,w%>;
head[u] = cnt;
}
bool vis[N];
void Dijkstra() {
memset(dist, -1, sizeof(dist));
priority_queue<PII> q;
dist[1] = 1;
q.push(mp(-dist[1],1));
while(!q.empty()) {
int u = q.top().se;
q.pop();
if(vis[u]) continue;
vis[u] = 1;
for(int i=head[u];i;i=edge[i].next) {
int v = edge[i].to, w = edge[i].w;
if(dist[v]==-1 || dist[v]>dist[u]+w) {
dist[v] = dist[u] + w;
q.push(mp(-dist[v],v));
}
}
}
}
signed main()
{
h = read(), x = read(), y = read(), z = read();
if(x > y) swap(x,y);
if(x > z) swap(x,z);
for(int i=0;i<x;++i) {
add(i,(i+y)%x,y);
add(i,(i+z)%x,z);
}
Dijkstra();
int ans = 0;
for(int i=0;i<x;++i) {
if(dist[i] > -1) {
if(h >= dist[i]) {
ans += (h-dist[i])/x + 1;
}
}
}
printf("%lld
",ans);
return 0;
}
/*
15
4 7 9
9
*/
总结
利用同余设计状态。
同余最短路。