BZOJ 2085 Poi2010 Hamsters Hash+倍增Floyd
來源：程序員人生 發布時間：2015-04-02 08:17:46 閱讀次數：3623次
題目大意：給定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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
