【经典dp】hdu4622Reincarnation

呕卡64M内存卡了好久

题目描述

题目大意

给出一个字符串 S，每次询问一个区间的本质不同的子串个数。$|S| \le 2000$.

题目分析

首先无脑$n^2$个set开起来：MLE

稍微想想这个东西是能够区间dp的：对于一个字符串$[l,r]$，它的存在首先给所有包含$[l,r]$的$f[i][j]$贡献$1$；考虑相同的字符串下一次出现的位置$[l',r']$，那么对所有包含$[l,r']$的$f[i][j]$贡献$-1$。最后再按照顺序累加一下即可。

第一次：std::map存一个哈希值上一次出现的位置，MLE

第二次：手写哈希表，$\mod 8000007$挂链，MLE

第三次：手写哈希表，$\mod 5000007$挂链，MLE

第四次：手写哈希表，$\mod 10007$挂链，TLE？

第五次：手写哈希表，$\mod 500007$挂链、查询时候顺带后续修改，MLE？？？

嗯？这啥玩意？

啧。后来意识到枚举不同长度的时候，哈希表里历史记录值都是没用的。所以每次枚举长度都应该重置哈希表。而且这样一来，哈希表模数和空间就可以开小了。

还听说这个经典问题有一个$O(n)$做法？

网上找了一下只有两个类似的是：

1.loj#6070. 「2017 山东一轮集训 Day4」基因　　强制在线询问$s[l\cdots r]$中有多少本质不同的回文子串 $n\le 10^5,q\le 2\times10^5$

2.「湖南省队集训2018 Day2」有趣的字符串题　　每个询问会询问一段区间的本质不同回文子串个数 $n\le 3\times 10^5,m\le 10^6$

不过这两个题都要用到回文子串的性质：“一个串的所有回文后缀可以被划分成不超过log个等差数列”。所以网上尚没有找到这个问题的$O(n)$解法？

 #include<bits/stdc++.h>

 typedef unsigned long long uint;

 const int maxn = ;

 const int maxp = ;

 uint base = ;

 struct node

 {

     uint num;

     int val;

     node(uint a=, int b=):num(a),val(b) {}

 }edges[maxp];

 struct Hash_Table

 {

     #define MO 10007

     int head[],nxt[maxp],edgeTot;

     void init(){edgeTot=,memset(head, -, sizeof head);}

     int query(uint x, int c)

     {

         for (int i=head[x%MO]; i!=-; i=nxt[i])

             if (edges[i].num==x){

                 std::swap(c, edges[i].val);

                 return c;

             }

         edges[++edgeTot] = node(x, c), nxt[edgeTot] = head[x%MO], head[x%MO] = edgeTot;

         return ;

     }

     #undef MO

 }g;

 int T,n,q,l,r;

 char s[maxn];

 int f[maxn][maxn];

 uint pwr[maxn],hsh[maxn],val;

 uint hash(int l, int r)

 {

     return hsh[r]-hsh[l-]*pwr[r-l+];

 }

 int main()

 {

 //    freopen("hdu4622.in","r",stdin);

 //    freopen("hdu4622.out","w",stdout);

     pwr[] = ;

     for (int i=; i<=; i++)

         pwr[i] = pwr[i-]*base;

     for (scanf("%d",&T); T; --T)

     {

         scanf("%s",s+);

         n = strlen(s+);

         for (int i=; i<=n; i++) hsh[i] = hsh[i-]*base+s[i]-'a'+;

         for (int i=; i<=n; i++)

             for (int j=i; j<=n; j++) f[i][j] = ;

         for (int d=; d<=n; d++)

         {

             g.init();

             for (int i=,pos; i+d-<=n; i++)

             {

                 val = hash(i, i+d-), pos = g.query(val, i);

                 if (pos) --f[pos][i+d-];

                 ++f[i][i+d-];

             }

         }

         for (int i=n; i>=; i--)

             for (int j=i; j<=n; j++)

                 f[i][j] += f[i+][j]+f[i][j-]-f[i+][j-];

         for (scanf("%d",&q); q; --q)

             scanf("%d%d",&l,&r), printf("%d\n",f[l][r]);

     }

     return ;

 }

END

巴特西

【经典dp】hdu4622Reincarnation

题目描述

题目大意

题目分析

最新文章

热门文章