URAL 1081 - c++编程基础

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

例如：

input: output:

3 1 000(所有符合条件的序列有：000，001，010，100，101)

Time Limit:500MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

数据规模：0

理论基础：无。

题目分析：先观察：1-5位的答案。

1:01

2:00 01 10

3:000 001 010100 101

4:00000001 00100100 01011000 10011010

5:0000000001 00010 00100 0010101000 0100101010 10000 10001 10010 1010010101

观察数目：1:2,2:3,3:5,4:8,5:13...这是巧合吗？不是。我们看新序列的生成方式。在n-1位的所有序列的最高位添加0，数目为ans[i-1]，在n-1位的所有最高位为0的序列前添加1,数目为ans[i-2]（为什么呢？想想最高位为0的序列都是怎么来的？？？）这样，我们就得出：ans[i]=ans[i-1]+ans[i-2]。可是要的不是数目啊，是第K个序列啊。。。好吧，状态压缩dp可以解决，但是有没有更简单的方法呢？

我们再来观察：当N=5，K<=ans[4]时，我们输出的最高位肯定是0，这时只需要输出ans[4]时的K不就行了？同样此时如果K<=ans[3]递推下去。那如果K>ans[3]呢？那我们肯定输出的最高位是1，这时只需要输出ans[3]时的K-ans[3]不就行了？问题得到解决。。。

代码如下：


 
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
using namespace std;  
typedef double db;  
#define DBG 0   
#define maa (1<<31)   
#define mii ((1<<31)-1)   
#define ast(b) if(DBG && !(b)) { printf("%d!!|\n", __LINE__); while(1) getchar(); }  //调试   
#define dout DBG && cout << __LINE__ << ">>| "   
#define pr(x) #x"=" << (x) << " | "   
#define mk(x) DBG && cout << __LINE__ << "**| "#x << endl   
#define pra(arr, a, b)  if(DBG) {\   
    dout<<#arr"[] |" < inline bool updateMin(T& a, T b) { return a>b  a=b, true: false; }  
template inline bool updateMax(T& a, T b) { return aFibonacci[n])  
        {  
            puts("-1");  
            continue;  
        }  
        while(n)  
        {  
            if(k<=Fibonacci[--n])printf("0");  
            else  
            {  
                printf("1");  
                k-=Fibonacci[n];  
            }  
        }  
        puts("");  
    }  
    return 0;  
}