\(\mathcal{Description}\)

定义一种字符串\(gray\)串满足：

• 长度为奇数
• 正中间的字母只出现一次
• 左右两端相同，左右两端也是gray串

一个\(gray\)串的贡献为这个串长度的平方

需要注意的是一个长度为\(7\)的\(gray\)串是包含了长度为\(1,3\)的\(gray\)的

现给你一个长为\(n(n<=100,000)\)的字符串，你可以修改至多一个字母，使得总贡献值最大

输入方式为一个字符串

\(\mathcal{Solution}\)

• 考虑怎么去求修改字符的贡献

  我们修改一个字符时应该考虑两点:
  一是该字符原本造成的贡献没有了
  二是将其修改后会得到新的贡献
  当我们对第\(i\)个字符修改时
  用\(cost[i]\)表示\(i\)位置原本的贡献
  用\(bef[i][x](benefit)\)表示将\(i\)位置的字符修改为\(x\)所得到的贡献,特别的,设i位置本来的字符为\(x\),那么\(cost[i]=bef[i][x]\)
  那么将\(i\)位置的字符修改为\(x\)得到的贡献应为\(bef[i][x]-cost[i]\)

• 根据\(gray\)串的定义,我们知道一个\(gray\)串的长度应该是\(1,3,7,15,31\dots(2^x-1)\)

  所以我们最多有\(log_2(n)\)种长度不同的\(gray\)串,\(n\)最大为\(100,000\)也就是说最多有\(16\)种
  所以我们可以考虑求出所有长度的情况

• 求\(cost\)

  \(cost[i]\)表示的是\(i\)位置的字符原本的贡献,其包含了不同长度的贡献
  一个长度为\(n\)的\(gray\)串所有位置的贡献应该都是\(n*n\)
  考虑差分,找出所有不同长度的\(gray\)串,在其开头贡献加上\(n*n\),在其末尾加一的位置减去\(n*n\)

• 如何判断原串中一个串是否为\(gray\)串(过水可跳过)

  先将原串哈希一遍
  用\(pef[i][j]\)表示以\(i\)为开头,长度为\(2^j-1\)的串是否为\(gray\)串 \((\)我喜欢叫它完美串\(pef \Rightarrow perfect)\)
  用\(sum[i][j]\)表示字符\(i\)在前\(j\)个字符中出现了多少次
  设一个长度为\(2^i-1\)的串左端点为\(l\),中点为\(mid\),右端点为\(r\),中点字符为\(ch\),字符串的哈希值为\(sub\)
  则应满足以下条件
  \(sum[ch][r]-sum[ch][l-1]==1\)
  \(pef[l][i-1]=true\)
  \(pef[mid+1][i-1]=true\)
  \(sub(l,mid-1)==sub(mid+1,r)\)

• 求\(bef\)

  枚举所有长度以及其起点
  考虑将其变为\(gray\)串
  此时对于一个串有两种情况
  一是左半边与右半边都是\(gray\)串,但是中间的字符有重复,枚举将中间的字符修改为什么字符即可
  二是左半边与右半边有一个为\(gray\)串,此时两串不相同的字符应只有一个并且中间的字符应不会重复
  这一段的打法并没有特殊技巧,注意处理方法即可,细节看代码,思路很清晰

\(\mathcal{Code}\)

代码里有折叠,使用vim的朋友可以将其分开看

建议打代码时也分开打

/*******************************Author:Morning_GloryLANG:C++Created Time:2019年07月19日 星期五 20时41分51秒*******************************/#include 
    
     #include 
     
      #include 
      
       #define ll long long#define ull unsigned long longusing namespace std;const int maxn = 100050;const int limit = 16;const int h = 31;int n;int len[maxn];ll ans,inc;ll cost[maxn];ll bef[maxn][30];ull ha[maxn],mi[maxn];int sum[30][maxn];char s[maxn];bool pef[maxn][limit+5];//{
    {
    {subinline ull sub (int l,int r){       return ha[r]-ha[l-1]*mi[r-l+1];}//}}}//{
    {
    {checkinline bool check (int l1,int r1,int l2,int r2){    return sub(l1,r1)==sub(l2,r2);}//}}}//{
    {
    {lcpinline int lcp (int l1,int l2){    int res=0;    for (int i=limit;i>=0;--i){        int le=res+len[i];        if (l1+le<=n&&l2+le<=n&&check(l1,l1+le,l2,l2+le))   res+=len[i]+1;    }    return res;}//}}}//{
    {
    {initinline void init (){    for (int i=1;i<=limit+1;++i)    len[i]=len[i-1]<<1|1;    mi[0]=1,ans=n=strlen(s+1);    for (int i=1;i<=n;++i){        for (int j=1;j<=26;++j)            sum[j][i]=sum[j][i-1]+(s[i]-'a'+1==j);        pef[i][1]=true,mi[i]=mi[i-1]*h;        ha[i]=ha[i-1]*h+s[i]-'a'+1;    }}//}}}//{
    {
    {get_pefinline void get_pef(){    for (int i=2;len[i]<=n;++i)        for (int l=1,r=len[i];r<=n;++l,++r){            int mid=l+len[i-1],ch=s[mid]-'a'+1;            if (sum[ch][r]-sum[ch][l-1]==1) pef[l][i]=pef[l][i-1]&pef[mid+1][i-1]&check(l,mid-1,mid+1,r);            ans+=1ll*pef[l][i]*len[i]*len[i];        }}//}}}//{
    {
    {get_costinline void get_cost (){    for (int i=1;len[i]<=n;++i)        for (int l=1,r=len[i];r<=n;++l,++r){            cost[l]+=1ll*pef[l][i]*len[i]*len[i];            cost[r+1]-=1ll*pef[l][i]*len[i]*len[i];        }    for (int i=1;i<=n;++i)  cost[i]+=cost[i-1];}//}}}//{
    {
    {calcinline void calc (int l1,int k)// from l1   len[k]{    if (k==1){        for (int i=1;i<=26;++i) ++bef[l1][i];        return;    }    int mid=l1+len[k-1],l2=mid+1;    ll tmp=1ll*len[k]*len[k];    if (pef[l1][k-1]&&pef[l2][k-1]&&check(l1,mid-1,l2,l2+len[k-1]-1)){        for (int i=1;i<=26;++i)            if (sum[i][l1-1]==sum[i][mid-1])    bef[mid][i]+=tmp;        return;    }    int prf1=lcp(l1,l2);    int m1=l1+prf1,m2=l2+prf1;    int prf2=lcp(m1+1,m2+1);    if (m1+1+prf2
       
        >(s+1);    init();    get_pef();    get_cost();    for (int i=1;i<=n;++i)        for (int j=1;i+len[j]-1<=n;++j)            calc(i,j);    for (int i=1;i<=n;++i)        for (int j=1;j<=26;++j)             inc=max(inc,bef[i][j]-cost[i]);    cout<
        
         <
        
       
      
     
    

如有哪里讲得不是很明白或是有错误，欢迎指正

如您喜欢的话不妨点个赞收藏一下吧

如能得到推荐博主就更开心了

您的鼓励是博主的动力