问题:
http://poj.org/problem?id=1147思路:
这题太精妙了...
恐怕是到目前为止，最为精妙的了...
翻了很多网上资料，才想明白，艾，推理能力太差...
关键点:
1. 对于排序后的矩阵，每一行都可以通过第一行旋转得到
2. 假设矩阵中两行都以0开始，则它们左旋后，前后次序不变，所以在矩阵中以0开始的第1行，它的左旋后的序列在最后一列的第一个0的行。对1 开始的行有同样的性质
3. 通过1、2两点即可确定next数组，即第一列与最后一列的对应关系
4. 观察题目给出的Figure 1，可以看出第一列与最后一列之间的巧妙关系: b2可以通过找到第一列b1所对应的最后一列的所在行而得到
代码:
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<string.h>
4 #define MAX_LEN 3001
5 int first_col[MAX_LEN], last_col[MAX_LEN];
6 int N, zeros, ones, next[MAX_LEN];
7
8 int
9 main(int argc, char **argv)
10 {
11 int i, count;
12 while(scanf("%d", &N) != EOF) {
13 zeros = ones = 0;
14 for(i=1; i<=N; i++) {
15 scanf("%d", last_col+i);
16 if(last_col[i] == 0)
17 first_col[++zeros] = 0;
18 else
19 ++ones;
20 }
21 for(i=1; i<=ones; i++)
22 first_col[zeros+i] = 1;
23 ones = zeros+1;
24 zeros = 1;
25 for(i=1; i<=N; i++) {
26 if(last_col[i] == 0)
27 next[zeros++] = i;
28 else
29 next[ones++] = i;
30 }
31
32 for(count=1, i=1; count<=N; i=next[i], ++count)
33 printf("%d ", first_col[i]);
34 printf("\n");
35 }
36 }