ZeroJudge 解題筆記：c440. Bert Love QQ !

作者：王一哲
日期：2025年8月16日


ZeroJudge 題目連結：c440. Bert Love QQ !

解題想法

由左向右依序讀取字元，目前讀到的 Q 總數為 tq，左側的 Q 加權後數量為 lq。讀到 Q 時答案 ans 加上 lq，並將 tq 加 1；讀到 A 時將 lq 加上 tq，相當於讀到第2個A時，第1個A左側的Q有效數量為2倍。

Python 程式碼

使用時間約為 47 ms，記憶體約為 3.5 MB，通過測試。

s = input()  # 要測試的字串
n = len(s)  # 字串長度
ans, lq, tq = 0, 0, 0  # 答案ans，左側Q的數量lq，Q的總數tq 
for c in s:  # 依序取出字元
    if c == 'Q':  # 如果讀到 Q
        ans += lq  # ans 加上 lq
        tq += 1  # tq 加 1
    elif c == 'A':  # 如果讀到 A
        lq += tq  # lq 加上 tq
# end of for loop
print(ans)  # 印出答案

C++ 程式碼

使用時間約為 2 ms，記憶體約為 568 kB，通過測試。

#include <iostream>
#include <string>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string s; cin >> s;  // 要測試的字串
    LL ans = 0, lq = 0, tq = 0;  // 答案ans，左側Q的數量lq，Q的總數tq
    for(char c : s) {  // 依序取出字元
        if (c == 'Q') {  // 如果讀到 Q
            ans += lq; tq++;  // ans 加上 lq，tq 加 1
        } else if (c == 'A') {  // 如果讀到 A
            lq += tq;  // lq 加上 tq
        }
    }
    cout << ans << "\n";  // 印出答案
    return 0;
}