题解 | 小美的01串翻转

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string s;cin>>s;
    int n = s.size();
    int ans = 0;
    
    //模式串(有两种，但另一种可计算得到)
    string t = s;
    for(int i = 0;i < n;++i){
        if(i & 1) t[i] = '0';
        else t[i] = '1';
    }
    
    //前缀和数组统计0到i变为模式串所需次数
    vector<int> a(n + 1);
    for(int i = 1;i <= n;++i){
        a[i] = s[i - 1]==t[i - 1] ? 0 : 1;
        a[i] += a[i-1];
    }
    
    for(int i = 0;i < n;++i){
        for(int j = i;j < n;++j){
            string t = s.substr(i, j - i + 1);

            // 两种模式串次数和为串长度，通过做差求出另一种，累加较小值
            ans += min(a[j + 1] - a[i], (j - i + 1) - (a[j + 1] - a[i]));
        }
    }
    cout<<ans<<endl;
}
// 64 位输出请用 printf("%lld")