6782：Hanoi

题目描述

X 同学自从学会了汉诺塔游戏之后就非常沉迷。汉诺塔游戏由三根柱子（标号为0、1、2）和一堆体积不同的圆盘组成。每根柱子上有一些圆盘。如果每根柱子上的圆盘体积都满足从上到下依次增大，那么称之为合法状态，否则为非法状态。从一个状态出发，可以将一个柱子最顶端的圆盘移到另一根柱子上，若移动之后仍是合法状态，则称这一步移动为“合法的”。现在给定合法的起始状态和结束状态，我们需要通过一系列“合法的”步骤将起始状态变换至结束状态。由于移动每一步都需要体力，X 同学想寻找移动步数最少的方案（最优方案）。特别地，X 同学对于最优方案下移动了 $k$ 次盘子之后的局面感兴趣，但怎么也玩不好这个游戏，于是来咨询你。

输入解释

第一行一个整数 $T(1 \leq T \leq 20)$，表示测试用例组数。

每组测试用例的第一行有两个整数 $n(1\leq n\leq 10^5)$ 和 $k(0 \leq k \leq 10^{18})$，表示有 $n$ 个圆盘，圆盘的体积分别为 $1,2,\ldots,n$。$k$ 如上述。

接下来一行表示起始状态，含 $n$ 个整数，第 $i$ 个整数表示体积为 $i$ 的圆盘一开始所在的柱子。

接下来一行表示结束状态，含 $n$ 个整数，第 $i$ 个整数表示体积为 $i$ 的圆盘最终所在的柱子。

可以证明给定每个圆盘所在的柱子后，只存在唯一一种合法状态。数据保证最优方案唯一，$k$ 不大于最优方案移动总步数。

输出解释

输出 $T$ 行整数。

对每组测试用例，输出一行共 $n$ 个整数，第 $i$ 个整数表示体积为 $i$ 的圆盘在最优方案下移动了 $k$ 步之后所在的柱子编号。

输入样例

输出样例

2 0 1

来自杭电HDUOJ的附加信息

Recommend

heyang

该题目是Virtual Judge题目，来自杭电HDUOJ

题目来源 2020 年百度之星·程序设计大赛 - 初赛二

源链接： HDU-6782

最后修改于 2020-10-25T23:34:20+00:00 由爬虫自动更新

共提交 0 次

通过率 --%

时间上限	内存上限
6000/3000MS(Java/Others)	262144/262144K(Java/Others)