(a)题解
题目描述
首先考虑(60)分暴力，可以对每一个字母用前缀和维护一下。
然后我们可以得到
[ans=max(sum[a][r]-sum[a][l-1])-min(sum[b][r]-sum[b][l-1])
]
我们设(a)字符为(max)，(b)设为(min)
[ans=(sum[a][r]-sum[a][l-1])-(sum[b][r]-sum[b][l-1])
]
化简得
[ans=(sum[a][r]-sum[a][l-1])-(sum[b][r]-sum[b][l-1])
]
[ans=sum[a][r]-sum[b][r]-(sum[a][l-1]-sum[b][l-1])
]
对于字符的枚举，我们发现不用(26^2)去枚举，因为每次加字符只有当前的字符数量变化，所以我们只需要枚举新加的字符就可以了。
我们发现对于(sum[a][l-1]-sum[b][l-1])，我们并不关心(l-1)是什么，我们只关心它们的差值的最小值，所以我们用(minn[a][b])表示(a)和(b)差值的最小值。
对于(sum[a][r])和(sum[b][r]),因为(r)是当前枚举的，所以我们直接用(sum[a])和(sum[b])来代替。
所以
[ans=max(ans,sum[a]-sum[b]-minn[a][b])
]
因为区间内(a)或者(b)都不能等于(0)，所以我们记录一个(pos[a][b])表示(minnn[a][b])出现的位置，记录一个(last[j])表示(j)这个字符最后出现的位置，如果(pos[a][b]==last[b])证明这段区间里没有(b)，所以我们要新加在(last[b])位置的这个(b)，也就是更新时答案减一。
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100,M=30;
char s[N];
int sum[M],last[M],pos[M][M],minn[M][M];
int n,ans=0;
int main()
{
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
scanf("%d",&n);
scanf("%s",s+1);
for (int i=1;i<=n;i++)
{
int now=s[i]-'a'+1;
last[now]=i;
sum[now]++;
for (int j=1;j<=26;j++)
{
int tmp;
if (sum[j]&&now!=j)
{
tmp=sum[now]-sum[j]-minn[now][j];
if (pos[now][j]==last[j]) tmp--;
ans=max(ans,tmp);
tmp=sum[j]-sum[now]-minn[j][now];
if (pos[j][now]==last[j]) tmp--;
ans=max(ans,tmp);
}
}
for (int j=1;j<=26;j++)
{
if (sum[now]-sum[j]<minn[now][j])
{
minn[now][j]=sum[now]-sum[j];
pos[now][j]=i;
}
if (sum[j]-sum[now]<minn[j][now])
{
minn[j][now]=sum[j]-sum[now];
pos[j][now]=i;
}
}
}
printf("%d
",ans);
getchar();getchar();
return 0;
}