题解 LA3357

题目大意 多组数据，每组数据给定一个正整数 \(n\)，要求输出第 \(n\) 大的满足没有前导零或两个相邻的 \(1\) 的二进制串。

分析 我们令 \(a_n\) 为 \(n\) 位的这种串的个数，\(S_n\) 为 \(a\) 的前缀和，有

\[a_n = S_{n-2}+1\]

这是因为等于从这个串的 \(1,2,\cdots,n-2\) 位上再重新构造一个串，但是没有前导零的限制。

有意思的是 \(a_n\) 正好为斐波那契数列。

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int T, n;
ll s[50], a[50];

int main()
{
    a[1] = 1, a[2] = 1, s[1] = 1, s[2] = 2;
    for(int i = 3; i <= 44; ++i)
        a[i] = s[i - 2] + 1, s[i] = s[i - 1] + a[i];
        
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        
        int t = 0, last = 0;
        while(n) {
            last = t, t = 0;
            while(n > s[t + 1]) ++t;
            
            n -= s[t] + 1;
            
            for(int i = t + 1; i <= last - 1; ++i)
                putchar('0');
            putchar('1');
        }
        for(int i = 1; i <= t; ++i)
            putchar('0');
        putchar('\n');
    }
}

题解 LA3357

原文：https://www.cnblogs.com/whx1003/p/12319012.html