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

fudq's AC Road

何以解忧,唯有AC!

 
 
 

日志

 
 

hdu 4691 Front compression  

2013-08-21 14:58:37|  分类: ACM-hdu |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
http://acm.hdu.edu.cn/showproblem.php?pid=4691
先给出一个字符串s,然后n个区间,每个区间两个边界值a,b,表示s的子串[a, b)。现在将子串进行压缩,如果当前的子串[a, b)和上一个子串[x, y)的最大共同前缀为t,则记子串[a, b)为:t 子串[t+1,b)。问n个区间压缩前和压缩后所需的总字符个数(包括空格和回车)。
题解:
后缀数组+RMQ。
先将字符串s用后缀数组处理一遍,然后利用RMQ预处理height数组,以a为首的后缀和以b为首的后缀的最长公共前缀为min(height[i]), rank[a] < i <= rank[b],如果rank[a] > rank[b],则交换下。处理完后,给出当前的子串[a, b),已知上一个子串[x, y),可以查询出以a为首的后缀和以x为首的后缀的最长公共前缀tmp,然后和tt=min(b-a, y-x)进行比较,如果tmp > tt,则得到被压缩部分为tt,否则为tmp。
直接把后缀数组和RMQ的模板贴上来,然后再稍做处理便可,最后数据用int64表示,因rmq_n数组开小了wa了好几次。。。

/*
* pro.cpp
*
* Created on: 2013-08-21
* Author: fudq
*/
#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;
//#pragma comment(linker,"/STACK:102400000,102400000")

#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define LL __int64

const int N=100010;
const int M=32010;
const int MOD=1000000007ll;
const int INF=0x7fffffff;
const int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const double eps=1e-7;
const double PI=acos(-1.0);

inline int sign(double x){return (x>eps)-(x<-eps);}
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T lcm(T a,T b,T d){return a/d*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
template<class T> inline T Min(T a,T b,T c){return min(min(a, b),c);}
template<class T> inline T Max(T a,T b,T c){return max(max(a, b),c);}
template<class T> inline T Min(T a,T b,T c,T d){return min(min(a, b),min(c,d));}
template<class T> inline T Max(T a,T b,T c,T d){return max(max(a, b),max(c,d));}
/*************************/

char s[N];
int n, sa[4*N], rank[N], height[N];
int buf[4*N], ct[N], sx[N], sax[N];

inline bool leq(int a, int b, int x, int y)
{
return (a < x || a == x && b <= y);
}
inline bool leq(int a, int b, int c, int x, int y, int z)
{
return (a < x || a == x && leq(b, c, y, z));
}
inline int geti(int t, int nx, int sa[])
{
return (sa[t]<nx ? sa[t]*3+1 : (sa[t]-nx)*3+2);
}

static void radix(int a[], int b[], int s[], int n, int k)
{
int i, t, sum;
memset(ct, 0, (k + 1) * sizeof(int));
for (i = 0; i < n; ++i) ct[s[a[i]]]++;
for (i = 0, sum = 0; i <= k; ++i)
{
t = ct[i]; ct[i] = sum; sum += t;
}
for (i = 0; i < n; i++) b[ct[s[a[i]]]++] = a[i];
}

void suffix(int s[], int sa[], int n, int k)
{
int i, j, e, p, t;
int name = 0, cx = -1, cy = -1, cz = -1;
int nx = (n+2)/3, ny = (n+1)/3, nz = n/3, nxz = nx+nz;
int *syz = s + n + 3, *sayz = sa + n + 3;
for (i=0, j=0; i < n + (nx - ny); i++)
if (i%3 != 0) syz[j++] = i;
radix(syz , sayz, s+2, nxz, k);
radix(sayz, syz , s+1, nxz, k);
radix(syz , sayz, s , nxz, k);
for (i = 0; i < nxz; i++)
{
if (s[ sayz[i] ] != cx || s[ sayz[i] + 1 ] != cy ||s[ sayz[i] + 2 ] != cz)
{
name++; cx = s[ sayz[i] ];
cy = s[ sayz[i] + 1 ]; cz = s[ sayz[i] + 2 ];
}
if (sayz[i] % 3 == 1) syz[ sayz[i] / 3 ] = name;
else syz[ sayz[i]/3 + nx ] = name;
}
if (name < nxz)
{
suffix(syz, sayz, nxz, name);
for (i = 0; i < nxz; i++) syz[sayz[i]] = i + 1;
}
else
{
for (i = 0; i < nxz; i++) sayz[syz[i] - 1] = i;
}
for (i = j = 0; i < nxz; i++)
if (sayz[i] < nx) sx[j++] = 3 * sayz[i];
radix(sx, sax, s, nx, k);
for (p=0, t=nx-ny, e=0; e < n; e++)
{
i = geti(t, nx, sayz); j = sax[p];
if ( sayz[t] < nx ?leq(s[i], syz[sayz[t]+nx], s[j], syz[j/3]) :
leq(s[i], s[i+1], syz[sayz[t]-nx+1],
s[j], s[j+1], syz[j/3+nx]) )
{
sa[e] = i;
if (++t == nxz)
{
for (e++; p < nx; p++, e++)
sa[e] = sax[p];
}
}
else
{
sa[e] = j;
if (++p == nx) for (++e; t < nxz; ++t, ++e)
sa[e] = geti(t, nx, sayz);
}
}
}

void makesa()
{
memset(buf, 0, 4 * n * sizeof(int));
memset(sa, 0, 4 * n * sizeof(int));
for (int i=0; i<n; ++i) buf[i] = s[i] & 0xff;
suffix(buf, sa, n, 255);
}

void lcp()
{
int i, j, k;
for (j = rank[height[i=k=0]=0]; i < n - 1; i++, k++)
while (k >= 0 && s[i] != s[ sa[j-1] + k ])
height[j] = (k--), j = rank[ sa[j] + 1 ];
}

void Rank()
{
for(int i=1;i<n;i++)
rank[sa[i]]=i;
}


int rmq_n[N][32];
void rmq_init(int arr[],int n)
{
int i,j;
for(i=1;i<=n;++i)
rmq_n[i][0]=arr[i];
for(j=1;j<=int(log(n+0.0)/log(2.0));++j)
for(i=1;i+(1<<j)-1<=n;++i)
rmq_n[i][j]=min(rmq_n[i][j-1],rmq_n[i+(1<<(j-1))][j-1]);
}

int rmq(int a,int b)
{
int m=int(log(b-a+1.0)/log(2.0));
int x=min(rmq_n[a][m],rmq_n[b-(1<<m)+1][m]);
return x;
}

int Get(int a)
{
int s=0;
if(a < 10)
return 1;
while(a)
{
a/=10;
s++;
}
return s;
}

void solve()
{
n=(int)strlen(s)+1;
makesa();
Rank();
lcp();
rmq_init(height,n);
int m,a,b,x,y,tmp,res,tt,len1,len2;
LL s1=0,s2=0;
scanf("%d",&m);
scanf("%d%d",&x,&y);
s1=y-x+1;s2=s1+2;
for(int i=1;i<m;i++)
{
scanf("%d%d",&a,&b);
s1=s1+b-a+1;len1=y-x;len2=b-a;tt=min(len1,len2);
if(x == a)
res=tt;
else
{
if(rank[x] < rank[a])
tmp=rmq(rank[x]+1,rank[a]);
else
tmp=rmq(rank[a]+1,rank[x]);

if(tmp > tt)
res=tt;
else
res=tmp;
}
s2=s2+Get(res)+len2-res+2;
x=a;y=b;
}
printf("%I64d %I64d\n",s1,s2);
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("testin.txt","r",stdin);
//freopen("testout.txt","w",stdout);
#endif
while(scanf("%s",s)!=EOF)
solve();
return 0;
}



  评论这张
 
阅读(122)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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