n位不含前导零不含连续1的数共有fib(n)个,fib(n)为斐波那契数列。

所以可以预处理一下fib的前缀和,查找一下第n个数是k位数,然后再递归计算它是第k位数里的多少位。

举个例子,比如说要找第11个数,发现它是个5位数,所以最高位是个1,然后它还是5位数里的第4个数。

这时要找第三个数了,因为后面的数允许有前导零,第三个数是100,所以第5位是1,第4位是0,后面三位是100,

答案就是10100

说的有点啰嗦,在纸上模拟一下还是很容易理解的。

 #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; typedef long long LL; const int maxf = + ;
const int maxn = ; LL fib[maxn], sum[maxn];
int ans[], p = ; void f(int n)
{
if(n == ) return;
int digits = lower_bound(sum+, sum+p, n) - sum;
ans[digits-] = ;
n -= sum[digits-];
n--;
f(n);
} int main()
{
int T, n; scanf("%d", &T); fib[] = fib[] = ;
for(p = ; fib[p-] < maxf; p++) fib[p] = fib[p-] + fib[p-];
sum[] = fib[];
for(int i = ; i < p; i++) sum[i] = sum[i-] + fib[i]; while(T--)
{
scanf("%d", &n);
memset(ans, , sizeof(ans));
int d = lower_bound(sum+, sum+p, n) - sum;
f(n);
for(int i = d-; i >= ; i--) printf("%d", ans[i]);
printf("\n");
} return ;
}

代码君

04-26 16:18
查看更多