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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3620]似乎在梦中见过的样子  

2014-12-07 11:06:08|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3620: 似乎在梦中见过的样子

卡你妹的常数啊啊啊
搞了一上午还是没过QAQ
最后无节操交标程A了
“Madoka,不要相信 QB(shu ju fan wei)!”
现在我的代码也能A了QuQ,感谢ydc神犇
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
//using namespace std;
/*
#include<ctime>
int start = clock();
*/
const int N = 15000+10;
const int LOGN = 22+1;
int n,m,Sa[N],height[N];
int st[LOGN][N],two[50];
int Log2[N],*_2d[N];
int tmp,tmp1,tmp2;
inline int min(const int a,const int b){return a > b? b: a;}
inline int max(const int a,const int b){return a < b? b: a;}
inline void swap(int &a,int &b){tmp=a;a=b;b=tmp;}
namespace Suf{
int tmp[2][N*2],tl[N],cot[N];
void sort(int n,char s[],int sa[]){
int i,j,r,*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=0;i<m;i++)cot[i]+=cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[x[i]]] = i;
for(j=1;j<n,p<n;j+=j,m=p){
//sort 1
for(p=0,i=n-j;i<n;i++)y[p++] = i;//*
for(i=0;i<n;i++)if(sa[i] >= j)y[p++] = sa[i]-j;
for(i=0;i<n;i++)tl[i] = x[y[i]];
//sort 2
for(i=0;i<m;i++)cot[i] = 0;
for(i=0;i<n;i++)cot[tl[i]]++;
for(i=0;i<m;i++)cot[i]+=cot[i-1];
for(i=n-1;i>=0;i--)sa[--cot[tl[i]]] = y[i];
//get x
std::swap(x,y);x[sa[0]] = 0;p=1;
for(i=1;i<n;i++)
if((sa[i]+j<n)^(sa[i-1]+j<n))x[sa[i]] = p++;
else x[sa[i]] = y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]?p-1:p++;
}
}
void geth(int n,char s[],int sa[],int h[]){
int i,j,k=0,*rank = tmp[0];
for(i=0;i<n;i++)rank[sa[i]] = i;

for(i=0;i<n;h[rank[i++]] = k)
if(rank[i]-1 >= 0) for(k=k?k-1:k,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
else k = 0;
}
}
char str[N];
int main(){
//freopen("in.txt","r",stdin);
//freopen("dream2.in","r",stdin);
int i,j;
scanf("%s",str);
int len = strlen(str);
scanf("%d",&m);
Suf::sort(len,str,Sa);
//printf("geth\n");
Suf::geth(len,str,Sa,height);
/*
for(i=0;i<len;i++){
printf("[%d]%s\n",height[i],str + Sa[i]);
}*/
for(i=0;i<len;i++)Log2[i+1] = log2(i+1),_2d[i] = st[i];
for(i=1;i<len;i++)st[0][i] = height[i];
for(i=1,two[0]=1;i<=30;i++)two[i] = two[i-1]*2;
int lgn = log2(len-1)+1;
for(j=1;j<=lgn;j++)
for(i=1;i+two[j-1]<=len-1;i++)
st[j][i] = min(st[j-1][i],st[j-1][i+two[j-1]]);
int ans = 0,*rank = Suf::tmp[0];
//printf("%d\n",lcp(rank[0],rank[1]));
//Count Ans

//printf("%d\n",clock()-start);

//printf("End");
int I = len-1 - ((2*m+1)-1),
J = len-1 - (m-1);
//printf("\n%d %d\n",st[10][0],*((int*)&st + ((int*)&st[10][0] - (int*)&st) ));
//printf("%d\n",st[230][0]);
int T=0;
for(i=0;i<=I;i++){
int last = 0,l,r;
for(j=i+m+1;j<=J;j++){
//r = lcp(rank[i],rank[j]);
//if(T%100==0)printf("YM zky\n");
if(1){
int l = rank[i],r = rank[j];
if(r < l){tmp=l;l=r;r=tmp;}
l++;
int k = Log2[r-l+1];
tmp = min(st[k][l],st[k][r-two[k]+1]);

//tmp1 = *(_2d[l]+k);
//tmp2 = *(_2d[r-two[k]+1] + k);
//if(tmp1 < tmp)tmp = tmp1;
//tmp = min(*(_2d[l]+k),*(_2d[r-two[k]+1] + k));
//tmp = //st[l][k],st[r-two[k]+1][k]
//tmp=j^i;
}

r = tmp;
l = m;r = min(r,j-i-1);
l = max(l,last - j+1 +1);
//if(r-l+1 <= 0)continue;
//printf("%d %d [%d %d]\n",i,j,l,r);
//if(i==0 && j==3)printf("last:%d \n",last);
if(r-l+1>0){
ans = ans + r-l+1;
last = j+r-1;
}
T++;
}
}
printf("%d\n",ans);
return 0;
}

题解:
不会kmp的做法……所以写的后缀数组。
首先搞出h数组,建好st表,然后就可以O(1)查询lcp
然后枚举两个A串的起点
比较蛋疼的地方是一个区间可能有多种划分方案,但是只能计算一次。
但是可以发现如果两个区间左端点不同,那么一定不同。
所以先枚举左边A串起点,也就是区间左端点,然后可以发现区间右端点是随着你枚举右边A串起点单调递增的。
随便搞一下就行了。

然后我TM就被卡常数了
最嘲讽的是,被卡的原因是ST表访问太慢了。加了寻址优化没有任何用处
“从这件是中我得到的教训是:n≈1e8的时候,超大数组的访问会特别慢”
Update[2014-12-30]
根据ydc神犇的建议把st[N][LOGN]改成st[LOGN][N],然后用时减少一半,终于过了orz……
  评论这张
 
阅读(98)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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