题目

Solution

以下把B,C,S看作A,B,C

结论一：对于满足条件的最长子段 [ l , r ] [l,r] [l,r]，只有两种情况：①3种字母个数都相差1；② l = 1 l=1 l=1或 r = n r=n r=n

证明：假设最优解的 a &lt; b &lt; c a&lt;b&lt;c a<b<c。首先， c − b c-b c−b和 b − a b-a b−a不可能都大于1,。
若①②不成立，则 b − a &gt; 1 b-a&gt;1 b−a>1或 c − b &gt; 1 c-b&gt;1 c−b>1。
不妨设 b − a &gt; 1 b-a&gt;1 b−a>1，则 c − b = 1 c-b=1 c−b=1
因为②不成立，所以右边的位置不能是 a a a, c c c，只能是 b b b，左边也是这样（不然还能更优）。
此时 a &lt; c &lt; b + 2 a&lt;c&lt;b+2 a<c<b+2，能得到更优解，所以原来的不是最优解

结论二：对于子段 [ l , r ] [l,r] [l,r]，当 l ∈ [ 1 , 3 ] l∈[1,3] l∈[1,3]或 r ∈ [ n − 2 , n ] r∈[n−2,n] r∈[n−2,n]时一定能找到最优解。

证明：假设最优解 3 &lt; l &lt; = r &lt; n − 2 3&lt;l&lt;=r&lt;n-2 3<l<=r<n−2。
左右各扩展三位，使得 l ′ ∈ [ 1 , 3 ] l&#x27;∈[1,3] l′∈[1,3]， r ′ ∈ [ n − 2 , n ] r&#x27;∈[n−2,n] r′∈[n−2,n]，枚举 l ′ l&#x27; l′和 r ′ r&#x27; r′的所有可能情况后，枚举 a , b , c a,b,c a,b,c的相对大小关系，再加上结论一，可以进行判断，最终发现结论成立

Code

#include<bits/stdc++.h> using namespace std; const int N=1000002; char s1[N]; int i,ans,A,B,C,a[N],b[N],c[N],n,j; int main(){ scanf("%d%s",&n,s1+1); for (i=1;i<=n;i++) a[i]=a[i-1]+(s1[i]=='B'),b[i]=b[i-1]+(s1[i]=='C'),c[i]=c[i-1]+(s1[i]=='S'); for (i=1;i<=3;i++) for (j=n;j-i+1>ans;j--){ A=a[j]-a[i-1];B=b[j]-b[i-1];C=c[j]-c[i-1]; if (A!=B && A!=C && B!=C || (!A)+(!B)+(!C)==2){ ans=j-i+1; break; } } for (j=n-2;j<=n;j++) for (i=1;j-i+1>ans;i++){ A=a[j]-a[i-1];B=b[j]-b[i-1];C=c[j]-c[i-1]; if (A!=B && A!=C && B!=C || (!A)+(!B)+(!C)==2){ ans=j-i+1; break; } } printf("%d",ans); }