二进制串题解(国际考试备用题)

                                             二进制串

    (bin.cpp）

 【问题描述】

    有Ｎ个二进制数串 B=(b , b , ..., b )，我们按以下方法建立一个矩阵Ｍ：
                         1   2  .....  N

    矩阵Ｍ的第一行是二进制数串Ｂ；
    后面的每一行都是通过把前一行循环左移而得到的。    
    b  b  ... b     b
    1  2       N-1  N

    b  b  ... b b
    2  3       N   1

   ...
    b    b  ... b    b
    N-1  N       N-3  N-2

   b  b  ... b     b
  N   1      N-2  N-1

    然后，把以行为单位按字典顺序排序得到矩阵Ｍ。
    请写一个程序，给出矩阵Ｍ的最后一列（排序以后），求第一行（也是排序以后的）。

【输入文件】

    第一行有一个正整数Ｎ，表示二进制串Ｂ的长度，第二行有Ｎ个用空格隔开的二进制数
    字，表示矩阵Ｍ的最后一列。

【输出文件】

    只有一行二进制串，表示矩阵Ｍ的第一行，这Ｎ个二进制数字没有用空格隔开。
    样例1    
    bin1.in    
    5    
    1 0 0 1 0    

    bin1.out    
    00011

    bin2.in    
    8    
    1 1 0 1 1 0 1 0

    bin2.out    
    00111011

【数据范围】

   对于 30%的数据，有N<=20
   对于 50%的数据，有N<=550
   对于 100%的数据，有0<N<=5000

   这道题主要是一道找规律的题目
   因它是每次左移，所以每个数字都会出现在结尾
   所以它出现了几个1，整个二进制串就有几个1
   其次同理每个数字也会出现在开头
   所以按大到小排列最大的开头肯定是1
   现在来看一下样例，我们可以得出这样的结论①
   0xxx1
   0xxx0
   0xxx0
   1xxx1
   1xxx0
   这里的未知数都用xxx代替，但不表示xxx是相同的
   因为它是从小到大排列的，所以往左移之后就是
   xxx10
   xxx00
   xxx00
   xxx11
   xxx01
   这样看起来是变了，但是实际上它的组合数不变，组合方式不变，只是排序方式变了
   我们再将它排序就会变回结论①
   但是我们不知道这些数字前面的数字是哪一个地方的
   这里说明一下
   结论①里最小的二进制串左移之后再排序，它肯定就变成了结论①里的第2串
   因为它的后面4个是最小的，其他的例如2号串左移之前的后4个组成的二进制串肯定比1号组成的大
   所以左移之后1就变成了2号
   注意，这里不是说1号变成2号,所以2号变成3号，3号变成4号....
   是说0开头的1号变成了0结尾的2号
   那么，1开头的4号就变成了1结尾的1号
   以此类推，排序，会发现每次都是这样子，左移之后排序都是这个顺序变化
   然而要推出所有数字要n-1次，经过变化后最后一行便就是在原来的基础上按这个方法来一遍
   即0开头的按顺序到了0结尾的去了，1开头的按顺序到了1结尾的去了

   如样例
           顺序变化
   0  1      1->2
   0  0      2->3
   0  0      3->5
   1  1      4->1
   1  0      5->4
   再按照这个变化方式输出一次
   第一个输出是1号对应的2号
   第二个输出是2号对应的3号
   第三个输出是3号对应的5号
   第四个输出是4号对应的5号
   第五个输出是5号对应的4号
   最后输出便是00011

   Code: