Codeforces 1082B Vova and Trophies（前缀+后缀）

题意：给定长度为n的字符串s，字符串中只有G和S，只允许最多一次操作：任意位置的两个字符互换。求连续G的最长长度。

题解：维护pre和pr，nxt和nx。pre和nxt像连续子段和一样维护G的个数，pr和nx维护分别前面和后面各有多少个G。

遍历每个位置i，pre[i-1]+nxt[i+1]，判断当前位置i能不能用多余的G来替换，pr和nx判断一下是否与pre和nxt相同即可，过程中更新答案。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 
 5 const int N=2e5+10;
 6 typedef long long ll;
 7 
 8 char s[N];
 9 ll pr[N],nx[N];
10 ll pre[N],nxt[N];
11 
12 int main(){
13     int n;
14     ll ans=0;
15     scanf("%d%s",&n,s+1);
16     for(int i=1;i<=n;i++){
17         pr[i]=pr[i-1];
18         if(s[i]=='G') pre[i]=pre[i-1]+1,pr[i]++;
19         else pre[i]=0;
20     }
21     for(int i=n;i>=1;i--){
22         nx[i]=nx[i+1];
23         if(s[i]=='G') nxt[i]=nxt[i+1]+1,nx[i]++;
24         else nxt[i]=0;
25     }
26     for(int i=1;i<=n;i++){
27         ll sum=0;
28         sum=pre[i-1]+nxt[i+1];
29         if(s[i]=='G') ans=max(ans,sum+1);
30         else{
31             if(pr[i-1]!=pre[i-1]||nx[i+1]!=nxt[i+1]) sum++;
32             ans=max(ans,sum);
33         }
34     }
35     printf("%lld
",ans);
36     return 0;
37 }

View Code