[USACO 2015 FEBRUARY BRONZE] COW 题解 题目大意 给定一个长度为 NNN 的字符串，仅包含字符 C、O、W。我们需要统计序列 COW 作为子序列（不要求连续）在字符串中出现的次数。 算法分析 暴力解法的问题 最直观的想法是枚举三个位置 i<j<ki < j < ki<j<k，判断 s[i]=Cs[i] = \text{C}s[i]=C、s[j]=Os[j] = \text{O}s[j]=O、s[k]=Ws[k] = \text{W}s[k]=W。这样的时间复杂度为 O(N3)O(N^3)O(N3)，对于 N≤105N \leq 10^5N≤105 来说显然不可行。 高效解法 我们采用动态规划的思想，记录到当前位置为止： * 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(N)O(N)，只需要遍历一次字符串 * 空间复杂度：O(1)O(1)O(1)，只需要几个计数器变量 正确性证明 设 FC(i)F_C(i)FC (i) 表示前 iii 个字符中 C 的个数，FCO(i)F_{CO}(i)FCO (i) 表示前 iii 个字符中 CO 子序列的个数，FCOW(i)F_{COW}(i)FCOW (i) 表示前 iii 个字符中 COW 子序列的个数。 递推关系： 1. 如果 s[i]=Cs[i] = \text{C}s[i]=C: FC(i)=FC(i−1)+1F_C(i) = F_C(i-1) + 1FC (i)=FC (i−1)+1，FCO(i)=FCO(i−1)F_{CO}(i) = F_{CO}(i-1)FCO (i)=FCO (i−1)，FCOW(i)=FCOW(i−1)F_{COW}(i) = F_{COW}(i-1)FCOW (i)=FCOW (i−1) 2. 如果 s[i]=Os[i] = \text{O}s[i]=O: FC(i)=FC(i−1)F_C(i) = F_C(i-1)FC (i)=FC (i−1)，FCO(i)=FCO(i−1)+FC(i−1)F_{CO}(i) = F_{CO}(i-1) + F_C(i-1)FCO (i)=FCO (i−1)+FC (i−1)，FCOW(i)=FCOW(i−1)F_{COW}(i) = F_{COW}(i-1)FCOW (i)=FCOW (i−1) 3. 如果 s[i]=Ws[i] = \text{W}s[i]=W: FC(i)=FC(i−1)F_C(i) = F_C(i-1)FC (i)=FC (i−1)，FCO(i)=FCO(i−1)F_{CO}(i) = F_{CO}(i-1)FCO (i)=FCO (i−1)，FCOW(i)=FCOW(i−1)+FCO(i−1)F_{COW}(i) = F_{COW}(i-1) + F_{CO}(i-1)FCOW (i)=FCOW (i−1)+FCO (i−1) 我们的算法正是模拟了这个递推过程。 代码实现 示例分析 示例1 其他示例 * CWOW: 只有1个 COW 序列 * CCOW: 有2个 COW 序列（两个 C 都可以和 O、W 组成序列） * CCOOWW: 有8个 COW 序列 注意事项 1. 使用 long long 类型存储计数器，因为答案可能很大 2. 算法是 O(N)O(N)O(N) 的，可以处理 N≤105N \leq 10^5N≤105 的数据规模 3. 注意字符顺序必须是 C → O → W，不能颠倒 总结 本题考察了子序列计数的动态规划思想。通过维护中间状态（C、CO 的数量），我们可以在线性时间内计算出 COW 序列的总数。这种方法可以推广到计算任意固定序列作为子序列出现的次数。