URAL

题目链接：H - Binary Lexicographic Sequence

题意：

Consider all the sequences with length (0 <  N < 44), containing only the elements 0 and 1, and no two ones are adjacent (110 is not a valid sequence of length 3, 0101 is a valid sequence of length 4). Write a program which finds the sequence, which is on K-th place (0 <  K < 10 ⁹) in the lexicographically sorted in ascending order collection of the described sequences.

Input

The first line of input contains two positive integers N and K.

Output

Write the found sequence or −1 if the number K is larger then the number of valid sequences.

input	output
3 1	000

题意就是求长度为3的第k大的01串，串的要求1不可以相邻

题解：我们二分答案，把答案转化为二进制，怎么判断呢，用数位dp求出比当前串要小的合法个数，我们先用

dp[pos][0]表示长度为pos第1个为0的串的个数dp[pos][1]开头为1的个数
转移方程看代码。

#include<bits/stdc++.h>
#include<set>
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#define pb push_back
#define ll long long
#define PI 3.14159265
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#define eps 1e-7
typedef unsigned long long ull;
const int mod=1e9+9;
const int inf=0x3f3f3f3f;
const int maxn=1e5+5;
const int root=1e6+7;
using namespace std;
ll t,n,m,k,len;
int a[50];
ll dp[50][2];//dp[pos][0]表示长度为pos第1个为0的串的个数dp[pos][1]开头为1的个数
void init()
{
    dp[1][0]=1;dp[1][1]=1;
    dp[2][0]=2;dp[2][1]=1;
    for(int i=3;i<=44;i++)
    {
        dp[i][0]=dp[i-1][0]+dp[i-1][1];
        dp[i][1]=dp[i-1][0];
    }
}
int slove(ll x)
{
    int t=1;
    while(x)
    {
        if(x%2)a[t]=1;
        else a[t]=0;
        x/=2;
        t++;
    }
    return t;
}
ll dfs(ll pos,bool lim,bool pre)//求小于等于x的合法串个数
{
    if(pos==0)
    {
        return 1;
    }
    ll ans=0;
    if(!lim)
    {
        if(!pre)
        {
            return dp[pos][0]+dp[pos][1];
        }
        else
        {
            return dp[pos][0];
        }
    }
    else
    {
        if(a[pos]==0)
        {
            return dfs(pos-1,true,false);
        }
        else
        {
            if(!pre)ans+=dfs(pos-1,true,true);
            ans+=dfs(pos-1,false,false);
            return ans;
        }
    }

}
bool judge(ll x)
{
    memset(a,0,sizeof(a));
    len=slove(x);
    ll sum=dfs(n,1,0);
    return sum>=k;
}
int main()
{
    init();
    while(~scanf("%lld %lld",&n,&k))
    {
        ll l=0;
        ll r=(1ll<<n)-1;//这里要用ll不然位运算会溢出
        while(l<=r)
        {
            ll mid=(l+r)>>1;
            if(judge(mid))r=mid-1;
            else l=mid+1;
        }
        memset(a,0,sizeof(a));
        if(k>dp[n][0]+dp[n][1]){
            puts("-1");
            continue;
        }
        len=slove(l);
        for(int i=n;i>=1;i--)
        {
            printf("%d",a[i]);
        }
        printf("
");
    }
    return 0;
}