C++ 代码

#include<iostream>
#include<algorithm>
using namespace std;

using ll=long long ;
ll p[65];

//p[i]代表第Si有多少个字符
void init()
{
    ll v=2;
    int i;
    for(i=1;i<=64;++i)
    {
        p[i]=v-1;
        v*=2;
    }
}

//递推
//当前剩余的字符数,所在的层数
int dfs(ll v,int dep)
{
    ll ln=p[dep]/2;
    //每层中间的值为0
    if(v==ln+1)return 0;
    //在dep层的左半边
    if(v<=ln)return dfs(v,dep-1);
    //在dep层的右半边,因此要取反
    return 1-dfs(ln*2+2-v,dep-1);
}

//判断那一层的字符总数大于等于v
int solve(ll v)
{
    int dep=1;
    for(;;dep++)
    {
        if(p[dep]>=v)break;
    }
    return dfs(v,dep);
}

int main()
{
    init();

    int T;
    cin>>T;

    int Case=1;
    ll v;
    for(;Case<=T;Case++)
    {
        cout<<"Case #"<<Case<<": ";
        cin>>v;
        cout<<solve(v)<<endl;
    }

    return 0;
}