题解 | #子序列#

牛客IOI周赛26-普及组T2

作者：Feecle6418
链接：https://ac.nowcoder.com/discuss/669017?type=101&order=0&pos=7&page=1&channel=-1&source_id=1
来源：牛客网

结论：最优解要么是最左边插入一个 a，要么是最右边插入一个 b。枚举两种情况，判断即可。具体判断时，记录前面有几个 a，遇到一个 b 就加上 (a 的个数)*(a 的个数-1)/2。

需要开 unsigned long long。

#include<bits/stdc++.h>
using namespace std;
char a[550000];
long long len;
int main(){
    cin >> (a + 1);
    len = strlen(a + 1);
    long long ans = 0,sum = 0,maxn = 0,ct = 0;
    a[0] = 'a';
    a[len + 1] = 'b';
    for(int i = 0;i <= len;i++){
        if(a[i] == 'a') ans++;
        else if(a[i] == 'b') sum += (ans - 1) * ans / 2; 
    }
    for(int i = 1;i <= len + 1;i++){
        if(a[i] == 'a') ct++;
        if(a[i] == 'b') maxn += (ct - 1) * ct / 2; 
    }
    cout << max(maxn,sum) << endl;
    return 0;
}