問(wèn)題:
http://poj.org/problem?id=1147思路:
這題太精妙了...
恐怕是到目前為止，最為精妙的了...
翻了很多網(wǎng)上資料，才想明白，艾，推理能力太差...
關(guān)鍵點(diǎn):
1. 對(duì)于排序后的矩陣，每一行都可以通過(guò)第一行旋轉(zhuǎn)得到
2. 假設(shè)矩陣中兩行都以0開(kāi)始，則它們左旋后，前后次序不變，所以在矩陣中以0開(kāi)始的第1行，它的左旋后的序列在最后一列的第一個(gè)0的行。對(duì)1 開(kāi)始的行有同樣的性質(zhì)
3. 通過(guò)1、2兩點(diǎn)即可確定next數(shù)組，即第一列與最后一列的對(duì)應(yīng)關(guān)系
4. 觀察題目給出的Figure 1，可以看出第一列與最后一列之間的巧妙關(guān)系: b2可以通過(guò)找到第一列b1所對(duì)應(yīng)的最后一列的所在行而得到
代碼:
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 }