题解 CF356E 【Xenia and String Problem】
Morning_Glory
2019-07-20 16:49:53
[也许更好的阅读体验](https://www.cnblogs.com/Morning-Glory/p/11218174.html)
# $\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的朋友可以将其分开看
建议打代码时也分开打
```cpp
/*******************************
Author:Morning_Glory
LANG:C++
Created Time:2019年07月19日 星期五 20时41分51秒
*******************************/
#include <iostream>
#include <fstream>
#include <cstring>
#define ll long long
#define ull unsigned long long
using 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];
//{{{sub
inline ull sub (int l,int r)
{
return ha[r]-ha[l-1]*mi[r-l+1];
}
//}}}
//{{{check
inline bool check (int l1,int r1,int l2,int r2)
{
return sub(l1,r1)==sub(l2,r2);
}
//}}}
//{{{lcp
inline 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;
}
//}}}
//{{{init
inline 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_pef
inline 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_cost
inline 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];
}
//}}}
//{{{calc
inline 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<mid) return;
if (pef[l1][k-1]&&sum[s[mid]-'a'+1][l1-1]==sum[s[mid]-'a'+1][mid-1]) bef[m2][s[m1]-'a'+1]+=tmp;
if (pef[l2][k-1]&&sum[s[mid]-'a'+1][mid]==sum[s[mid]-'a'+1][l2+len[k-1]-1]) bef[m1][s[m2]-'a'+1]+=tmp;
}
//}}}
int main()
{
freopen("356E.in","r",stdin);
freopen("356E.out","w",stdout);
ios::sync_with_stdio(false);
cin>>(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<<ans+inc<<endl;
return 0;
}
```