查找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:

對于每組測試，輸出一個整數(shù)一行，表示給你的串有多少種方案能組成acm。

Sample Input:

accmmmca

Sample Output:

6
解題思路：先打表每個字符下，前面'a'的個數(shù)，然后從后往前遍歷，計算'm'的個數(shù)，當遇到字符'c'時，即將前面'a'的個數(shù)cnt[i]乘以后面'm'的個數(shù)，迭代計算，但要注意的是兩數(shù)相乘會爆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 ;

 }