[USACO 2015 February Bronze] COW 题解

题目大意

给定一个长度为 $N$ 的字符串，仅包含字符 C、O、W。我们需要统计序列 COW 作为子序列（不要求连续）在字符串中出现的次数。

算法分析

暴力解法的问题

最直观的想法是枚举三个位置 $i < j < k$，判断 $s[i] = \text{C}$、$s[j] = \text{O}$、$s[k] = \text{W}$。这样的时间复杂度为 $O(N^3)$，对于 $N \leq 10^5$ 来说显然不可行。

高效解法

我们采用动态规划的思想，记录到当前位置为止：

• C 的数量（即 COW 中第一个字符的出现次数）
• 序列 CO 的数量（即第一个字符为 C，第二个字符为 O 的序列数）
• 序列 COW 的数量（即完整的 COW 序列数）

具体维护方式：

1. 当遇到字符 C 时，它本身可以作为新的 COW 序列的起点
2. 当遇到字符 O 时，它可以与之前的所有 C 组成 CO 序列
3. 当遇到字符 W 时，它可以与之前的所有 CO 序列组成完整的 COW 序列

核心算法

设三个计数器：

• c_count: 字符 C 出现的次数
• co_count: 序列 CO 出现的次数
• cow_count: 序列 COW 出现的次数

遍历字符串的每个字符：

1. 如果是 C: c_count++
2. 如果是 O: co_count += c_count（每个 C 都可以和这个 O 组成 CO）
3. 如果是 W: cow_count += co_count（每个 CO 都可以和这个 W 组成 COW）

时间复杂度

• 时间复杂度：$O(N)$，只需要遍历一次字符串
• 空间复杂度：$O(1)$，只需要几个计数器变量

正确性证明

设 $F_C(i)$ 表示前 $i$ 个字符中 C 的个数，$F_{CO}(i)$ 表示前 $i$ 个字符中 CO 子序列的个数，$F_{COW}(i)$ 表示前 $i$ 个字符中 COW 子序列的个数。

递推关系：

1. 如果 $s[i] = \text{C}$: $F_C(i) = F_C(i-1) + 1$，$F_{CO}(i) = F_{CO}(i-1)$，$F_{COW}(i) = F_{COW}(i-1)$
2. 如果 $s[i] = \text{O}$: $F_C(i) = F_C(i-1)$，$F_{CO}(i) = F_{CO}(i-1) + F_C(i-1)$，$F_{COW}(i) = F_{COW}(i-1)$
3. 如果 $s[i] = \text{W}$: $F_C(i) = F_C(i-1)$，$F_{CO}(i) = F_{CO}(i-1)$，$F_{COW}(i) = F_{COW}(i-1) + F_{CO}(i-1)$

我们的算法正是模拟了这个递推过程。

代码实现

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

int main() {
    long long n, c = 0, co = 0, cow = 0;
    string s;
    cin >> n >> s;
    
    for(int i = 0; i < n; i++) {
        if(s[i] == 'C') {
            c++;  // 新的C，可以作为COW的起点
        } else if(s[i] == 'O') {
            co += c;  // 这个O可以和之前的所有C组成CO
        } else if(s[i] == 'W') {
            cow += co;  // 这个W可以和之前的所有CO组成COW
        }
    }
    
    cout << cow << endl;
    return 0;
}

示例分析

示例1

输入:
6
COOWWW

处理过程:
字符  c   co   cow
C     1   0    0
O     1   1    0
O     1   2    0
W     1   2    2
W     1   2    4
W     1   2    6

输出: 6

其他示例

• CWOW: 只有1个 COW 序列
• CCOW: 有2个 COW 序列（两个 C 都可以和 O、W 组成序列）
• CCOOWW: 有8个 COW 序列

注意事项

1. 使用 long long 类型存储计数器，因为答案可能很大
2. 算法是 $O(N)$ 的，可以处理 $N \leq 10^5$ 的数据规模
3. 注意字符顺序必须是 C → O → W，不能颠倒

总结

本题考察了子序列计数的动态规划思想。通过维护中间状态（C、CO 的数量），我们可以在线性时间内计算出 COW 序列的总数。这种方法可以推广到计算任意固定序列作为子序列出现的次数。