HDU-2511-汉诺塔 X

发布时间：2020-12-14 04:26:06 所属栏目：大数据来源：网络整理

导读：首先我们来求第m次移动的盘子号数，先列出当m比较小可以直接观察的前几项 m : 1、2、3、4、5、6、7、8、9、10 id : 1、2、1、3、1、2、1、4、 1、2 很容易联想到树状数组的lowbit，这题的id就是lowbit(m)在二进制中的编号。 ? for (id = 1; (m 1) == 0; id+

首先我们来求第m次移动的盘子号数，先列出当m比较小可以直接观察的前几项

m : 1、2、3、4、5、6、7、8、9、10

id : 1、2、1、3、1、2、1、4、1、2

很容易联想到树状数组的lowbit，这题的id就是lowbit(m)在二进制中的编号。

for (id = 1; (m & 1) == 0; id++,m >>= 1);?就能求出id。

然后还要求从哪个盘移到哪个盘，经模拟前几项发现：

当n是奇数时：

如果id是奇数,那么盘子的移动顺序总是 1 -> 3,3 -> 2,2 -> 1,?1 -> 3,2 -> 1无限循环

如果id是偶数,那么盘子的移动顺序总是 1 -> 2,2 -> 3,3 -> 1,?1 -> 2,3 -> 1无限循环

当n是偶数时：

如果id是奇数,3 -> 1无限循环

如果id是偶数,2 -> 1无限循环

经过上面右移之后的m必然是一个奇数，m >> 1可以求出id号盘子之前被移动过几次；

Accepted

2511

0MS

1360K

589 B

G++

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int main() {
    int t,n;
    LL m;
    scanf("%d",&t);
    while (t--) {
        scanf("%d%lld",&n,&m);
        int id,from,to;
        for (id = 1; (m & 1) == 0; id++,m >>= 1);
        if ((id & 1) ^ (n & 1)) {
            from = (m >> 1) % 3 + 1; 
            to = from % 3 + 1;
        } else {
            // 这里这样写是为了保证from在1到3之间 
            from = (-2 - (m >> 1)) % 3 + 3;
            to = (from + 1) % 3 + 1; 
        }
        printf("%d %d %dn",id,to);
    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!