URAL 1081 Binary Lexicographic Sequence (递推 + 递归)

2017-01-12 19:04:57来源:CSDN作者:aozil_yang人点击

大体题意:

定义一个合法的二进制序列为序列中没有两个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 < 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

inputoutput
3 1
000
Problem Author: Emil Kelevedzhiev
Problem Source: Winter Mathematical Festival Varna '2001 Informatics Tournament
Tags: dynamic programming  (
hide tags for unsolved problems
)Difficulty: 255    Printable version    Submit solution    Discussion (24)
All submissions (11523)    All accepted submissions (4997)    Solutions rating (4273)


最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台