首页 > 代码库 > [poi2010]Hamsters

[poi2010]Hamsters

2024-08-01 19:36:59   228人阅读

题意：Tz养了一群仓鼠，他们都有英文小写的名字，现在Tz想用一个字母序列来表示他们的名字，只要他们的名字是字母序列中的一个子串就算，出现多次可以重复计算。现在Tz想好了要出现多少个名字，请你求出最短的字母序列的长度是多少。(n <= 200,  m <= 1e9)

思路：首先可以处理出g[a][b]表示b接在a后面的长度(即重复部分之前都不算)

         那么就可以转化成求长度m-1的最短路。

         假设dis[i][a][b]为经过i步a走到b的最短路，那么dis[i][a][b] = min(dis[i/2][a][c] + dis[i-i/2][c][b]) (1<=c<=n)

         那么是不是就可以利用快速幂的思想了。。

         前面求g[a][b]可利用hash判断是否一样

code：

 1 /* 2  * Author:  Yzcstc 3  * Created Time:  2014/11/12 20:54:48 4  * File Name: hamsters.cpp 5  */ 6 #include<cstdio> 7 #include<iostream> 8 #include<cstring> 9 #include<cstdlib>10 #include<cmath>11 #include<algorithm>12 #include<string>13 #include<map>14 #include<set>15 #include<vector>16 #include<queue>17 #include<stack>18 #include<ctime>19 #define M0(x)  memset(x, 0, sizeof(x))20 #define repf(i, a, b) for (int i = (a); i <= (b); ++i)21 #define Inf  0x7fffffff22 #define M 1000723 using namespace std;24 typedef long long ll;25 const int maxn = 204;26 int n, m;27 char str[120000];28 vector<int> hs[210];29 int sz[maxn], pw[120000];30 ll A[maxn][maxn], B[maxn][maxn];31 ll s[maxn], tmp[maxn];32 33 inline int Hash(const int &p, const int& l, const int& r){34        return hs[p][r] - hs[p][l-1] * pw[r-l+1];35 }36 37 void init(){38      int len, v;39      repf(i, 1, n){40            scanf("%s", str + 1);41            sz[i] = len = strlen(str + 1);42            hs[i].push_back(v = 0);43            repf(j, 1, len) 44                 v = v * M + str[j], hs[i].push_back(v);45      }46 }47 48 void modify(ll *s, ll A[][maxn]){49      memset(tmp, 0x3f, sizeof(tmp));50 //     cout << tmp[0] << endl;51      for (int i = 1; i <= n; ++i)52             for (int j = 1; j <= n; ++j)53                    tmp[j] = min(tmp[j], s[i] + A[i][j]);54      repf(i, 1, n) s[i] = tmp[i];55 }56 57 void modify(ll A[][maxn]){58      memset(B, 0x3f, sizeof(B));59      repf(k, 1, n) repf(i, 1, n) repf(j, 1, n)60            B[i][j] = min(B[i][j], A[i][k] + A[k][j]); 61      repf(i, 1, n) repf(j, 1, n) A[i][j] = B[i][j];    62 }63 64 void quick(int n){65      for (;n>0; n>>=1){66            if (n & 1) modify(s, A);67            modify(A);68      }    69 }70 71 void solve(){72      repf(i, 1, n) repf(j, 1, n){73            A[i][j] = sz[j];  74            for (int k = max(2, sz[i]-sz[j]+2); k <= sz[i]; ++k)75                 if (Hash(i, k, sz[i]) == Hash(j, 1, sz[i]-k+1)){76                       A[i][j] = sz[j] - (sz[i]-k+1);  break;77                 }78      }79      repf(i, 1, n) s[i] = sz[i];80      quick(--m);81      ll ans = 1LL<<62;82 //     cout << ans << endl;83      repf(i, 1, n) ans = min(ans, s[i]);84      cout << ans << endl;85 } 86 87 int main(){88     pw[0] = 1;89     repf(i, 1, 100000) pw[i] = pw[i-1] * M; 90     while (scanf("%d%d", &n, &m) != EOF){91         init();92         solve();93     }94     return 0;95 }
View Code

 

[poi2010]Hamsters


联系
我们