非官方题解

这道题似乎是春节巅峰赛第五题的削弱版。
这是我巅峰赛的代码：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#define endl "\n"
#define Ll long long
#define true 1
#define false 0
using namespace std;
const int N = 1e5 + 10, M = 1e2 + 10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const Ll mod = 998244353;
Ll T = 1;

int n, cnt_a, cnt_ac, cnt_acg, cnt_acgo;
string s;
void solve ()
{
    //main;
    cin >> n >> s;
    for (int i = 0; i < n; i ++)
    {
        if (s[i] == 'a')
        {
            cnt_a ++;
            cnt_a = cnt_a % mod;
        }else if (s[i] == 'c')
        {
            cnt_ac += cnt_a;
            cnt_ac = cnt_ac % mod;
        }else if (s[i] == 'g')
        {
            cnt_acg += cnt_ac;
            cnt_acg = cnt_acg % mod;
        }else if (s[i] == 'o')
        {
            cnt_acgo += cnt_acg;
            cnt_acgo = cnt_acgo % mod;
        }
    }cout << cnt_acgo % mod << endl;
    return ;
}int main (int argc, const char * argv[])
{
    //main;
    //cin >> T;
    while (T --)
    {
        solve ();
    }return 0;
}

稍微改一下就成了这道题的标程：（Code：）

#include <bits/stdc++.h>
//#define endl "\n"
#define Ll long long
#define true 1
#define false 0
//using namespace std;
const int N = 2e5 + 10, M = 1e2 + 10;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
Ll T = 1;

std::string s;
void solve ()
{
    //main;
    std::cin >> s;
    int len = s.length ();
    int cnt_k = 0, cnt_m = 0, cnt_p = 0;
    for (int i = 0; i < len; ++ i)
    {
        if (s[i] == 'K') cnt_k ++;
        else if (s[i] == 'M') cnt_m += cnt_k;
        else if (s[i] == 'P') cnt_p += cnt_m;
    }std::cout << cnt_p << std::endl;
    return ;
}int main (int argc, const char * argv[])
{
    //main;
    //cin >> T;
    while (T --)
    {
        solve ();
    }return 0;
}

个人认为这是本次欢乐赛最难的一题。
观察后发现，如果把题目降级为统计“KM”出现的次数，那么只需要用前面“K”出现的次数加上后面“M”的次数就是答案。

而如果加上“P”，那么cnt_KMP等于cnt_KM加上“P”出现的次数，如下图：