URAL/1081

---

Solution From Xcheng:

递推。

首先，计算满足条件的N位序列的总个数。设为f[n]

f[n]=f[n-1]+f[n-2]

可是这样理解：长度为N的序列对应于：

1.长度为N-1的序列左边加上0

2.长度为N-2的序列左边加上10

之后就类似求排列序号的方法。

要明白以下这个事实：

N位序列 0，a2,...an 必然在 N位序列 1，a2,..an 之前。

而 0，a2,..an 序列数对应于f[n-1]

若K大于等于f[n-1]则说明第一位为1，问题转化为求N-1位序列的第 K-f[n-1] 个是什么

若K小于f[n-1]则说明第一位为0，问题转化为求N-1位序列的第K个是什么

---

我的方法和上述的差不多，贴个代码

#include <cstdio>
 
const int oo=50;
 
int a[oo],n,k,f[oo][2];
bool tt;
 
void dfs(int L,int s){
	if (L==0 || s==0)	return;
	if (s<=f[L][0])	dfs(L-1,s);
	else	a[L]=1,dfs(L-1,s-f[L][0]);
}
 
int main(){
	freopen("s.in","r",stdin);
	freopen("s.out","w",stdout);
 
	scanf("%d%d",&n,&k);
	f[0][0]=1;
	for (int i=1;i<=n;i++){
		f[i][0]=f[i-1][0]+f[i-1][1];
		f[i][1]=f[i-1][0];
		if (k<=f[i][0]+f[i][1]){
			tt=true;
			dfs(i,k);
			break;
		}
	}
 
	if (!tt)	printf("-1");
	else
	for (int i=n;i;i--)
		printf("%d",a[i]);
 
	printf("\n");
 
	return 0;
}

---

贴个pascal版的 判断方法同上 从高位开始试 试能否为1 然后成功输出。

program cyd;
  var
    d:array[0..45]of integer;
    f:array[-5..45]of int64;
    i,j,k,l,m,n,a,b,c:longint;
  procedure print;
    var
      i:integer;
    begin
      for i:=n downto 1 do
        write(d[i]);
      halt;
    end;
  begin
    f[0]:=1;
    f[1]:=2;
    readln(n,k);
    for i:=2 to n do
      f[i]:=f[i-1]+f[i-2];
    if f[n]<k then begin writeln(-1); halt; end;
    for i:=0 to n do
      if f[i]>=k then break;
    dec(k,f[i-1]+1);
    d[i]:=1;
    if k=0 then print;
    for j:=i-2 downto 0 do
      if (d[j+1]=0)and(k-f[j-1]>=0) then
        begin
          d[j]:=1;
          dec(k,f[j-1]);
          if k=0 then print;
        end;
  end.

---

方法和上面类似

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<algorithm>
 
using namespace std;
int f[55][2];
int ans[55], cnt=0;
int main()
{
	int n, K;
	scanf("%d%d", &n, &K);
	memset(f, 0, sizeof(f));
	f[1][1]=f[1][0]=1;
	for (int i=2; i<=n; i++)
	{
		f[i][1]=f[i-1][0];
		f[i][0]=f[i-1][0]+f[i-1][1];
	}
	if (K>f[n][1]+f[n][0]) {printf("%d", -1); return 0;}
	int i=n;
	while (i)
	{
		if (K>f[i][0]) 
		{
			ans[++cnt]=1;
			K-=f[i][0];
		}else ans[++cnt]=0;
		i--;
	}
	for (int i=1; i<=n; i++)
		printf("%d", ans[i]);
	return 0;
}