注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ4104][ThuSC2015]解密运算  

2015-06-20 16:02:01|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

4104: [Thu Summer Camp 2015]解密运算

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 116  Solved: 72
[Submit][Status][Discuss]

Description

 对于一个长度为N的字符串,我们在字符串的末尾添加一个特殊的字符"."。之后将字符串视为一个环,从位置1,2,3,...,N+1为起点读出N+1个字符,就能得到N+1个字符串。

比如对于字符串“ABCAAA”,我们可以得到这N+1个串:
ABCAAA.
BCAAA.A
CAAA.AB
AAA.ABC
AA.ABCA
A.ABCAA
.ABCAAA
接着我们对得到的这N+1个串按字典序从小到大进行排序(注意特殊字符“.”的字典序小于任何其他的字符)结果如下:
.ABCAAA
A.ABCAA
AA.ABCA
AAA.ABC
ABCAAA.
BCAAA.A
CAAA.AB
最后,将排序好的N+1个串的最后一个字符取出,按照顺序排成一个新的字符串,也就是上面这个表的最后一列,就是加密后的密文“AAAC.AB”。
请通过加密后的密文求出加密前的字符串。

Input

第一行有两个整数N,M,分别表示加密前的字符串长度和字符集大小,其中字符用整数1,2,3,...,M编号,添加的特殊字符“."用0编号。
第二行为N+1个整数,表示加密后的字符串。

Output

输出仅一行,包含N个整数,用空格隔开,依次表示加密前字符串中每个字符的编号。

Sample Input

6 3 1 1 1 3 0 1 2

Sample Output

1 2 3 1 1 1

HINT

#i (i=1~4)    N=5*(i+1) M<=3

#5~6    N,M<=50 字符串中字符互不相同

#7~8    N,M<=1000 字符串中字符互不相同

#9~12    N,M<=1000

#13~#20    N,M<=200000

Solution

对于样例输入,我们可以确定如下对应方式(A->B表示A之后为B):
A -> .
A -> A
A -> A
C -> A
. -> A
A -> B
B -> C
其中字母A表示不唯一。
然后以第一列为第一关键字,第二列为第二关键字sort一下,还是按照刚才的对应方式,然后前面加一列(因为最前面的那一列在第二列排完序以后是惟一确定的),像这样:
A -> . -> A
A -> A -> .
A -> A -> A
C -> A -> A
. -> A -> B
A -> B -> C
B -> C -> A
重复这个过程,可以用平方的时间来得到答案。
然而我们发现这个过程一直在重复同一种对应方式。实际上对应方式就是每个字母a[i]的下一个字母为sa[i],所以只要用O(n+m)的时间用计数排序来处理出sa数组就好了。其中n为字符串长度,m为字符集大小。

Code

/**************************************************************
    Problem: 4104
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:272 ms
    Memory:11372 kb
****************************************************************/
 
#include<cstdio>
char ch,B[1<<15],*S=B,*T=B;
#define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++)
int aa;int F(){
    while(ch=getc(),ch<'0'||ch>'9');aa=ch-'0';
    while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return aa;
}
char buf[1<<23],*O=buf,stk[10];int ts;
void P(int x){
    if(!x)*O++='0';else{
        for(ts=0;x;x/=10)stk[++ts]=x%10;
        for(;ts;*O++='0'+stk[ts--]);
    }*O++=' ';
}
#define N 200010
int n,m,s[N],sa[N],c[N],i,o;main(){
    for(n=F()+1,m=F(),i=1;i<=n;i++)c[s[i]=F()]++,!s[i]?o=i:1;
    for(i=1;i<=m;i++)c[i]+=c[i-1];
    for(i=n;i;i--)sa[c[s[i]]--]=i;
    while(s[o=sa[o]])P(s[o]);puts(buf);
}
  评论这张
 
阅读(171)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018