题解

题面描述

试卷由 $n$ 道单项选择题构成，每道题只有 $a$ , $b$ , $c$ , $d$ 四个选项。小红在批改试卷时，如果在答案序列中存在一个子序列恰好等于字符串 $"abc"$ ，她会产生一定的愤怒值。其中，子序列是指从原字符串中删除任意个（可以为零、也可以为全部）字符后保留剩余字符的顺序。如果答案序列中存在多个不同的方式可以得到 $"abc"$ 这个子序列，那么小红的愤怒值就是所有方式的数量。

思路

P2803.第1题-小红改试卷

1000ms

Tried: 94

Accepted: 33

Difficulty: 3

所属公司 : 阿里

算法与标签>动态规划

题目内容

小红正在批改同学的试卷,试卷由 $n$ 道单项选择题构成,每道题只有 $a ,b,c,d$ 四个选项.

如果在答案序列中存在恰好为" $abc$ "的子序列,那么小红会认为只是随手写的答案,会产生一点愤怒值. 给你这个答案序列,你需要求出小红会产生多少愤怒值

子序列为从原字符串中删除任意个(可以为零、可以为全部)字符得到的新字符串。

输入描述

第一行输出一个长度为 $n$ 的只存在 $a, b, c, d$ 字符串序列，表示答案序列 $(1≤n≤10^5)$

输出描述

输出一个整数,表示结果。

样例1

输入

abcc

输出

输入

预期输出（选填）

题解

题面描述

思路

P2803.第1题-小红改试卷

题目内容

输入描述

输出描述

样例1

Status

Development

Support

About