题解：P12690 [KOI 2022 Round 1] ABBC

hack

~~我的代码就是这样挂的~~。

CPP

BABC

CPP

思路

貌似是一道贪心。

我们从后向前遍历

s

，需要记下如下信息：

$cntB$ ：表示到第 $i$ 位，我们当前可用的 $B$ 的数量；
$cntC$ ：表示到第 $i$ 位，我们当前可用的 $C$ 的数量；
$cntAB$ ：表示到第 $i$ 位，我们已经组好的 $AB$ 数量；
$cntBC$ ：表示到第 $i$ 位，我们已经组好的 $BC$ 数量；

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

$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$ 。
$s_i = B$ $\begin{cases} cntBC + 1,cntC - 1 & (cntC \ne 0) \\ cntB + 1 & (cntC = 0) \end{cases}$
$s_i = C$ $\begin{cases} cntC + 1\end{cases}$ 答案即为 $cntAB + cntBC$ 。

代码

CPP

#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;
}

感谢阅读！

题解：P12690 [KOI 2022 Round 1] ABBC

文章操作

hack

思路

代码

相关推荐

评论

题解：P12690 [KOI 2022 Round 1] ABBC