90分,求调
查看原帖
90分,求调
729457
ACehomoxue楼主2024/8/20 11:04
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define el cout<<'\n'
const int maxn=1e5+10,mod=998244353,inf=(1ull<<63)-1;
int h,x,y,z,dis[maxn],ans=0;
bool vis[maxn];
vector<pair<int,int> > vec[maxn];
void spfa() {
	queue<int> qu;
	qu.push(0);vis[0]=true;dis[0]=0;
	while(!qu.empty()) {
		int now=qu.front();qu.pop();
		for(auto tmp:vec[now]) {
			int to=tmp.first,tk=tmp.second;
			if(dis[to]>dis[now]+tk) {
				dis[to]=dis[now]+tk;
				if(vis[to]==false) {
					vis[to]=true;
					qu.push(to);
				}
			}
		}
	}
}
signed main () {
	cin>>h>>x>>y>>z;
	if(x==1||y==1||z==1) cout<<h<<'\n',exit(0);
	h--;
	for(int i=0;i<x;i++) {
	    vec[i].push_back({(i+y)%x,y});
	    vec[i].push_back({(i+z)%x,z});
	    dis[i]=inf;
	}
	spfa();
  	for(int i=0;i<x;i++) if(h>=dis[i]) ans+=(h-dis[i])/x+1;
  	cout<<ans;el;
	return 0;
}
2024/8/20 11:04
加载中...