NC214517. 字符串魔法(hard)
描述
白浅获得了一个仅由A和B组成的字符串。他可以至多使用一次魔法来改变字符串。
魔法：选择一个子串，满足子串中 A 的数量等于 B 的数量，然后按字典序从小到大排序这个子串，即变成形如AAA...AAABBB...BBB这样的字符串(A和B的数量均与原来的子串相同)。
他想知道，在他至多使用一次魔法后，这个字符串能够出现的最长的字典序不递减的子串的长度为多少。
输入描述
第一行包含一个整数n，代表字符串的长度。
接下来一行给出一个长度为n的字符串。
输出描述
输出一行一个正整数表示答案。
示例1
输入:
6 AABBAA
输出:
6
说明:
选择”BBAA”的子串，这个子串 A 和 B 的出现次数相等，满足要求。使用魔法变成AABB，则整个字符串变为AAAABB，所以最长不递减子串长度为6。
C++(clang++11) 解法, 执行用时: 17ms, 内存消耗: 3008K, 提交时间: 2021-01-22 21:23:20
#include<bits/stdc++.h>
using namespace std;
const int N=222222;
char s[N];
int n,a[N],l[N],r[N],f[N*2];
int main()
{
int i,j,x;
scanf("%d%s",&n,s+1);
for(i=1;i<=n;i=i+1)
{
if(s[i]=='A')
a[i]=a[i-1]+1;
else
a[i]=a[i-1]-1;
}
for(i=1;i<=n;i=i+1)
{
if(s[i]=='A')
l[i]=l[i-1]+1;
else
l[i]=0;
}
for(i=n;i>=1;i=i-1)
{
if(s[i]=='B')
r[i]=r[i+1]+1;
else
r[i]=0;
}
for(i=1;i<=n;i=i+1)
f[a[i]+N]=i;
x=0;
for(i=0;i<=n;i=i+1)
{
j=f[a[i]+N];
x=max(x,j-i+l[i]+r[j+1]);
}
cout<<x;
return 0;
}