酷暑一夏1

不忘初心，方得始终

• 于  Vijos, 新年趣事系列  阅读 

Vijos1068 新年趣事之玩具 题解

题目

今年春节，xiaomengxian回到了邵阳过年。刚准备进门时，突然发现院子里有个小孩在摆弄什么东西。走进一看，原来他在玩一种智力玩具，叫做“汉诺塔”。“汉诺塔”是这样一种玩具：有三个柱子，分别编号：#1，#2，#3。初始时，有N个直径不同的盘子放在第一根柱子上，且越底下的盘子直径越大。游戏的目的是把所有的盘子转移到第二根柱子上。约束条件是：任何时候都只能把小盘子放在大盘子上。
由于盘子数目比较多，小孩玩了很久都没有完成任务。于是，xiaomengxian走上前去，打开随身携带的笔记本电脑，运行了一个很久以前编写的程序。它的主要过程大致是这样的：
(省略)
有了xiaomengxian的帮助，小孩很快就完成了任务。他在感谢xiaomengxian的同时，又问了一个问题，想考考xiaomengxian。这个问题就是，给出一个中间状态，能否很快的说出这是第几次移动后的状态？
为了描述方便，对于每一个中间状态，我们定义序列D。其中，Di表示第i小的盘子所在的柱子编号。显然，Di=1，2，3。
下面是N=3的例子：
(省略)

题解

理解题目里面的代码，然后帮它剪枝就好了。

代码

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<cstdio>
#include<cstdlib>
const int MAXN=50+5;
int pan[MAXN],n;long long ans,twos[MAXN];
void init()
{
	twos[0]=1;
	for(int i=1;i<=50;i++)
		twos[i]=twos[i-1]*2;
	return;
}
void Hanoi(int n,int from,int to,int temp)
{
	if(n>0)
	{
		if(pan[n]==from)
		{
			Hanoi(n-1,from,temp,to);
		}
		else if(pan[n]==to)
		{
			ans+=twos[n-1];
			Hanoi(n-1,temp,to,from);
		}
		else if(pan[n]==temp)
		{
			printf("-1");
			exit(0);
		}
	}
}
int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&pan[i]);
	Hanoi(n,1,2,3);
	printf("%lld",ans);
	return 0;
}
最近的文章

Vijos1238 容易的网络游戏 题解

题目现在网络游戏一款接一款地推出，佳佳和他的同学们也迷上了网络游戏。他们最近在玩N款不同的网络游戏。一些网络游戏允许玩家购买双倍经验卡。拥有双倍经验卡的玩家可以在有效期内获得更多的经验值。佳佳和他的同学们有着丰富的网游经验，对于任何一款网络游戏，只要是在双倍经验的条件下，无论谁玩都可以在单位时间内轻 …

• 于  Vijos, 网络游戏系列 继续阅读
更早的文章

Vijos1070 新年趣事之游戏 题解

题目xiaomengxian的哥哥是一个游戏迷，他喜欢研究各种游戏。这天，xiaomengxian到他家玩，他便拿出了自己最近正在研究的一个游戏给xiaomengxian看。这个游戏是这样的：一个国家有N个城市，有些城市之间可以建设铁路，并且不同城市之间建设铁路的费用各不相同。问如何用最小的费用，使 …

• 于  Vijos, 新年趣事系列 继续阅读