e540 - 01585 - Score

🔗 前往 ZeroJudge 原題

題目描述

題目要求計算一個由 'O' 和 'X' 組成的字串的得分。'O' 代表正確答案，'X' 代表錯誤答案。得分的計算方式是，每個 'O' 的分數等於它自身以及它前面連續 'O' 的數量之和。例如，對於字串 "OOXXOXXOOO"，得分是 1 + 2 + 0 + 0 + 1 + 0 + 0 + 1 + 2 + 3 = 10。

解題思路

這題可以使用貪心演算法來解決。我們遍歷字串，維護一個變數 c 來記錄連續 'O' 的數量。如果遇到 'O'，則將 c 加 1，並將 c 的值加到總得分 ans 中。如果遇到 'X'，則將 c 重置為 0。

複雜度分析

• 時間複雜度: O(n)，其中 n 是字串的長度。因為我們只需要遍歷字串一次。
• 空間複雜度: O(1)，因為我們只需要常數級別的額外空間來存儲變數 c 和 ans。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	int n;
	cin >> n;
	string a;
	while(n--){
		cin >> a;
		int c=0,ans=0;
		for(int i=0,al=a.length();i<al;++i){
			if(a[i]=='O'){
				++c;
				ans+=c;
			}
			else
				c=0;
		}
		cout << ans << "\n";
	}
}