题解 | 小苯的ovo2.0

先全部改成o，然后二重循环枚举一个范围，将此范围改成v，然后计算取最大值

同时可以在上一个答案大于本次计算答案时，退出循环

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

long long compute(const string& s, int n, int total_v) {
    int cnt_v = 0, cnt_o = 0;
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'o') {
            cnt_o++;
        } else { 
            ans += 1LL * cnt_o * (n - cnt_o - total_v);
        }
    }
    return ans;
}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> idx_candidate;

    for (int i = 0; i < n; i++) {
        if (s[i] == '?') {
            s[i] = 'o';
            idx_candidate.push_back(i);
        }
    }
    
    int m = idx_candidate.size();
    
    int total_v = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'v') total_v++;
    }
    
    long long ans = compute(s, n, total_v);
    
    for (int i = 0; i < m; i++) {
        int j;
        int prev_ans=-1;
        for (j = i; j < m; j++) {
            s[idx_candidate[j]] = 'v';
            total_v++; 
            long long cur_ans = compute(s, n, total_v);
            //cout<<i<<" "<<cur_ans<<endl;
            ans=max(ans,cur_ans);
            if (cur_ans < prev_ans) {
                break;
            }
            prev_ans=cur_ans;
        }
        for (int k = i; k < m; k++) {
            if (s[idx_candidate[k]]=='v'){
                s[idx_candidate[k]] = 'o';
                total_v--;
            }else{
                break;
            }
        }
    }
    
    cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}

import sys
input=lambda :sys.stdin.readline()[:-1]
max_n=lambda x,y:x if x>y else y
inf=float('inf')


def solve():
    s=list(input())
    n=len(s)
    def compute(s):
        cnt_v=s.count("v")
        cnt_o=0
        ans=0
        for c in s:
            if c=="o":
                cnt_o+=1
            else:
                ans+=cnt_o*(n-cnt_o-cnt_v)
        return ans
    idx_candidate=[]
    for i,c in enumerate(s):
        if c=="?":
            s[i]="o"
            idx_candidate.append(i)
    ans=compute(s)
    idx_candidate_n=len(idx_candidate)
    for i in range(idx_candidate_n):
        for j in range(i,idx_candidate_n):
            s[idx_candidate[j]]="v"
            ans=max_n(ans,compute(s))
        for j in range(i,idx_candidate_n):
            s[idx_candidate[j]]="o"
    print(ans)
    
for _ in range(int(input())):
    solve()