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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ2062]素颜2(face2)  

2014-12-16 21:37:03|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2062: 素颜2(face2)

还算比较裸的题,但是写起来有点蛋疼……
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
const int LOGN = 22;
int n,m,Sa[N],anc[N][LOGN];
char str[N];
short v[N][LOGN];
namespace Suf{
int tl[N],tmp[2][N*2],cot[N];
struct List{
List(){d=0;next = NULL;}
int d;List *next;
void push(int);void pop();
}list[N],house[N];int hn=0;
queue<List*>pupa;
List *newList(){
if(hn<N)return &house[hn++];
List *l = pupa.front();pupa.pop();
if(l->next)pupa.push(l->next);
*l = List();return l;
}
void List::push(int a){
List *l = newList();
l->d = a;l->next = next;next = l;
}
void List::pop(){}
int Anc(int x,int k){
if(k>=LOGN || x==-1)return -1;
if(v[x][k])return anc[x][k];
v[x][k]=1;
anc[x][k] = Anc(Anc(x,k-1),k-1);
return anc[x][k];
}
void sort(int n,char s[],int sa[]){
int i,j,k,*x=tmp[0],*y=tmp[1],p=0;
int m='z'+1;
for(i=0;i<m;i++)cot[i] = 0;
for(i=0;i<n;i++)cot[x[i]=s[i]]++;
for(i=1;i<m;i++)cot[i] += cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[x[i]]] = i;
for(j=1,k=0;j<n&&p<n;j+=j,m=p,k++){
//sort 2
for(i=n-1;i>=0;i--)list[x[Anc(i,k)]].push(i);
for(i=0,p=0;i<m;i++){
for(List *l = list[i].next;l!=NULL;l=l->next)y[p++] = l->d;
if(list[i].next){pupa.push(list[i].next);list[i].next = NULL;}
}
for(i=0;i<n;i++)tl[i] = x[y[i]];
//sort 1
for(i=0;i<m;i++)cot[i] = 0;
for(i=0;i<n;i++)cot[tl[i]]++;
for(i=1;i<m;i++)cot[i] += cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[tl[i]]] = y[i];
//calc x
swap(x,y);x[sa[0]] = 0;p=1;
for(i=1;i<n;i++)
x[sa[i]] = y[sa[i]]==y[sa[i-1]]&&y[Anc(sa[i],k)]==y[Anc(sa[i-1],k)]?p-1:p++;
}
}
}
int scan(){
char cc=' ';int re=0,fh=1;
while(cc==' '||cc=='\r'||cc=='\n')cc=getchar();
if(cc=='+')cc=getchar(),fh=1;
if(cc=='-')cc=getchar(),fh=-1;
while('0'<=cc&&cc<='9'){
re=re*10+cc-'0';
cc=getchar();
}return re*fh;
}
int main(){
int i,j;char cc;
//freopen("out.txt","w",stdout);
n = scan();
for(i=0;i<n;i++){
scanf(" %c",&cc);
str[i]=cc;
}
for(i=0;i<n;i++)anc[i][0] = scan()-1,v[i][0]=1;
Suf::sort(n,str,Sa);
for(i=0;i<n;i++)
printf("%d\n",Sa[i]+1);

return 0;
}

题解:
后缀数组倍增算法变形。
原来是对字符串求后缀数组,现在是对一个奇怪的东西求。
稍稍修改一下算法就行,把原来找后面第2^j个的部分修改成像树上倍增一样的方法。
还有y数组的求法也需要稍微改一下,因为这里一个串可能对应多个前驱(这里应该是变化最大的地方)
写之前多想想就好了,我因为没想好WA了一次……注意相同串的处理
  评论这张
 
阅读(24)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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