【URAL-1081】解题报告（递推，斐波那契）

题目大意

1081. Binary Lexicographic Sequence

  • Time limit: 0.5 second
  • Memory limit: 64 MB

Consider all the sequences with length (0 < N < 44), containing only the elements 0 and 1, and no two ones are adjacent (110 is not a valid sequence of length 3, 0101 is a valid sequence of length 4). Write a program which finds the sequence, which is on K-th place (0 < K < 109) in the lexicographically sorted in ascending order collection of the described sequences. ### Input The first line of input contains two positive integers N and K.

Output

Write the found sequence or −1 if the number K is larger then the number of valid sequences.

Sample

input

3 1

output

000

Problem Author:

Emil Kelevedzhiev ### Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament

题目大意

求词典序下第K个长度为N且无相邻位置都为1的0、1序列。无解时输出-1。

解题思路

  • 先考虑长度为n的符合要求序列有多少个。
    • 1（2个）:0 1
    • 2（3个）:00 01 10
    • 3（5个）:000 001 010 100 101
    • 4（8个）:0000 0001 0010 0100 0101 1000 1001 1010
    • 5（13个）:00000 00001 00010 00100 00101 01000 01001 01010 10000 10001 10010 10100 10101
  • 发现规律，个数为斐波那契数列。构成原因：dp[k+1]的前dp[k]项为前面补0，后dp[k-1]项为前面补10

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>
#include <cstring>
#include <iostream>
#include <set>
#include <algorithm>
#include <queue>
#include <map>
#include <string>
#define eps 1e-8
#define INF 0x3f3f3f3f
#define rep(i,a,n) for(int i=a;i<n;i++)
#define per(i,a,n) for(int i=n-1;i>=a;i--)
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll n,k;
ll dp[maxn];
void solve(){
	dp[0]=1;
	dp[1]=2;
	dp[2]=3;
	rep(i,3,50){
		dp[i]=dp[i-1]+dp[i-2];
	}
}
int main(){
	solve();
	while(~scanf("%lld%lld",&n,&k)){
		if(k>dp[n]){
			printf("-1\n");
		}
		else {
			while(n)
			{
				n--;
				if(k<=dp[n])printf("0");
				else
				{
					printf("1");
					k-=dp[n];
				}
			}
			printf("\n");
		}
	}
}

收获与反思

  • 注意观察斐波那契数列