a题解

红太狼 2023-06-01 15:54 26阅读 0赞

### \\(a\\)题解 ###

题目描述

![nQD7DS.png][]

首先考虑\\(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\n",ans); getchar();getchar(); return 0; }

转载于:https://www.cnblogs.com/last-diary/p/11479150.html

[nQD7DS.png]: /images/20230601/12a3a93a723941e09b9d23d3889a6e3a.png