蒟蒻的小窝

蒟蒻的小窝

题解 P6232 【[eJOI2019]挂架】

posted on 2020-11-28 09:58:36 | under 题解 |
/*
解法一: 
对于样例1可以画一棵树 
                          / \
                         /    \
                        /       \
                      0/          \1
                      /             \
                     /               \
                    /  \            /  \
                  0/    \1       0/     \1
                 /       \       /       \
               0/ \1   0/ \1   0/ \1   0/ \1
               /   \   /   \   /   \   /   \
              000 100 010 110 001 101 011 111
               0   4   2   6   1   5   3   7
               1   5   3   7   2   6   4   8
              000 001 010 011 100 101 110 111
               0   1   2   3   4   5   6   7
               1   2   3   4   5   6   7   8 
0为左子树,1为右子树 
我们从下往上记录 ,发现这不就是下面所对的数-1的二进制吗
再继续研究,发现从上往下记录的二进制数为这个位置的编号-1
题目问的就是编号,所以只需要将k-1,转成二进制,然后倒过来,不足n位的补零,转成十进制,然后+1 

解法二:
从样例1中总结出来的规律 
N=1:1|2 
N=2:1 3|2 4
N=3:1 5 3 7|2 6 4 8
N=4:1 9 5 13 3 11 7 15|2 10 6 14 4 12 8 16
N=5:1 17 9 25 5 21 13 29 3 19 11 27 7 23 15 31|2 18 10 26 6 22 14 30 4 20 12 28 8 24 16 32 
每个N所对的值被竖线隔成了两半
前一部分可以从N-1的整个部分的每个数*2-1得到 
后一部分可以从前一部分的数+1得到(也就是N-1整个部分的每个数*2) 
*/
#include <bits/stdc++.h>
using namespace std;
struct reader{
    template<typename Type>
    reader&operator>>(Type&ret){
        ret=0;int f=1;char ch=getchar();
        for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-f;
        for(; isdigit(ch);ch=getchar())ret=(ret<<1)+(ret<<3)+(ch-'0');
        ret*=f;return *this;
    }
}fin;

int a[105],b[105];
long long n,k,ans;

int main(){

    fin>>n>>k;k--;

    while(k){
        int y=k%2;
        a[++a[0]]=y;
        k/=2;
    }

    int cnt=0; 
    for(int i=n-a[0]+1;i<=n;i++)b[i]=a[++cnt];

    long long s=1;
    for(int i=1;i<=n;i++){
        ans+=b[i]==1?s:0;
        s*=2;
    }

    printf("%lld\n",ans+1);

    return 0;
}