奶牛碑文

奶牛碑文

奶牛碑文题目链接

以下是题目图片:

在这个题目中,我们应该要考虑这样几种情况:

1. WOC: C后面没有字母,这种情况下,答案应当为0
2. WCOCOW: C出现在了O或者W的后面
3. WO: 字母不全

这类问题与括号配对问题不同(力扣:有效的括号),本题有三个需要配对的元素,因此,这里建议使用轴的思想来处理这道题
例如:

以O为轴,统计O左边的C的个数,然后再统计O右边的个数,然后将所求到的个数相乘并赋值给O,对每个O都执行同样的操作后,统计每个O的赋值,并且求和,便可以得到正确答案,这种做法时间复杂度为O(n^2^),并且利用代码来实现可能比较复杂,因此,我们需要更简单的方法

我们通过一次遍历,统计在O左边的C的个数,并赋值给O,统计在W左边O上赋值的总和,然后赋值给W,最后遍历得到W上赋值的总和,便是该题的答案,时间复杂度为O(n),明显优于第一种算法,而且代码实现也更加简单.
附AC代码:

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

int o[100005],w[100005];
int main()
{
    typedef long long ll;
    int length;
    int index_o=0,index_w=0,cnt=0,number_w=0;
    char str[100005];
    cin>>length>>str;
    for (int i=0;i<length;i++)
    {
        if (str[i]=='C') cnt++;
        if (str[i]=='O') {
            o[index_o]=cnt;
            number_w+=cnt;
            index_o++;
        }
        if (str[i]=='W') {
            w[index_w]=number_w;
            index_w++;
        }
    }
    //cout<<cnt<<endl;
    ll ans=0;
    for (int i=0;i<index_w;i++){
        ans+=w[i];
    }
    cout<<ans<<endl;
    return 0;
}