c440 - Bert Love QQ !
題目描述
題目要求計算字串中 "QAQ" 子序列的數量。更具體地說，對於字串中的每個 'A'，計算其左側 'Q' 的數量和右側 'Q' 的數量，然後將它們相乘，並將所有 'A' 的結果加總。
解題思路
程式碼採用暴力法解決問題。它遍歷字串中的每個字元。如果當前字元是 'A'，則計算其左側和右側 'Q' 的數量。然後，將左側 'Q' 的數量乘以右側 'Q' 的數量，並將結果加到總計中。最後，程式輸出總計。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是字串的長度。因為對於每個 'A' 字元，程式都需要遍歷其左側和右側的字串來計算 'Q' 的數量。
- 空間複雜度: O(1)，程式只使用常數額外的空間。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
string a;
while(cin >> a){
long long int al=a.length(),ans=0;
for(int i=0;i<al;++i){
if(a[i]=='A'){
long long int lq=0,rq=0;
for(int j=0;j<i;++j){
if(a[j]=='Q'){
++lq;
}
}
for(int j=i+1;j<al;++j){
if(a[j]=='Q'){
++rq;
}
}
ans+=lq*rq;
}
}
cout << ans << "\n";
}
}