好题, 著名的BWT算法. 我们先看给定的例子
00011 00110 01100 10001 11000
题目的输入是最后一列, 我们可以看到, 第一列必然是按照00..11, 这种样式排列的, 1的个数是输入的1的个数. 这样我们就有了第一列了.
那如何知道第一行第二个字符呢? 我们如果把前面的3行的第一个零移到最后面, 新的3行仍然按照字典序排列. 这就是解题的关键了.
我们知道第一行左旋后, 0移到最后面, 但是仍然按照字典序排列的话, 我们就可以从最后一列找到第一个0出现的位置, 这里是2. 则我们就可以知道第一行左旋后变成了第二行, 而第二行的第一个字符即是第一行的第二个字符. 如此类推.
/******************************************************************************* # Author : Neo Fung # Email : neosfung@gmail.com # Last modified: 2012-03-07 19:24 # Filename: POJ1147 Binary codes.cpp # Description : ******************************************************************************/ #ifdef _MSC_VER #define DEBUG #define _CRT_SECURE_NO_DEPRECATE #endif #include <fstream> #include <stdio.h> #include <iostream> #include <string.h> #include <string> #include <limits.h> #include <algorithm> #include <math.h> #include <numeric> #include <functional> #include <ctype.h> #define MAX 3001 using namespace std; int input[MAX],tmp[MAX],next[MAX]; bool used[MAX]; int main(void) { #ifdef DEBUG freopen("../stdin.txt","r",stdin); freopen("../stdout.txt","w",stdout); #endif int n; while(~scanf("%d",&n) && n) { int cnt=0; memset(used,false,sizeof(used)); memset(tmp,0,sizeof(tmp)); for(int i=0;i<n;++i) { scanf("%d",&input[i]); if(input[i]) ++cnt; } for(int i=n-cnt;i<n;++i) tmp[i]=1; for(int i=0;i<n;++i) { int j=0; while(tmp[i]!=input[j] || used[j]) ++j; used[j]=true; next[i]=j; } int ind=0; for(int i=0;i<n;++i) { ind=next[ind]; printf("%d%c",input[ind],i==(n-1)?'\n':' '); } } return 0; }