查找ACM(加强版)

Time Limit: 2000/1000ms (Java/Others)

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
解题思路：先打表每个字符下，前面'a'的个数，然后从后往前遍历，计算'm'的个数，当遇到字符'c'时，即将前面'a'的个数cnt[i]乘以后面'm'的个数，迭代计算，但要注意的是两数相乘会爆int，所以先强转成long long，再做计算，这样就不会爆int了。

 #include<bits/stdc++.h>

 using namespace std;

 const int N = ;

 typedef long long LL;

 char s[N];

 int cnt[N];

 int main()

 {

     while(cin>>s){

         int a=,m=,len=strlen(s);

         for(int i=;i<len;++i){

            if(s[i]=='a')a++;

            cnt[i]=a;

         }

         LL ans=;

         for(int i=len-;i>=;--i){

             if(s[i]=='m')++m;

             if(s[i]=='c')ans+=(LL)m*cnt[i];

         }

         cout<<ans<<endl;

     }

     return ;

 }