這里送上一道微軟的筆試題，具體題目如下：

Time Limit: 10000ms

Case Time Limit: 1000ms

Memory Limit: 256MB

Description

Consider a string set that each of them consists of {0, 1} only. All strings in the set have the same number of 0s and 1s.

Write a program to find and output the K-th string according to the dictionary order. If s​uch a string doesn’t exist,

or the input is not valid, please output “Impossible”. For example, if we have two ‘0’s and two ‘1’s,

we will have a set with 6 different strings, {0011, 0101, 0110, 1001, 1010, 1100}, and the 4th string is 1001.

Input

The first line of the input file contains a single integer t (1 ≤ t ≤ 10000),

the number of test cases, followed by the input data for each test case.

Each test case is 3 integers separated by blank space: N, M(2 <= N + M <= 33 and N , M >= 0),

K(1 <= K <= 1000000000). N stands for the number of ‘0’s, M stands for the number of ‘1’s,

and K stands for the K-th of string in the set that needs to be printed as output.

Output

For each case, print exactly one line. If the string exists, please print it, otherwise print “Impossible”.

Sample In

3

2 2 2

2 2 7

4 7 47

Sample Out

0101

Impossible

01010111011

其實(shí)說了這么多，意思很簡(jiǎn)單，就是輸入N個(gè)0，M個(gè)1.然后求出由M，N個(gè)1,0組成的第K大的數(shù)。如果不存在則輸出impossible.

初來乍到的，大家可能會(huì)認(rèn)為這是一個(gè)全排列的問題，但是全排列在問題在于不能很好的知道每個(gè)數(shù)到底排在第幾位，并且時(shí)間上肯定是不能通過的，遞歸的效率大家應(yīng)該都知道。

我們可能會(huì)想到另外一種解決方案，直接列舉，從最小的000...1111開始，一直列舉到1111..000然后記錄下當(dāng)前是否是含N個(gè)0，M個(gè)1。這種方式是最容易理解的了，但是如果數(shù)字比較大，比如17個(gè)1,17個(gè)0,我們且不說這么大的整數(shù)不能保存，就這個(gè)時(shí)間上也不合算啊，雖然他是線性復(fù)雜度，但是這個(gè)線性數(shù)也太大了點(diǎn)。。。

OK，我接下來又想到了是否可以通過樹的遍歷，想了想被我否了。

終于想到了一種方式，就是通過不斷的交換獲得。我們想到，如果從一個(gè)第1大的數(shù)變成第2大的數(shù)，必然要使這個(gè)數(shù)增大，那么怎么個(gè)增大法？才能使得這兩個(gè)數(shù)是最接近的，也就是說我們只增加了1，而不是中間還存在很多數(shù)呢？

那就是從左到右掃描數(shù)據(jù)，直到遇到10就交換，并且在該1之前的1要和***位的0交換。好的思路已經(jīng)完全暴露了，我這里就列舉一個(gè)例子。

比如5個(gè)1，5個(gè)0的情況。

我們保存的格式是1111100000(實(shí)際數(shù)為0000011111)，它是最小的數(shù)(輸出的時(shí)候倒著輸出，這種結(jié)構(gòu)主要為了理解方便)。***的數(shù)是0000011111.（記住，是倒著哈！）

當(dāng)我們要增加的時(shí)候在J=5的時(shí)候，出現(xiàn)了0，且j=4時(shí),它為1，這樣就交換他們，j=4之前的1和低位的0交換，這里沒有0就不需要交換了。得到1111010000（實(shí)際數(shù)為0000101111）.

當(dāng)我們出現(xiàn)0011101100(實(shí)際數(shù)為0011011100)要使數(shù)字增加1應(yīng)該怎么做呢？顯然，還是J=5時(shí)出現(xiàn)了0且j-1=4時(shí)為1交換他們，并且j=4之前的1和***位的0開始不斷交換，***我們會(huì)得到結(jié)果：1100011100.(實(shí)際數(shù)為00111000011).

Ok,說到這里大家應(yīng)該就完全懂了，且看算法源代碼：[集思廣益，你們有沒有更好的解決方案？]

//M：0的個(gè)數(shù)，N，1的個(gè)數(shù)。K要輸出第幾個(gè)數(shù)。 
bool test(int N,int M,int K){ 
    if(calculateTotalNum(M+N,M)<K)//若實(shí)際上的數(shù)少于k，返回false,則輸出impossible 
        return false; 
    int L=M+N,count=1; 
    bitset<MaxLength> bit; 
    map<int,bitset<MaxLength>> mapStr; 
    for(int i=0;i<M;i++)//初始話最小數(shù)，即0都在最左邊比如0011 
        bit[i]=1; 
    if(K==1){ 
        print(bit,M+N);//輸出 
        return true; 
    } 
    int j=0;//表示從低位一直搜索到高位，有沒有遇到01，有的話就不斷交換。 
    while(!isLast(bit,M,N)){//沒有搜索到***一個(gè)數(shù)字 
        if(j>=M+N-1) 
            j=0;//已經(jīng)搜索到***位了，這個(gè)時(shí)候就需要從0位搜索 
        if(1==bit[j]&&0==bit[j+1]){ 
            int right=j-1,left=0; 
            //從J的前一個(gè)搜素，并且該之前的1全部移動(dòng)到最左邊 
            while(right>=0&&bit[right]==1&&left<right){ 
                bool temp=bit[right]; 
                bit[right]=bit[left]; 
                bit[left]=temp; 
                right--,left++; 
            } 
            bit[j]=0;//交換0,1 
            bit[j+1]=1; 
            count++;//統(tǒng)計(jì)是第幾個(gè)大的數(shù)了 
            if(count==K){ 
                print(bit,M+N); 
                return true; 
            } 
            j=0;//重新回過頭來搜素 
        } 
        else 
            j++; 
    } 
    return true; 
} 
 
int calculateTotalNum(int N,int M){//組合問題，計(jì)算一共多少個(gè)數(shù)。C(M,N)=A(N,N)/(A(M,M)*A(N-M,N-M)) 
    int result=1; 
    for(int i=1;i<=N;i++) 
        result*=i; 
    for(int i=1;i<=M;i++) 
        result/=i; 
    for(int i=1;i<=N-M;i++) 
        result/=i; 
    return result; 
} 
bool isLast(bitset<MaxLength> bit,int M,int N){ 
    int i=0; 
    while(i<N&&0==bit[i]) 
        i++; 
    if(i==N) 
        return true; 
    else 
        return false; 
} 
void print(bitset<MaxLength> bit,int N){// 
    for(int i=N-1;i>=0;i--) 
        cout<<bit[i]; 
    cout<<"　　"; 
} 

 附上效果截圖：

 [庸男勿擾] 同學(xué)提供了一種其他的解決方式，主要是通過遞歸的判斷當(dāng)前0,1組合生成的個(gè)數(shù)與K進(jìn)行比較。

(保證在不減一個(gè)0時(shí)，生成的組合總數(shù)是大于K的，否則return。)

若當(dāng)前0的個(gè)數(shù)減一后，生成的總數(shù)要大于K，則輸出0，同時(shí)0的個(gè)數(shù)減一，K,1的個(gè)數(shù)不變。

若當(dāng)前0的個(gè)數(shù)減一后，生成的總數(shù)小于K，則輸出1，同時(shí)1的個(gè)數(shù)減一，0的個(gè)數(shù)不變，K=K-當(dāng)前總數(shù)。

遞歸調(diào)用。***能得到結(jié)果。

代碼 [庸男勿擾] 已經(jīng)貼出，在回答留言處！

[有一個(gè)問題是，我和庸男勿擾在計(jì)算總次數(shù)的時(shí)候都會(huì)有溢出的問題，即使用Long long也會(huì)溢出的，大家在計(jì)算階乘或者組合問題對(duì)溢出解決方案有什么好的建議可以給出嗎？] 

原文鏈接：http://www.cnblogs.com/xiaoyi115/p/3696507.html