CF356E - Xenia and String Problem

也许更好的阅读体验

$Description$Description

定义一种字符串 $gray$gray串满足：

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

一个 $gray$gray串的贡献为这个串长度的平方
需要注意的是一个长度为 $7$7的 $gray$gray串是包含了长度为 $1,3$1,3的 $gray$gray的

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

$Solution$Solution

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

• 根据 $gray$gray串的定义,我们知道一个 $gray$gray串的长度应该是 $1,3,7,15,31\dots (2^x-1)$1,3,7,15,31…(2x−1)
  所以我们最多有 $lo{g}_2\left(n\right)$log2​(n)种长度不同的 $gray$gray串, $n$n最大为 $100,000$100,000也就是说最多有 $16$16种
  所以我们可以考虑求出所有长度的情况

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

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

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

$Code$Code
代码里有折叠,使用vim的朋友可以将其分开看
建议打代码时也分开打

/******************************* 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;
}

如有哪里讲得不是很明白或是有错误，欢迎指正
如您喜欢的话不妨点个赞收藏一下吧
如能得到推荐博主就更开心了
您的鼓励是博主的动力