URAL 1081 Binary Lexicographic Sequence （递推 + 递归）

时间：2023-02-03 10:03:03

大体题意：

定义一个合法的二进制序列为序列中没有两个1是相邻的，对于所有长度为n的合法序列按照字典序排序后（保留前导0），求第K大的串是多少？

思路：

我们先得求出一个n位的合法二进制的个数是多少！

f[1] = 2;

f[2] = 3

f[3] = 5

f[4] = 8

这几个很容易算出来，然后我们就很明显的发现规律了，这是一个斐波那契数列！

其实想一想确实这个样！

你构造第n位时（高位），要么填0，要么填1，填0的话，直接是f(n-1),填1的话，要填10，结果是f(n-2)

因此  f(n) = f(n-1) + f(n-2);

然后在考虑第K大！

f(n-2)的数  第一个数是1，f(n-1) 第一个数是0，显然f(n-1)字典序要小！

因此如果k <= f(n-1)  ，那么这一位必然填0，继续递归！

相反如果k > f(n-1) 这一位必然是10，继续递归！

注意 k 不合法时，要输出-1，没看到wa了一次！

详细见代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int n, k;
ll f[50];
void init(){
    f[0] = 1;
    f[1] = 2;
    for (int i = 2; i <= 45; ++i){
        f[i] = f[i-1] + f[i-2];
    }
}
string ans;
void dfs(int c,int o){
    if (c == 0){
        return;

    }
    if (c == 1){
        if (o == 1) {
            ans += "0";
            return;
        }
        ans += "1";
        return;
    }
    if (f[c-1] >= o){
        ans += "0";
        dfs(c-1,o);
    }
    else {
        ans += "10";
        dfs(c-2,o-f[c-1]);
    }
}
int main(){
    init();
    while(scanf("%d %d",&n, &k)!=EOF){
        ans = "";
        if (k > f[n]){
            puts("-1");
            continue;
        }
        dfs(n,k);
        printf("%s\n",ans.c_str());
    }
    return 0;
}

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 < 10 9) 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 output 
3 1

000
Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament
Difficulty: 255     Printable version     Submit solution     Discussion (24)
All submissions (11523)     All accepted submissions (4997)     Solutions rating (4273)


标签：

相关文章