题目
LA3357 Pinary
题解
不知道是这道数位DP简单了还是我做了有一些数位DP题然后提升了qwq。首先根据套路设出一个函数g(x)表示后x位随便取的时候答案的个数，然后想办法预处理g数组，但是因为题目要求没有连续的1，所以很自然的加一维,g(x,0)，表示后x位随便取，第一位取0的时候，的答案个数，1的状态类似。转移就很简单了。g数组搞定。
然后第一步是要确定位数，不难发现如果有lim（先考虑lim>=2）位的话，lim这位肯定是1，lim-1这一位肯定为0，所以长度为lim位的答案共有g[lim-1][0]个，就可以推出答案位数lim了。
知道位数之后，我们已经确定了两位了，继续往后走，因为这道题是01串所以实际上是非常方便的，如果i这一位为0的话答案共有g[i][0]个，当这时的k<=g[i][0]时这一位为0否则为1.（感觉有点像treap，而且kth变化的过程实际上也和treap求rank非常像），只需要特判一下最后一位，就行了。qwq是不是好简单。
代码
//QWsin
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1000+10;
typedef long long ll;ll g[maxn][2];
inline void init_g()
{g[0][0]=g[0][1]=g[1][1]=g[1][0]=1;for(int i=2;i<=1000;++i) {g[i][0]=g[i-1][1]+g[i-1][0];g[i][1]=g[i-1][0];}
}int kth;inline void solve()
{scanf("%d",&kth);int lim=1;while(kth > g[lim-1][0]) kth-=g[(lim++)-1][0];putchar('1');if(lim!=1){putchar('0');for(int i=lim-2;i>=1;--i){if(i==1)putchar(kth==1?'0':'1');else if(kth > g[i][0]) kth-=g[i][0],putchar('1');else putchar('0');}}putchar('\n');
}int main()
{init_g();int T;cin>>T;while(T--) solve();return 0;
}