跳楼机

题目背景

DJL 为了避免成为一只咸鱼，来找 srwudi 学习压代码的技巧。

题目描述

Srwudi 的家是一幢 \(h\) 层的摩天大楼。由于前来学习的蒟蒻越来越多，srwudi 改造了一个跳楼机，使得访客可以更方便的上楼。

经过改造，srwudi 的跳楼机可以采用以下四种方式移动：

1. 向上移动 \(x\) 层；
2. 向上移动 \(y\) 层；
3. 向上移动 \(z\) 层；
4. 回到第一层。

一个月黑风高的大中午，DJL 来到了 srwudi 的家，现在他在 srwudi 家的第一层，碰巧跳楼机也在第一层。DJL 想知道，他可以乘坐跳楼机前往的楼层数。

输入格式

第一行一个整数 \(h\)，表示摩天大楼的层数。

第二行三个正整数，分别表示题目中的 \(x, y, z\)。

输出格式

一行一个整数，表示 DJL 可以到达的楼层数。

样例 #1

样例输入 #1

15
4 7 9

样例输出 #1

9

样例 #2

样例输入 #2

33333333333
99005 99002 100000

样例输出 #2

33302114671

提示

可以到达的楼层有：\(1,5,8,9,10,12,13,14,15\)。

\(1 \le h \le 2^{63}-1\)，\(1 \le x,y,z \le 10^5\)。

题解：

\(\%\%\%Mr\)_\(Leceue\)
先考虑如何统计答案,如果我们知道一个数 \(num\) 是由 \(y,z\) 构成的,即 \(num=a*y+b*z\),那么如果加上 \(x\) ,它能到达的楼层数为 \((h-num)/x+1\) 其中 \(+1\) 是因为要统计不加 \(x\) 时的答案;

那么如果我们能找到这些数,再去统计不就好了吗,但是会有重复,而且数字太过庞大,无法完全跑出,那么考虑什么时候回重复计数,即当 \(num1=num2+ax\) ,此时 \(num1\) 的贡献已经被 \(num2\) 统计过,再观察两个数字,发现 \(num1 \% x=num2 \% x\) ,那么我们只要找到余数相同中最小值即可,余数共有 xx 种;

设计转移方程: 设 \(f[i]f[i]\) 指余数为 ii 时最小楼层数,那么转移有两种方式;

\(f[(i+y)\%x]=min(f[i]+y,f[(i+y)\%x])\)

\(f[(i+z)\%x]=min(f[i]+z,f[(i+y)\%x])\)

​ 我们可以用最短路来优化类似于点 \(i\) 与点 \((i+y)\%x\) 连边,代价为 \(y\) ;

std：

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
const int N = 2e5+9;
ll H,ans;
int x,y,z;

int h[N],ver[N],w[N],ne[N],idx;

void add(int u,int v,int val)
{
	idx++,ver[idx]= v,ne[idx] = h[u],w[idx] = val,h[u] = idx;
}

queue<int>q;
bool inq[N];
ll dis[N];
void spfa()
{
	for(int i = 0;i < x;i++)dis[i] = LLONG_MAX+1;//2^64
	q.push(1),inq[1] = 1,dis[1] = 1;
	while(!q.empty())
	{
		int u = q.front();inq[u] = 0,q.pop();
		for(int i = h[u];~i;i = ne[i])
		{
			int v = ver[i];
			if(dis[v] > dis[u] + w[i])
			{
				dis[v] = dis[u] + w[i];
				if(!inq[v])q.push(v),inq[v] = 1;
			}
		}
	}
}

int main()
{
	scanf("%lld%d%d%d",&H,&x,&y,&z);
	if(x == 1 || y == 1 || z == 1)return printf("%lld",H),0;
	
	if(x > y)swap(x,y);
	if(x > z)swap(x,z);
	memset(h,-1,sizeof h);
	for(int i = 0;i < x;i++)
	{
		add(i,(i+y)%x,y);
		add(i,(i+z)%x,z);
	}
	
	spfa();
	
	for(int i = 0;i < x;i++)
		if(H >= dis[i])ans += (H-dis[i])/x+1;
	
	printf("%lld",ans);
	
	return 0;
}
//putin:
//9223372036854775807
//10 10 10
//putout:
//922337203685477581

原文地址：http://www.cnblogs.com/AC7-/p/16876136.html