admin 管理员组

文章数量: 887007

uoj #152. 【UR #10】汉诺塔

#152. 【UR #10】汉诺塔

 统计
  •  描述
  •  提交
  •  自定义测试

picks 博士乘上时光机器，打算回到 2012 年化身马猴烧酒阻止金星凌日，挽救世风日下的 OI 界于水火之中。

但是不幸的是，时光机器出现了一些特殊的故障，picks 博士被传送到了一个未知的时空。为了修理时光机器，他必须要得到一种叫做巴拉拉能量的能源。经过调查，他发现在这个时空中存在着一个被当地人称为魔仙堡的领域，从生活在那儿的小魔仙那里就可以得到足够的巴拉拉能量。

然而在那个时空中，存在着一股强大的势力与善良的小魔仙们敌对——那就是邪恶的黑魔仙们。巴拉拉能量是不能被黑魔仙得到的，否则就会产生严重的后果。为了检验 picks 博士是否是黑魔仙派来窃取巴拉拉能量的奸细，睿智的魔仙女王给 picks 博士出了一道题：

我现在使用巴拉拉能量造了三根柱子（编号分别为  1 1 到  3 3）以及  n n 块颜色不同的圆盘（编号为  1 1 到  n n）。最开始我给定一个  1 1 到  n n 的排列  A A，我会用巴拉拉能量把这些圆盘放到编号为  1 1 的柱子上，使得从上到下第  i i 块圆盘的编号是  Ai Ai。

接着你可以进行若干次操作，每一次操作用两个整数  a,b a,b （ 1≤a,b≤3,a≠b 1≤a,b≤3,a≠b） 来描述，表示这次操作你将会把地  a a 根柱子最上面的圆盘取出，并放到第  b b 根柱子上去（如果当前第  a a 根柱子上不存在圆盘，这次操作将会被小魔仙们忽略）。最终你要使得这  n n 块圆盘在同一根柱子上，且从上到下编号依次递增（最终状态下所有圆盘可以在任意一根柱子上）。

小魔仙们虽然善良，但是他们的耐心并不是无限的，所以你必须在  106 106 次操作内完成任务。

输入格式

第一行一个正整数  n n。

第二行是一个  1 1 到  n n 的排列  A A，相邻数字之间恰有一个空格隔开。

输出格式

第一行输出一个整数  K K（ 0≤K≤106 0≤K≤106）。

接下来  K K 行每行两个整数  ai,bi ai,bi，按照顺序依次描述你的每一次操作。

如果有多种方案，输出任意一种即可。

样例一

input
3
2 1 3
output
4
1 3
1 2
3 1
2 1
explanation

最开始三根柱子上的圆盘状态分别为 (2,1,3),(),() (2,1,3),(),()。

第一次操作后圆盘状态为 (1,3),(),(2) (1,3),(),(2)

第二次操作后圆盘状态为 (3),(1),(2) (3),(1),(2)

第三次操作后圆盘状态为 (2,3),(1),() (2,3),(1),()

第四次操作后圆盘状态为 (1,2,3),(),() (1,2,3),(),()

在所有操作结束后，圆盘都在第一根柱子上且从上到下编号依次递增。

样例二

见样例数据下载。

限制与约定

测试点编号 n n 的规模
1 n≤10 n≤10
2
3
4 n≤500 n≤500
5
6
7 n≤10000 n≤10000
8
9
10

时间限制： 1s 1s

空间限制： 256MB 256MB

下载

样例数据下载


题解：模拟+归并排序

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1000003
using namespace std;
int r1[N],ans[N];
int x[N],y[N],cnt;
int a[N],n;
void calc(int &a,int &b,int x)
{if (x==1)  a=3,b=2;if (x==2)  a=1,b=3;if (x==3)  a=1,b=2;
}
void merge(int pos,int l,int r)
{int mid=(l+r)/2;if (l==r) return;int t1,t2;calc(t1,t2,pos);for (int i=l;i<=mid;i++) x[++cnt]=pos,y[cnt]=t1;for (int i=l;i<=mid;i++) x[++cnt]=t1,y[cnt]=t2;merge(t2,l,mid); merge(pos,mid+1,r);int i=l; int j=mid+1; int k1=l;while (i<=mid&&j<=r){if (a[i]<=a[j]){r1[k1]=a[i]; i++; k1++;  x[++cnt]=t2,y[cnt]=t1;}else r1[k1]=a[j],j++,k1++,x[++cnt]=pos,y[cnt]=t1;}while (i<=mid){r1[k1]=a[i]; i++; k1++;x[++cnt]=t2; y[cnt]=t1;}while (j<=r){r1[k1]=a[j]; j++; k1++;x[++cnt]=pos; y[cnt]=t1;}for (int i=l;i<=r;i++)a[i]=r1[i],x[++cnt]=t1,y[cnt]=pos;
}
int main()
{scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);merge(1,1,n);printf("%d\n",cnt);for (int i=1;i<=cnt;i++)printf("%d %d\n",x[i],y[i]);return 0;
}




本文标签： uoj 152 UR 10汉诺塔

版权声明：本文标题：uoj #152. 【UR #10】汉诺塔 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732357233h1534781.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。