题目链接：uva 1350 - Pinary

题目大意:给出n，输出第n给Pinary Number，Pinary Number为二进制数，并且没有连续两个1相连。

解题思路：dp[i]表示到第i位有dp[i]种，于是给定n，一层循环判断dp[i]≤n的话，就输出1，并且n减掉dp[i],注意输出0的时候，不能输出前导0.

#include 
   
     #include 
    
      typedef long long ll; const int N = 50; ll dp[N]; void init () { memset(dp, 0, sizeof(dp)); dp[0] = dp[1] = 1; for (int i = 2; i <= 40; i++) dp[i] = dp[i-1] + dp[i-2]; } void solve (ll n) { bool flag = false; for (int i = 40; i; i--) { if (n >





= dp[i]) { printf("1"); n -= dp[i]; flag = true; } else if (flag) printf("0"); } printf("\n"); } int main () { init (); int cas; ll n; scanf("%d", &cas); for (int i = 0; i < cas; i++) { scanf("%lld", &n); solve(n); } return 0; }