UOJ152 【UR #10】汉诺塔 题解

题目链接：#152. 【UR #10】汉诺塔

题意：

cxy 是魔仙女王。

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

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

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

输入格式：

第一行一个正整数 \(n\)。

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

输出格式：

第一行输出一个整数 \(K\)（\(0 \leq K \leq 10^6\)）。

接下来 \(K\) 行每行两个整数 \(a_i,b_i\)，按照顺序依次描述你的每一次操作。

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

数据范围：

\(n \le 10^4\)

模拟一下可以发现这东西不是个dp，也不是传统的 \(\tt{Hanoi}\) 塔。

仔细观察可以发现这个其实是在给序列排序，并且给定了两个缓冲区。

于是我们想到最简单的选择排序。但是这样的交换数量为 \(O(n^2)\) 的

熟悉排序算法的同学一定发现了，这个缓冲区和基数排序那个很像

只不过这个只有 \(2\) 个缓冲区，因此这是一个 \(2\) 进制下的基数排序。

具体地，第一轮我们把偶数放到第二根柱子，奇数放到第三根柱子

第 \(k\) 轮我们把第 \(k\) 位为 \(0\) 的放到第二根柱子，第 \(k\) 位为 \(1\) 的放到第三根柱子。

总操作次数为 \(2n \log_2 a_{\max} < 2.7\times 10^5\)

时间复杂度 \(O(n \log a_{\max})\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)())
#define lg2(x) (63 - __builtin_clzll(x))
int n,ln;
vector<int> a[5];
void move(int x,int y)
{cout << x << ' ' << y << '\n', a[y].push_back(a[x].back()); a[x].pop_back();}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n; ln = lg2(n); cout << 2*n*(ln+1) << '\n';
    for(int i=1,x; i<=n; i++) { cin >> x; a[1].push_back(x); }
    reverse(a[1].begin(),a[1].end());
    for(int i=0; i<=ln; i++)
    {
        while(!a[1].empty()) move(1,2 + ((a[1].back() >> i) & 1));
        while(!a[3].empty()) move(3,1);
        while(!a[2].empty()) move(2,1);
    }
    return 0;
}