加载中…
个人资料
lch1475369
lch1475369
  • 博客等级:
  • 博客积分:0
  • 博客访问:56,395
  • 关注人气:28
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

2011.12.23

(2011-12-23 18:50:36)
标签:

杂谈

计划:
看 DengklekMessage 解答,后总结为何想不到方法

topcoder SRM 526 DengklekMessage
  题目大意,给出匹配串good,和n个字符串片段piece[],现从 n 个片段中取出 k 个,首尾相接得到一个新字符串 S,定义 S 与 good 的匹配数为 S 的价值 val;一共可以生成 n^k 个这样的 S,问它们的val的平均值是多少。( |good|=500  n=50  k=10^12 )
  
  由于k很大,所以我首先想到的是倍增,在递推的过程中由于要计算新增加的匹配,所以还要记录与good相匹配的最长前缀后缀长度,f(i,j1,j2)表示用了2^j个片段,与good匹配的最长前后缀长度为j1,j2的val
    f(i+1,j1,j4)=f(i,j1,j2)+f(i,j3,j4)+g(j2,j3)
  如图直观一点:
2011.12.23
  但这个方法很明显是不行的,因为j1、j2的枚举量比较大,会超时;后来我还想了另外一些方法,但因为k实在很大,都离不开倍增。

正确方法:
2011.12.23
   如图,一共可得到n^k个不同字符串(用不同横线表示),每个字符串与good的匹配数为G[i],于是ans=∑G[i]/n^k;设F[i]表示n^k在加入第i个片段时新增加的good匹配,显然有∑F[i]=∑G[i],于是有ans=∑F[i]/n^k.
   定义S与good的相接长度为最大的j,满足S长为j的后缀与good长为j的前缀相匹配
   设f[i]=F[i]/n^k,g(i,j)为选取i个片段后得到S与good相接长度为j的概率,match(j,p)为good的长为j的前缀与piece[p]相接后得到的字符串与good的匹配数,L=|good|,则显然有:
     F[i]=∑(j=0..L-1)∑(p=1..n) g(i-1,j)/n*n^k*match(j,p)
   于是有:
     f[i]=∑(j=0..L-1)∑(p=1..n) g(i-1,j)/n*match(j,p)
     ans=∑(i=1..k) f[i]
   现在问题在于如何求f[i]。

   我们知道,求f(i)时依赖于前i-1个片段的相接长度j(j<=L),故只需考虑 i 前的L个片段的选择即可。我们来看 f(L+1) 和 f(L+2) 的选取:
2011.12.23

  f(L+1)依赖于片段1..L,f(L+2)依赖于片段2..L+1,在一般的DP中我们经常这样分析得出f(L+1)和f(L+2)的关系,在这里也一样:1..L是任意取的,一共能生成n^L个不同的 S,在 S 后加上 piece[p] 得到f(L+1);同理2..L+1也是任意的,生成n^L个S也是一样的,所以说f(L+2)理应等于f(L+1)。
   同理得:f(L+1)=f(L+2)=...=f(k),于是上面的式子可以写成 ans=∑(i=1..L) f(i) + f(L+1)*(k-L).
   
   至于match(j,p)可以用kmp匹配一下就出来了,g(i,j)也可以用简单的递推得到:
     g(i+1,nexj[j,p])+=g(i,j)/n

总结:
   为什么会想不到?
   主要是因为过于紧盯着大数字K,一直在考虑倍增算法,总是把每个字符串横着来看(G[i]),而没有想到把n^k个字符串看做一个整体,竖着看(F[i]);
   这道题为我们提供新的思路,当数据规模大的时候,不一定要用O(logn)级的方法降低时间,有的时候换个角度想(局部与整体,纵向与横向),可以得到一些新的东西(周期性),从而降低时间,甚至到O(1)级的。

程序如下:
const int maxn=50+5, maxl=500+10;
string good;
double ans,g[maxl][maxl],f[maxl];
int n,L,match[maxl][maxn],nextj[maxl][maxn],next[maxl];

class DengklekMessage
              
              public: 
                      
              void calc_next()
              {
                   int k;
                   next[0]=k=-1;
                   for (int i=1; i<L; i++)
                   {
                       while (k!=-1 && good[i]!=good[k+1]) k=next[k];
                       if (good[i]==good[k+1]) k++;
                       next[i]=k;
                   }
              }
                      
              double theExpected(vector <string> pieces, vector <string> goodSub, long long K) 
                  
                    memset(f,0,sizeof(f));
                    memset(g,0,sizeof(g));
                    memset(match,0,sizeof(match));
                    memset(nextj,0,sizeof(nextj));
                    
                    good="";
                    for (int i=0; i<goodSub.size(); i++)
                     good=good+goodSub[i];
                    n=pieces.size(), L=good.size();
                    
                    calc_next();
                    for (int i=0; i<L; i++)
                    {
                        string s0=good.substr(0,i),s;
                        for (int j=0; j<n; j++)
                        {
                            match[i][j]=0;
                            s=s0+pieces[j];
                            int k=-1;
                            for (int p=0; p<s.size(); p++)
                            {
                                while (k!=-1 && s[p]!=good[k+1]) k=next[k];
                                if (s[p]==good[k+1]) k++;
                                if (k==L-1) 
                                {
                                   match[i][j]++; k=next[k];
                                }
                            }
                            nextj[i][j]=k+1;
                        }
                    }
                    
                    g[0][0]=1;
                    for (int i=0; i<=L; i++)
                    {
                        f[i+1]=0;
                        for (int j=0; j<L; j++)
                         if (g[i][j]>0)
                          for (int k=0; k<n; k++)
                          {
                              g[i+1][nextj[j][k]]=g[i+1][nextj[j][k]]+g[i][j]/n;
                              f[i+1]=f[i+1]+g[i][j]*match[j][k]/n;
                          }
                    }
                    
                    ans=0;
                    for (int i=1; i<=min(K,(long long)L); i++) ans+=f[i];
                    if (K-L>0) ans=ans+f[L+1]*(K-L);
                    return ans;
                  
   
   

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
前一篇:划分树
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

    < 前一篇划分树
      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有