c440: Bert Love QQ !

內容

bert307 從全國賽後，得到了一種神奇的魔力～～

當他看到一個字串( String ) ，就會找尋其中的子序列 [ QAQ ]！

當找到一個 [ QAQ ]，Bert 就會 QQ 一次！

現在請寫個程式算一算 bert307 會 QQ 幾次～～

如果你不知道什麼是子序列，以下舉個範例：

子序列：字串當中由左到右挑取字元所構成的字串。

例如 algo 的子序列一共是： Ø（空集合）, a, l, g, o, al, ag, ao, lg, lo, go, alg, alo, ago, lgo, algo 。

輸入

單筆輸入~~

輸入只有一串字串 ( 長度 <= 100000 )

字串只包含大寫字母 " A " ~ " Z "

// Input 1
QAQAQYSYIOIKKK

// Input 2
QAQQQZZYNOAAA

輸出

寫一個程式算出 Bert 會 QQ 幾次～～

// Output 1
4

// Ouput 2
3

解題思路

由於子序列只包含 Q 和 A，所以其他字元皆不會有想結果，不用理會它們。

先舉幾個例子當參考

• QQQAQ = 3*1

• QQQAQQ = 3*2

• QQQAAQQ = 3*2 + 3*2

• QQQAQAQQ = 3*3 + 4*2

• QQQAQAQQAAQQQ = 3*6 + 4*5 + 6*3 + 6*3

發現要如果要計算 QAQ 子序列總量，就是當遇到 A 的時候把左邊的 Q 和右邊的 Q 相乘，然後把所有遇到 A 的情況相加即是答案。

但這樣子太難給程式計算了，所以在寫程式時要把邏輯反轉一下當變成"遇到 Q 的時候，會新產生多少個 QAQ 子序列"。

完整程式碼

AC (2ms, 188KB)

#include <stdio.h>

char input[100010];

int main()
{
    long long ans = 0;
    int sumQ = 0, leftQ = 0;
    gets(input);
    for (int i = 0; input[i]; i++)
    {
        if (input[i] == 'Q')
            sumQ++, ans += leftQ;
        else if (input[i] == 'A')
            leftQ += sumQ;
    }
    printf("%lld", ans);
    return 0;
}