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

时光机TimeMachine

——一个退役OIer

 
 
 

日志

 
 

[BZOJ3790]神奇项链  

2014-12-11 14:45:34|  分类: Problems |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3790: 神奇项链

不就之后就要被权限掉的题
hash写得各种不熟……但是写后缀数组感觉有点浪费,manacher又不会……
另外注意数据范围似乎应该是1e5
然后因为清空部分写得姿势不好WA了一次。
题解在代码下方

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 100000+10;
const int MOD = 1E9+77;
const int MAX = 2E9;
typedef long long ll;
typedef pair<int,int> Data;
int n,m;
int tree[N],en;
Data edges[N*2];
bool operator < (Data &a,Data &b){return a.second == b.second?a.first < b.first:a.second < b.second;}
void push(int x,int val){for(x++;x;x-=x&-x)tree[x] = min(tree[x],val);}
int get(int x){int re=MAX;for(x++;x<=n+1;x+=x&-x)re = min(re,tree[x]);return re;}
char str[N];
int hash[2][N];
int MUL[N]={1,75};
bool cmp(int l1,int l2,int len,short t=0){
int tmp[2];
tmp[0] = ((ll)hash[0][l1+len-1] - (ll)hash[0][l1-1]*MUL[len])%MOD;
tmp[1] = ((ll)hash[1][l2+len-1] - (ll)hash[1][l2-1]*MUL[len])%MOD;
if(tmp[0] < 0)tmp[0] += MOD;
if(tmp[1] < 0)tmp[1] += MOD;
//if(t)printf("[%d %d]\n",tmp[0],tmp[1]);
return tmp[0] == tmp[1];
}
int main(){
int i,j;
while(scanf("%s",str+1)!=EOF){
n = strlen(str+1);
en=0;
for(i=1;i<=n;i++){
tree[i]=MAX;
if(i>1)MUL[i] = (ll)MUL[i-1]*MUL[1]%MOD;
hash[0][i] = ((ll)hash[0][i-1]*MUL[1] + str[i]-'a')%MOD;
hash[1][i] = ((ll)hash[1][i-1]*MUL[1] + str[n-i+1]-'a')%MOD;
}tree[i] = MAX;
//for(i=1;i<=n+1;i++) printf("%d ",tree[i]);printf("\n");
//for(i=1;i<=n;i++)printf("%d ",hash[1][i]);printf("\n");
for(i=1;i<=n;i++){
int l,r;
//0
if(i+1 <= n && str[i]==str[i+1]){
//short DEBUG=0;
//if(i==3)DEBUG=1;
l=1;r = min(i,n-i);
while(l<r){
int mid = (l+r+1)/2;
if(cmp(i+1,n-i+1,mid))l = mid;
else r = mid-1;
}
//if(i==3)DEBUG=1;
//printf("%d %d\n",i-l+1,i+1+l-1);
edges[++en] = Data(i-l+1,i+1+l-1);
}
//1
l=1;r = min(i,n-i+1);
while(l<r){
int mid = (l+r+1)/2;
//if(DEBUG)printf("%d %d %d",mid,i);
if(cmp(i,n-i+1,mid))l = mid;
else r = mid-1;
}
//if(i==2)DEBUG=0;
//printf("%d %d\n",i-l+1,i+l-1);
edges[++en] = Data(i-l+1,i+l-1);
}
sort(edges+1,edges+1+en);
//DP
push(0,0);
int tmp=MAX;
for(i=1;i<=en;i++){
j = get(edges[i].first-1)+1;
if(j < tmp)tmp = j;
if(edges[i].second!=edges[i+1].second || i==en){
push(edges[i].second,tmp);
tmp = MAX;
}
}
printf("%d\n",get(n)-1);
}
return 0;
}

题解:
找出所以尽可能大的回文串,最多有2*n个。
回文串用Hash写的
问题变成选尽可能少的可重复区间覆盖整个序列
然后sort区间做DP
  评论这张
 
阅读(54)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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