牛客练习赛51 A abc
题意：
给出一个字符串s,你需要做的是统计s中子串”abc”的个数。子串的定义就是存在任意下标a<b<c，那么”s[a]s[b]s[c]”就构成s的一个子串。如”abc”的子串有”a”、”b”、”c”、”ab”、”ac”、”bc”、”abc”。
输入描述:
一个字符串s。保证输入只包含小写拉丁字符。
1<=|s|<=1e5
输出描述:
一个整数表示s中子串”abc”的个数。
示例1
输入
abcabc
输出
4
ac代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll a=0,ab=0,abc=0;
int main(){
cin>>s;
for(int i=0;s[i]!=’\0′;i++){
if(s[i]==’a’)
a++;
else if(s[i]==’b’)
ab+=a;
else if(s[i]==’c’)
abc+=ab;
}
cout<<abc<<endl;
return 0;
}
using namespace std;
typedef long long ll;
string s;
ll a=0,ab=0,abc=0;
int main(){
cin>>s;
for(int i=0;s[i]!=’\0′;i++){
if(s[i]==’a’)
a++;
else if(s[i]==’b’)
ab+=a;
else if(s[i]==’c’)
abc+=ab;
}
cout<<abc<<endl;
return 0;
}
思路：
1.需要统计的是abc的个数，字符串长度1e5，暴力直接超时，所以只能扫一遍。
2.然后我们可以想abc的顺序是先a再b最后c，我们可以先想子问题ab,
只要有a就加一，记录a出现的次数c1，当出现b时就会有c1个ab,那么看abc,ab作为一个整体，记录ab出现的次数AB，当出现c是就有AB个abc。
3.当遍历出现a是就记录下来a++,当遍历b时ab就有a个，当遍历到c时，abc就有ab个，最后输出abc的值。
版权声明：本文为lusiqi原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。