[Luogu]跳楼机P3403

发表于 | 阅读次数：

Description

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

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

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

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

Input Format

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

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

Output Format

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

Input Sample

1
2
15
4 7 9

Output Sample

1
9

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$数组的转移式

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#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;
}