BZOJ 2085 Poi2010 Hamsters Hash+倍增Floyd
来源：程序员人生 发布时间：2015-04-02 08:17:46 阅读次数：3328次
题目大意：给定n个长度总和不超过10W的字符串，求1个最短的母串，使所有字符串的出现次数之和=m 这n个字符串保证不相互包括
TM能不能好好翻译了
令f[i][j]表示第i个字符串后面接上第j个字符串后会增加多少长度
由于j1定不是i的子串，因此这实际上就是在求i的最长的后缀，该后缀同时也是j的前缀
注意不能连出长度为0的边，因此当i=j时要保证这个长度<len[i]
怎样求呢？其实Hash1下，枚举i和j，暴力做就能够了
这不会T？
首先设第i个字符串的长度为ai，设k=Σai
易知当计算f[i][j]时的复杂度是O(min(ai,aj))
那末现在的问题就是当k固定时，最大化ΣΣmin(ai,aj)
我们将所有的ai排个序，容易发现当相邻的两个数ai和aj都变成(ai+aj)/2时目标函数1定会增大
证明：
若ak<=ai<aj，那末min(ak,ai)和min(ak,aj)都不变
若ai<aj<=ak，那末min(ai,ak)+min(aj,ak)=ai+aj1定不变
min(ai,ai)+min(aj,aj)=ai+aj也不变
只有min(ai,aj)增大了
因此终究当所有的ai都相同时目标函数最大
故每一个ai都等于k/n，这1步的终究时间复杂度是O(k/n*n^2)=O(kn)
k=10W，n=200，明显不会T
现在的问题就是给定1张图求源点动身走m条边的最短路
倍增Floyd便可
终究时间复杂度O(kn+n^3logn)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 220
#define BASE 131
#define MOD 999911657
using namespace std;
int n,m,len[M];
char str[101000],*s[M];
long long power[101000],_hash[101000],*hash[M];
long long f[M][M],g[M][M],ans[M][M];
int Get_Hash(long long *hash,int l,int r)
{
int len=r-l+1;
return (hash[r]-hash[l⑴]*power[len]%MOD+MOD)%MOD;
}
int Calculate(int x,int y)//计算x最长的后缀，这个后缀也是y的前缀
{
int i;
for(i=min(len[x],len[y])-(len[y]<=len[x]);~i;i--)
if( Get_Hash(hash[x],len[x]-i,len[x]⑴) == Get_Hash(hash
[y],0,i⑴) )
return i;
return 0;
}
int main()
{
int T,i,j,k;
cin>>n>>m;
int temp=1,max_len=0;
for(i=1;i<=n;i++)
{
scanf("%s",str+temp);
s[i]=str+temp;
hash[i]=_hash+temp;
len[i]=strlen(s[i]);
max_len=max(max_len,len[i]);
++temp+=len[i];
for(j=0;j<len[i];j++)
hash[i][j]=(hash[i][j⑴]*BASE+s[i][j])%MOD;
}
for(power[0]=1,i=1;i<=max_len;i++)
power[i]=power[i⑴]*BASE%MOD;
memset(f,0x3f,sizeof f);
for(i=1;i<=n;i++)
{
f[0][i]=len[i];
for(j=1;j<=n;j++)
f[i][j]=len[j]-Calculate(i,j);
}
memset(ans,0x3f,sizeof ans);
for(i=1;i<=n;i++)
ans[i][i]=0;
for(T=0;(1<<T)<=m;T++)
{
if(T)
{
memset(g,0x3f,sizeof g);
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
g[i][j]=min(g[i][j],f[i][k]+f
[k][j]);
memcpy(f,g,sizeof f);
}
if(m&(1<<T) )
{
memset(g,0x3f,sizeof g);
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
g[i][j]=min(g[i][j],f[i][k]
+ans[k][j]);
memcpy(ans,g,sizeof ans);
}
}
long long ans=0x3f3f3f3f3f3f3f3fll;
for(i=1;i<=n;i++)
ans=min(ans,::ans[0][i]);
cout<<ans<<endl;
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
