NEFU-1644 奶牛碑文

NEFU-1644 奶牛碑文

/ 0评 / 1456次 / 0

Description

小伟暑假期间到大草原旅游,在一块石头上发现了一些有趣的碑文。碑文似乎是一个神秘古老的语言,只包括三个大写字母 C、O 和 W。尽管小伟看不懂,但是令他高兴的是,C、O、W的顺序形式构成了一句他最喜欢的奶牛单词“COW”。现在,他想知道有多少次 COW 出现在文本中。 如果 COW 内穿插了其他字符,只要 COW 字符出现在正确的顺序,小伟也不介意。甚至,他也不介意出现不同的 COW 共享一些字母。例如,CWOW 出现了 1 次 COW,CCOW 算出现了2 次 COW,CCOOWW 算出现了 8 次 COW。

Input

第 1 行为 1 个整数 N。 第 2 行为 N 个字符的字符串,每个字符是一个 C、O 或 W。

Output

输出 COW 作为输入字符串的字串出现的次数(不一定是连续的)。 提示:答案会很大,建议用 64 位整数(long long)。

Accepted Code

#include <bits/stdc++.h>
using namespace std;
char ch[100005];
typedef long long LL;
int main()
{
    int t = 0;
    cin >> t;
    memset(ch, 0, sizeof(ch));
    scanf("%s", ch);
    LL cur_c = 0;
    LL cur_co = 0;
    LL cur_cow = 0;
    for (int i = 0; i < t; i++)
    {
        if (ch[i] == 'C')
        {
            cur_c++;
        }
        else if (ch[i] == 'O')
        {
            cur_co += cur_c;
        }
        else if (ch[i] == 'W')
        {
            cur_cow += cur_co;
        }
    }
    cout << cur_cow << endl;
}

解后反思

本题就比较有趣,利用向后遍历的过程中的状态转移加以优化。

例如在一串字符串中COWCW

第一次读到C cur_c=1 cur_co=0 cur_cow=0

第二次读到O cur_c=1 cur_co+=cur_c=1 cur_cow=0

第二次读到W cur_c=1 cur_co=1 cur_cow+=cur_co=1

以此类推

最终可得所有的COW有2个

发表回复

您的电子邮箱地址不会被公开。

你好 No.59611