admin 管理员组

文章数量: 887007

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

题目：

orzKPM。。。

分治，把数字是l~mid的拿出来放在一根柱子上，mid+1~r放在另一根柱子上。如此递归下去，每次递归只是改一下方向，l，r。然后只要处理r-l<=1的情况就可以了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <queue>
#include <cmath>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define maxn 1000500
#define ll long long
#define inf int(1e9)
using namespace std;
int ansx[maxn],ansy[maxn],a[3][maxn],N[3];
int tot;
int read(){int x=0,f=1; char ch=getchar();while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar();}while (isdigit(ch)) {x=x*10+ch-'0'; ch=getchar();}return x*f;
}
void move(int x,int y){ansx[++tot]=x+1,ansy[tot]=y+1;a[y][++N[y]]=a[x][N[x]--];
}
void dfs(int x,int l,int r,int dir){if (l==r) return;if (r-l<=1){if ((dir==0&&a[x][N[x]-1]<a[x][N[x]])||(dir==1&&a[x][N[x]-1]>a[x][N[x]])){move(x,(x+1)%3);move(x,(x+2)%3);move((x+1)%3,x);move((x+2)%3,x);}return;}int mid=(l+r)/2; int y=(x+1)%3,z=(x+2)%3;rep(i,l,r) if (a[x][N[x]]<=mid) move(x,y); else move(x,z);dfs(y,l,mid,1-dir);dfs(z,mid+1,r,1-dir);if (dir==0){down(i,r,mid+1) move(z,x);down(i,mid,l) move(y,x);     }else {rep(i,l,mid) move(y,x);rep(i,mid+1,r) move(z,x);}
}
int main(){int n=read();down(i,n,1) a[0][i]=read();N[0]=n;dfs(0,1,n,0);printf("%d\n",tot);rep(i,1,tot) printf("%d %d\n",ansx[i],ansy[i]);return 0;
}

 

转载于:.html

本文标签： UOJ152 UR 10汉诺塔

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