小乐乐与字符串

NC54509. 小乐乐与字符串

描述

在庆祝祖国母亲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

输入:

CCHNCHN

输出:

示例2

输入:

CCHNCHNCHNCHN

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

Pascal(fpc 3.0.2) 解法, 执行用时: 2ms, 内存消耗: 256K, 提交时间: 2019-11-08 19:27:17

var
a:ansistring;
i:longint;
c,h,n,z:int64;
begin
read(a);
for i:=1 to length(a) do
 begin
  if a[i]='C' then inc(c);
  if a[i]='H' then begin inc(h); n:=n+c; end;
  if a[i]='N' then z:=z+n;
 end;
writeln(z);
end.

Python3(3.5.2) 解法, 执行用时: 38ms, 内存消耗: 4076K, 提交时间: 2019-11-16 16:34:09

x=input()
a=0;b=0;c=0
for i in range(0,len(x)):
    if x[i]=='C':a=a+1
    if x[i]=='H':b=b+a
    if x[i]=='N':c=c+b
print(c)