| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 5647 | Accepted: 2201 |
Description
Consider a binary string (b1…bN) with N binary digits. Given such a string, the matrix of Figure 1 is formed from the rotated versions of the string.
| b1 | b2 | … | bN−1 | bN |
| b2 | b3 | … | bN | b1 |
| … | ||||
| bN−1 | bN | … | bN−3 | bN−2 |
| bN | b1 | … | bN−2 | bN−1 |
Figure 1. The rotated matrix
Then rows of the matrix are sorted in alphabetical order, where ‘0’ is before ‘1’. You are to write a program which, given the last column of the sorted matrix, finds the first row of the sorted matrix.
As an example, consider the string (00110). The sorted matrix is
| 0 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 0 | 0 |
and the corresponding last column is (1 0 0 1 0). Given this last column your program should determine the first row, which is (0 0 0 1 1).
Input
The first line contains one integer N ≤ 3000, the number of binary digits in the binary string. The second line contains N integers, the binary digits in the last column from top to bottom.
Output
The first line contains N integers: the binary digits in the first row from left to right.
Sample Input
51 0 0 1 0
Sample Output
0 0 0 1 1
对由0,1组成的n个数。照题中的旋转，最后依据每行的字典序排序，组成n*n的矩阵，给出矩阵的最后1列，求矩阵
的第首行。
给出最后一列能够求出第0列，由于是按字典序排的，所以第0列肯定0在前，1在后。而第0列为0的相对位置在最后
1列不变。由于第0列都为0，又是按字典序排的。第0列为1也一样。依据第0列和最后一列就能够将相应关系求出。
也就是next数组。
比如例子的
0 0 0 1 1
0 0 1 1 0
0 1 1 0 0
1 0 0 0 1
1 1 0 0 0
next[ ]={1,2,4,0,3}
第0行第0列为0，第0行的第1列下次旋转后为第0列的第0行，所以第0行第1列为第0列的第1行为0，第1列的第0行
为第2列的第1行，为第0列的第2行。所以第0行的第2列为第0列的第2行为0，通过推理发现为next数组中元素递推
代码：
#include#include #include using namespace std;const int maxn=5000+100;int last[maxn];int first[maxn];int next[maxn];int main(){ int n; while(~scanf("%d",&n)) { for(int i=0;i