[Luogu]跳楼机P3403

Description

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

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

向上移动x层；
向上移动y层；
向上移动z层；
回到第一层。

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

Input Format

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

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

Output Format

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

Input Sample

1
2

15
4 7 9

Output Sample

Hint

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

$1 \le h \le 10^{18},1 \le x, y, z \le 10^5$

题解

很神奇的题目。。。一开始看到就想起了 $NOIp2017D1T1$ 小凯的疑惑。

莫非这题是那题的变态加强版？然后也有 $O(1)$ 的解法？？？

emmm看了一下好像并不行。。。~~然后发现我只会做两个操作的~~

首先我们来简化一下题意，题目要求 $h=ax+by+cz(h<=H)$ 这么一个 $h$ 的所有不同取值的个数。

既然题目有三种操作，我们就一个个考虑过去。

我们首先考虑两种操作（这里我们选择操作2、3~~我就喜欢这么选~~）

假设我们这时通过几次操作2和几次操作3到了楼层 $i$ ，再来看操作1对答案的贡献，这时候我们可以做任意次的操作1，此时操作1对答案的贡献就是 $(H-i)/X$

这样我们就可以统计答案了吗？

并不行。在我们统计答案的时候，会发现有重复。而且 $i \le 10^{18}$ 的范围我们也无法承担。

那么我们需要选择一种不存在重复的统计方式。

看下数据范围，发现 $1 \le x,y,z \le 10^5$ ，所以肯定是在这里搞事情。

然后我们考虑进行 $mod$ 操作。

记录 $f_i$ 表示仅通过操作2和操作3可以到达的在 $mod \space X=i$ 意义下的最小楼层。

那么我们可以得到 $f$ 数组的转移式

$f_{(i+y)mod \space x}=f(i)+y$
$f_{(i+z)mod \space x}=f(i)+z$

对转移式进行观察，我们发现这就是在求最短路时我们进行转移的式子！ $f$ 在这里就相当于求最短路时的 $dis$

那么我们就可以快速求出所有 $f_i$ 的值。

然后统计答案，就顺利解决了。

#include <queue>
#include <stdio.h>
#include <string.h>
#define Re register int
#define LL long long

struct Edge{
	int to,next,w;
}e[200005];
int cnt,head[100005];
std::queue<int> q;
LL dis[100005],H,ans;
int X,Y,Z,vis[100005];

inline void AddEdge(int u,int v,int w) {e[++cnt]=(Edge){v,head[u],w}; head[u]=cnt;}
inline void SPFA()
{
	memset(dis,0x3F,sizeof(dis));
	q.push(1%X); dis[1%X]=1; vis[1%X]=1; //这里mod X处理X=1的情况
	while (!q.empty())
	{
		int now=q.front(); q.pop(); vis[now]=0;
		for (Re i=head[now];i;i=e[i].next)
			if (dis[e[i].to]>dis[now]+e[i].w)
			{
				dis[e[i].to]=dis[now]+e[i].w;
				if (!vis[e[i].to]) vis[e[i].to]=1,q.push(e[i].to);
			}
	} return;
}
int main()
{
	scanf("%lld%d%d%d",&H,&X,&Y,&Z);
	for (Re i=0; i<X; ++i)
		AddEdge(i,(i+Y)%X,Y),AddEdge(i,(i+Z)%X,Z);
	SPFA();
	for (Re i=0; i<X; ++i)
		if (dis[i]<=H) ans+=(H-dis[i])/X+1;
	printf("%lld\n",ans);
	return 0;
}