CF356E - Xenia and String Problem

比眉伴天荒 2021-11-16 08:20 114阅读 0赞

[也许更好的阅读体验][Link 1]

\\(\\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_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; }

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

转载于:https://www.cnblogs.com/Morning-Glory/p/11218174.html

[Link 1]: https://blog.csdn.net/Morning_Glory_JR/article/details/96595009