Luobuyu's Blog

0%

1884.COW

发表于 分类于 ， 热度： ℃ 评论：
本文字数： 1.2k 阅读时长 ≈ 1 分钟
和之前第一次热身赛的一道题目非常像，现在感觉真简单。

1884. COW

题目描述：

奶牛贝茜在她最喜欢的牧场中发现了一块石碑，上面刻有神秘的碑文。

碑文的文字似乎来自一种神秘的古代语言，可看作一个只包含 C,O,W 三种字符的字符串。

尽管贝茜无法解密该文字，但是她很欣赏 C,O,W 按顺序构成她最喜欢的单词 COW。

她想知道 COW 在碑文中一共出现了多少次。

她不介意 C,O,W 之间是否存在其他字符，只要这三个字符按正确的顺序出现即可。

她也不介意多个不同的 COW 是否共享了一些字符。

例如，COW 在 CWOW 中只出现一次，在 CCOW 中出现两次，在 CCOOWW 中出现八次。

给定碑文中的文字，请帮助贝茜计算 COW 出现的次数。

输入格式

第一行包含 $ N $ 。

第二行包含一个长度为 $ N $ 的字符串，其中只包含字符 C,O,W。

输出格式

输出给定字符串中 COW 作为子序列（不一定连续）的出现次数。

数据范围

$ 1≤N≤10^5 $

输入样例：

1
2
6
COOWWW

输出样例：

1
6

题解：

可以参考这个，二者非常像。

3549-最长非递减子序列（翻转） | Luobuyu’s Blog

设计状态： $ C $ 作为第一个状态， $ CO $ 作为第二个状态。当遇到 $ C $ 的时候更新 $ C $ 的数量，当遇到 $ O $ 的时候更新 $ CO $ ，其中 CO += C，遇到 $ W $ 的时候更新答案 ans += CO即可。

只需要记录一个数量，根本不需要开辟 $ dp $ 数组。注意要开 long long，因为答案是通过乘增加的，增加速度非常快。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
string s;
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tcase;
    cin >> n;
    cin >> s;
    ll c = 0, co = 0;
    ll ans = 0;
    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] == 'C')
        {
            c++;
        }
        else if (s[i] == 'O')
        {
            co += c;
        }
        else if (s[i] == 'W')
        {
            ans += co;
        }
    }
    cout << ans << endl;
    return 0;
}