题解思路

本人采用的方法是dp，递推，看了下目前题解还没有出现这种做法
于是发出来自己的思路

首先
根据乘法原理可以得到：
O前面C的数量 * O后面W的数量 = 这个O可以构成的“COW”子串数量

测试数据中当然不止有1个O，所以要把所有的O构成的子串数量相加

我们定义一个dp[N][2]数组，
其中dp[i][0]表示字符串的前i位中的‘C’的数量
dp[i][1]表示字符串的前i位中的‘W’的数量

而对于字符串的某一位i：

如果它是‘C’，那么状态转移方程为dp[i][0] = dp[i - 1][0] + 1;
                           dp[i][1] = dp[i - 1][1];
如果它是‘W’，那么状态转移方程为dp[i][0] = dp[i - 1][0];
                           dp[i][1] = dp[i - 1][1] + 1;
如果它是‘O’，那么状态转移方程为dp[i][0] = dp[i - 1][0];
                           dp[i][1] = dp[i - 1][1];

TIPS:一定要提前初始化dp[0][0],dp[0][1];

如果第i位是‘O’，那么它前面的‘C’的数量就是dp[i][0]
它后面的‘W’数量可以间接地通过dp[n - 1][1] - dp[i][1]得出
最后根据乘法原理答案dp[i][0] * (dp[n - 1][1] - dp[i][1])
注意有多个O,所以最后要相加

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int n;
int dp[N][2];
string s;

int main()
{
    cin >> n >> s;

    // 为了后面的递推，需要提前初始化dp[0][0]
    if(s[0] == 'C') dp[0][0] = 1, dp[0][1] = 0;
    else if(s[0] == 'O') dp[0][0] = 0, dp[0][1] = 0;
    else dp[0][0] = 0, dp[0][1] = 1;

    for (int i = 1; i < n; i++)
    {
        if (s[i] == 'C')
        {
            dp[i][0] = dp[i - 1][0] + 1;
            dp[i][1] = dp[i - 1][1];
        }
        else if(s[i] == 'W')
        {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = dp[i - 1][1] + 1;
        }
        else 
        {
            dp[i][0] = dp[i - 1][0];
            dp[i][1] = dp[i - 1][1];
        }
    }

    long long sum = 0； //会爆int，一定要开long long
    for(int i = 0; i < n; i++)
        if(s[i] == 'O') 
            sum += (long long)dp[i][0] * (dp[n - 1][1] - dp[i][1]);

    cout << sum;
    return 0;
}