题面

Sol

有一个显然的想法

处理出\(y, z\)能凑出的高度

然后这些高度凑一些\(x\)就可以得到其它的高度

那么可以把这些\(y, z\)凑出的高度对\(x\)取模，其它的用\(x\)来填补

所以设\(f[i]\)表示\(y, z\)凑出高度\(\%x\)为\(i\)需要的最低高度

那么答案就是

\[\sum_{i=0}^{x-1}\lfloor\frac{(n-f[i])}{x}\rfloor+1
\]

# include <bits/stdc++.h>

# define RG register

# define IL inline

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

const int _(1e5 + 5);

typedef long long ll;

IL ll Input(){

    RG ll x = 0, z = 1; RG char c = getchar();

    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;

    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);

    return x * z;

}

int x, y, z, first[_], cnt, vis[_];

ll n, ans, f[_];

struct Edge{

	int to, next, w;

} edge[_ << 1];

queue <int> Q;

IL void Add(RG int u, RG int v, RG int w){

	edge[cnt] = (Edge){v, first[u], w}, first[u] = cnt++;

}

int main(RG int argc, RG char* argv[]){

	n = Input(), x = Input(), y = Input(), z = Input();

	if(y < x) swap(x, y);

	if(z < x) swap(x, z);

	for(RG int i = 0; i < x; ++i) first[i] = -1;

	for(RG int i = 0; i < x; ++i) Add(i, (i + y) % x, y), Add(i, (i + z) % x, z);

	Fill(f, 127), f[1 % x] = 1, vis[1 % x] = 1, Q.push(1 % x);

	while(!Q.empty()){

		RG int u = Q.front(); Q.pop();

		for(RG int e = first[u]; e != -1; e = edge[e].next){

			RG int v = edge[e].to, w = edge[e].w;

			if(f[u] + w < f[v]){

				f[v] = f[u] + w;

				if(!vis[v]) vis[v] = 1, Q.push(v);

			}

		}

		vis[u] = 0;

	}

	for(RG int i = 0; i < x; ++i) if(f[i] <= n) ans += (n - f[i]) / x + 1;

    return printf("%lld\n", ans), 0;

}

巴特西

Luogu3403: 跳楼机

题面

Sol

最新文章

热门文章