💜一) 题目要求

描述

在庆祝祖国母亲70华诞之际，老师给小乐乐出了一个问题。大家都知道China的英文缩写是CHN，那么给你一个字符串s，你需要做的是统计s中子序列“CHN”的个数。

子序列的定义：存在任意下标a < b < c，那么“s[a]s[b]s[c]”就构成s的一个子序列。如“ABC”的子序列有“A”、“B”、“C”、“AB”、“AC”、“BC”、“ABC”。

💦“子序列”类似数学中某集合非空子集的概念

输入描述：

输入只包含大写字母的字符串s。(1 ≤ length ≤ 8000)

输出描述：

输出一个整数，为字符串s中子序列“CHN”的数量。

💙二) 题解

法1：暴力算法

以实例1为例，输入：CCHNCHN，输出：7
先明白为什么结果是7↓
😈给这个字符串"CCHNCHN"中每个字母从左到右依次编号1234567，那么出现"CHN"的情况：

思路：每找到一个C，继续向后查找H；每找到一个H，向后继续查找N
💔但是这样暴力解题用到多层循环，复杂度过大，提交不通过

#include <stdio.h>
#include <string.h>int main()
{char s[8000];scanf("%s", s);int count = 0;int len = strlen(s);for (int i = 0; i < len; i++){if (s[i] == 'C'){for (int j = i + 1; j < len; j++){if (s[j] == 'H'){for (int ss = j + 1; ss < len; ss++){if (s[ss] == 'N')count++;}}}}}printf("%d", count);return 0;
}

法2.找规律，累加

📘因此，我们可以先找以C开头的子序列，那么遇到H的话就组成"CH"，也就是说"CH"的个数取决于C的个数，同理，当你找到“N”的时候,就是“CH“还有"N组成的“CHN”，"CH“的个数就是“CHN”的个数，把个数做累加。

#include <stdio.h>
#include <string.h>
int main()
{char s[8000];scanf("%s", s);int len = strlen(s);long long int count_c = 0, count_h = 0, count_n = 0;for (int i = 0; i < len; i++){if (s[i] == 'C')count_c++;else if (s[i] == 'H')count_h += count_c;else if (s[i] == 'N')count_n += count_h;}printf("%lld", count_n);return 0;
}