gdufe acm 1136 查找ACM(加强版)

Problem Description:

作为一个acmer，应该具备团队合作能力和分析问题能力。给你一个只有a，c和m的字符串，你要依次取3个字母使之恰好为acm。 
           

比如串

accmmmca 你可以取

12345678

ac_m____

ac__m___

ac___m__

a_cm____

a_c_m___

a_c__m__共6种。

你只要给出给你的串有多少种方案能组成acm。

Input:

输入包含多组测试，对于每组测试，输入一个只有acm3种字母的串（长度<=200000）

Output:

对于每组测试，输出一个整数一行，表示给你的串有多少种方案能组成acm。

Sample Input:

accmmmca

Sample Output:

6

#include <stdio.h>
#include <string.h>
const int maxn=;
char s[maxn];
int cnt_a[maxn];
//cnt_a[i]是第i+个'c'前'a'的个数
int main(){
    //freopen("data.txt","r",stdin);
    //freopen("WA.txt","w",stdout);
    while(scanf("%s",s)!=EOF){
        int len=strlen(s);
        int a=,cnt=;
        for(int i=;i<len;i++){
            if(s[i]=='a')
                a++;
            else if(s[i]=='c'){
                cnt_a[cnt++]=a;
            }
        }//算出每个'c'前'a'的个数
        int m=;
        long long ans=;
        for(int i=len-;i>=;i--){
            if(s[i]=='m')
                m++;
            else if(s[i]=='c'){
                ans+=LL*cnt_a[--cnt]*m;
                //这里可能溢出，所以要转化为long long
            }
        }//算出每个'c'后'm'的个数，与在该'c'前的'a'的个数相乘，累加
        printf("%lld\n",ans);
    }
    return ;
}