[BZOJ 2408]混乱的置换
HauntedProgrammer
posted @ 2015年1月01日 02:46
in 未分类
, 1633 阅读
裸的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;
}
2019年9月11日 20:47
With the help of almost 10 years of experience of trusted, solid, residential residential cleaning, Tyloz Residential Cleaning Assistance Dubai make available residential vacuuming services which were trusted from many not to mention known for our outstanding good and care and attention. Our experienced Cleaners not to mention full Residential Cleaning Assistance are second to none.
2019年11月12日 20:39
Search for a position as being an information systems consultant or work as an 3rd party consultant. Consultants when using the educational historical past and skills find a way to appeal to an started company or simply work on his own.
2020年3月18日 00:54
Traveling is an excellent hobby for a myriad of people across the world. This moreover provides distinct advantages to help you people. Here's how come traveling is extremely important.
2020年3月18日 00:55
Flying also causes lifelong feelings. Whether a man or woman travels solo or and best freinds and family, the go through certainly grants him/her attractive and awesome stories, which he/she can give to people at home. A decent long holiday vacation with friends and family allows him/her to pay out some high-quality time at their side, which sequentially, benefits to help you renew and even restore family relationships and makes secure one-to-one and even family provides.
2020年3月18日 00:55
You ought to become an important Google Thing publisher. You should not worry, it's not essential to be an important 'Times Newspaper' as well as a 'Wall Highway Journal'. It is easy to set up ones own news site without difficulty. Look for those news pieces on Google and yahoo News and you'll find that there are quite a lot of ordinary websites on the website.
2020年3月18日 00:59
Analyzing the pieces of paper online and even watching 24-hour thing sites is becoming a lot more popular. Mainly because it is without a doubt cheaper and you just get alot more news. You can understand what is going on globally, as the application happens.
2020年3月18日 01:07
Technology with the long-run is without a doubt irrelevant. Which can be what a customer of mine explained when As i made an important presentation to help you him a couple of new products. I has been talking within the product's includes and health benefits and placed "state-of-the-art technology" and something to that effect, as one.
2020年4月27日 23:46
A maid with honor assignments continue till the very last minutes of your wedding working day. From always keeping the bride from the the develop eyes ahead of ceremony to ensuring that the star of the event has many of the necessities ready for the day, the maid of pay tribute to has the girl's hands full on the event. Little points like regardless of if the bride offers the wedding arrangement, veil, the girl's flower female etc. to being sure she will not be too traumatic or hungry ahead of ceremony, are especially in a maid with honor's guideline.
2020年4月27日 23:46
With regards to painting your house, there is actually something to consider. Painting, by numerous people's word is very simple, however many more would dispute on which. When you're looking to paint your home, you must always want the correct person for that business. Professional assistance can alter the piece of art experience altogether.
2021年6月06日 01:08
Hence, get beautifully clean premises by just following quite a few essential qualified advice. Plus, when it reaches getting your top-rated home cleaning, Maid Business Dubai offers the best dwelling cleaners to consider you the perfect bet. What's more, they know the way to get hold of satisfactory cleaning up results without difficulty.
2022年9月02日 03:11
Bangladesh Sylhet Division Secondary and Higher Secondary Education Board also successfully completed the Junior School Certificate and Junior Dakhil Certificate of Grade 8th standard annual terminal examination tests on November 2022 at all selected examination centers of the division, according to the reports lacks students have appeared from all districts under the Division and they all are waiting to check JSC Result 2022 Sylhet Board. Department of Secondary Education, JDC Result Sylhet Sylhet Division also conducted an evaluation process to the valuation of subject wise marks through answer sheet correction and the process of evaluation will be complete in before 2nd week of December 2022 and the education board will update answer scripts with student wise mark sheets in subject wise with total GPA grade points to Secondary and Higher Secondary Education Board Bangladesh.