【2016-2017 ACM-ICPC (ECNA 2016) G】That's one Hanoi-ed Teacher【汉诺塔问题】

50 阅读 0 评论 33 点赞

我是靠谱客的博主热情红酒，最近开发中收集的这篇文章主要介绍【2016-2017 ACM-ICPC (ECNA 2016) G】That's one Hanoi-ed Teacher【汉诺塔问题】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

3根柱子的汉诺塔模型。给定每根柱上当前时刻有几个圆盘，判断这个时刻是否会出现在汉诺塔模拟过程中，如果不会，输出"NO"。否则输出当前状态离终态还有多少步。

思路:

我们先回顾一下普通汉诺塔的模拟过程。

void dfs(int n,int a,int b,int c)	//第n个圆盘从a->c
{
	if(n == 1){
		printf("%d, %d->%dn",n,a,c);
		return;
	}
	dfs(n-1,a,c,b);
	printf("%d, %d->%dn",n,a,c);
	dfs(n-1,b,a,c);
}

我们可以发现模拟过程中的几步。首先是n-1从a->b，然后n从a->c，然后n-1从b->c。因此我们可以根据第n个圆盘所在的位置，判断当前状态处于哪一个步骤。然后再判断n-1个圆盘所处的位置，不断递归下去。这里需要知道，n个圆盘的汉诺塔，一共需要移动2^n-1步，F[n] = 2*F[n-1]+1，因此我们可以根据每个盘的状态，对当前步数区间进行缩小，最终可以求出结果答案。详情看代码。

代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define LOG1(x1,x2) cout << x1 << ": " << x2 << endl;
#define LOG2(x1,x2,y1,y2) cout << x1 << ": " << x2 << " , " << y1 << ": " << y2 << endl;
typedef long long ll;
typedef double db;
const db EPS = 1e-9;
using namespace std;
const int N = 70;

int num[N],n,flag;
ll ans;

// void dfs(int n,int a,int b,int c)	//a->c
// {
// 	if(n == 1){
// 		printf("%d, %d->%dn",n,a,c);
// 		return;
// 	}
// 	dfs(n-1,a,c,b);
// 	printf("%d, %d->%dn",n,a,c);
// 	dfs(n-1,b,a,c);
// }

ll dfs(int n,ll l,ll r,int a,int b,int c)
{
	if(num[n] == a){
		r = (r-l-1)/2+l;
		if(n == 1) return l;
		if(num[n-1] == b) return dfs(n-1,l,r,a,c,b);
		else if(num[n-1] == a) return dfs(n-1,l,r,a,c,b);
		else{
			flag = -1;
			return 0;
		}
	}	
	else if(num[n] == c){
		l = (r-l-1)/2+l+1;
		if(n == 1) return l;
		if(num[n-1] == b) return dfs(n-1,l,r,b,a,c);
		else if(num[n-1] == c) return dfs(n-1,l,r,b,a,c);
		else{
			flag = -1;
			return 0;
		}
	}
	else{
		flag = -1;
		return 0;
	}
}

int main()
{
	flag = 0;
	ll base = 1;
	rep(i,0,2){
		int xx; scanf("%d",&xx); n += xx;
		rep(j,1,xx){
			int yy; scanf("%d",&yy);
			num[yy] = i;
		}
	}
	// rep(i,1,n) printf("num[%d]:%dn",i,num[i]);
	rep(i,1,n) base *= 2;
	base--;
	int jud = 0;
	ans = dfs(n,0,base,0,1,2);
	if(jud) printf("Non");
	else{
		if(flag == -1) printf("Non");
		else{
			printf("%lldn",base-ans);
		}
	}
	return 0;
}

/*
5 5 4 3 2 1
0
0
*/