HauntedProgrammer's Blog

A said strange person

[BZOJ 2408]混乱的置换

HauntedProgrammer posted @ 2015年1月01日 02:46 in 未分类 , 893 阅读

裸的iBWT...[tex]O(n+m)[/tex]时空复杂度(这个m有什么贡献吗@.@)

BWT: 就是题目中的给定一个字符串,求出“矩阵”中的最后一列

iBWT: 给出“矩阵”中的最后一列,求出原串 

可以先算一个[tex]\psi[/tex]变换,然后遍历一遍。详情查阅Wikipedia -- Burrows-Wheeler Transform。

#include <cstdio>
#define MAXN 30000
int n,m,ai[MAXN],str[MAXN],cnt[12],p[MAXN],sm,mini=12,bufpt=0,tmp=0;
char buf[100000];
int getint()
{
    tmp=0;
    while(buf[bufpt]<'0'||buf[bufpt]>'9') bufpt++;
    while(buf[bufpt]>='0'&&buf[bufpt]<='9') tmp=10*tmp+buf[bufpt++]-'0';
    return tmp;
}
int main()
{
    fread(buf,sizeof(char),sizeof(buf),stdin);
    n=getint(),m=getint();
    for(int i=1;i<=n;i++) ai[i]=getint();
    for(int i=1;i<=n;i++) cnt[ai[i]]++;
    for(int i=1;i<=n;i++) if(ai[i]<mini) mini=ai[i],sm=i;
    for(int i=9;i;i--) cnt[i]=cnt[i-1];
    cnt[0]=0;
    for(int i=1;i<10;i++) cnt[i]+=cnt[i-1];
    for(int i=1;i<=n;i++) p[++cnt[ai[i]]]=i;
    for(int i=1,k=sm;i<=n;i++) str[i]=ai[k],k=p[k];
    printf("%d",str[1]);
    for(int i=2;i<=n;i++) printf(" %d",str[i]);
    printf("\n");
    return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter