题解：P12690 [KOI 2022 Round 1] ABBC

· · 题解

传送门

hack

我的代码就是这样挂的。

BABC
2

思路

貌似是一道贪心。

我们从后向前遍历 s，需要记下如下信息：

如何转移？我们可以分类讨论：

  1. s_i = A \begin{cases} cntAB + 1,cntB - 1 & (cntB \ne 0) \\ cntAB + 1,cntBC - 1,cntC + 1 & (cntB = 0 \text{且} cntBC \ne 0) \\ \text{不操作} & (cntB = 0 \text{且} cntBC = 0) \end{cases}

    容易证明这样更优，因为答案总数不变，我们还会多出一个 C。

  2. s_i = B \begin{cases} cntBC + 1,cntC - 1 & (cntC \ne 0) \\ cntB + 1 & (cntC = 0) \end{cases}
  3. s_i = C \begin{cases} cntC + 1\end{cases}

    答案即为 cntAB + cntBC。

    代码

    
#include<bits/stdc++.h>
#define int long long
#pragma GCC optimize(3)
using namespace std;
const int maxn = 100010;
const int inf = 1e9;
const int hs = 131;// 或 1331
//unsigned long long 
//cout << fixed << setprecision(3)
//cout << setw(5) << 
//continue
signed main(){
// freopen("aabc.in", "r", stdin);
// freopen("aabc.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
cin >> s;
// cout << s.length();
int n = s.length(), ansab = 0, ansbc = 0, b = 0, c = 0;
for(int i = n - 1;i >= 0;i--){
    if(s[i] == 'A'){
        if(b > 0) ansab++, b--;
        else if(ansbc > 0) ansab++, ansbc--, c++;
    }else if(s[i] == 'B'){
        if(c > 0) ansbc++, c--;
        else b++;
    }else c++;
}
cout << ansab + ansbc;
return 0;
}

感谢阅读！