shuoj 1 + 2 = 3? （二分+数位dp）

题目传送门

1 + 2 = 3?

发布时间: 2018年4月15日 22:46   最后更新: 2018年4月15日 23:25   时间限制: 1000ms   内存限制: 128M

描述

埃森哲是《财富》全球500 强企业之一，目前拥有约41.1 万名员工，服务于120 多个国家的4000 家企业。我们的客户既包括《财富》世界100 强中的94 家公司、《财富》世界500 强中3/4 以上的公司，也有世界上最大的国家政府机构。小Y 看到这样的介绍之后非常想加入公司，于是投递了简历，简历中写到自己参加过ACM 比赛，其中印象最深刻的一道问题是他在为比赛研究数字的时候，发现了一个神奇的等式方程x⊕2x=3x，他屈指算了一下有很多正整数x 满足这个等式，比如1和2，现在问题来了，

他想知道从小到大第N个满足这个等式的正整数，请你用程序帮他计算一下。

(⊕表示按位异或运算)

输入

第一行是一个正整数T(T≤100)，表示查询次数。

接着有T行，每行有一个正整数N(N≤1012)，表示小Y的查询。

输出

对于每一个查询N，输出第N个满足题中等式的正整数，并换行。

样例输入1

4

1

2

3

10

样例输出1

1

2

4

18
题意：求出第n个符合n^(2*n)==3*n
题解：首先，一个数的两倍就是二进制数向左移动一位，
      它与它的两倍要异或成三倍的数，那只有n这个数，
         它满足没有连续的1
          然后用二分+数位dp就行
代码：

#include<iostream>

#include<string.h>

#include<algorithm>

#include<stdio.h>

#include<queue>

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef long long ll;

typedef pair<int,int> PII;

#define mod 1000000007

#define INF 0x3f3f3f3f

#define NINF 0xc0c0c0c0

#define pb push_back

#define mp make_pair

#define all(x) (x).begin(),(x).end()

#define fi first

#define se second

//head

ll n;

int T;

ll bit[];

ll dp[][];

ll dfs(int pos,int sta,bool lead,bool limit)

{

    if(pos==-) return !lead;//除去0的影响

    if(!limit&&!lead&&dp[pos][sta]!=-)return dp[pos][sta];

    ll ans=;

    int up=limit?bit[pos]:;

    for(int i=;i<=up;i++)

    {

        if(i&&sta) continue;

        ans+=dfs(pos-,i,lead&&i==,limit&&(i==up));

    }

    if(!limit&&!lead) dp[pos][sta]=ans;

    return ans;

}

ll calc(ll x)

{

    int len=;

    while(x)

    {

        bit[len++]=x&;

        x>>=;

    }

    return dfs(len-,,true,true);

}

int main()

{

    memset(dp,-,sizeof(dp));

    scanf("%d",&T);

    while(T--)

    {

        scanf("%lld",&n);

        ll lb=,ub=1e18;

        ll ans=;

        while(ub-lb>){

            ll mid=(ub+lb)>>;

            if(calc(mid)<n) lb=mid;

            else ans=mid,ub=mid;

        }

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

    }

    return ;

}