f368 - 迦壕的回家作業
題目描述
題目描述了迦壕因色弱而無法分辨 RED 和 GREEN，導致寫功課時容易出錯。給定一個大寫英文字串，要求計算迦壕猜對顏色的機率，輸出形式為 1/n。
解題思路
這題的核心在於計算字串中 RED 和 GREEN 出現的次數。由於 RED 和 GREEN 的機率均等，因此猜對的機率是 1 / (2^RED 的數量 + 2^GREEN 的數量)。程式碼使用 Greedy 的方式遍歷字串，每找到一個 RED 或 GREEN 就將計數器加一。由於題目限制 RED 和 GREEN 的總數量小於等於 1000，因此可以直接計算 2 的冪次。程式碼預先計算了 2^0 到 2^1000 的值，儲存在 pw 陣列中，以便快速查詢。最後，根據 RED 和 GREEN 的數量計算機率，並以 1/n 的形式輸出。
複雜度分析
- 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為程式碼需要遍歷整個字串一次。
- 空間複雜度: O(1)，因為
pw陣列的大小是固定的 (1005)，不依賴於輸入字串的長度。
程式碼
#include <iostream>
using namespace std;
int sl,ans;
string s,pw[1005]={"1"};
string add(string a,string b){
int tmp[306]={0},al=a.length(),bl=b.length();
string c;
for(int i=0;i<al;++i)tmp[al-i-1]+=a[i]-'0';
for(int i=0;i<bl;++i)tmp[bl-i-1]+=b[i]-'0';
for(int i=0;i<305;++i)
if(tmp[i]>9){
++tmp[i+1];
tmp[i]-=10;
}
for(int i=305;i>=0;--i)
if(tmp[i]){
al=i;
break;
}
for(int i=al;i>=0;--i)c+=tmp[i]+'0';
return c;
}
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);
for(int i=1;i<=1000;++i){
pw[i]=add(pw[i-1],pw[i-1]);
}
while(cin >> s){
sl=s.size();
ans=0;
for(int i=0;i<sl;++i){
if(s[i]=='R'){
if(s[i+1]=='E'&&s[i+2]=='D'){
i+=2;
++ans;
}
}
else if(s[i]=='G'){
if(s[i+1]=='R'&&s[i+2]=='E'&&s[i+3]=='E'&&s[i+4]=='N'){
i+=4;
++ans;
}
}
}
cout << "1/" << pw[ans] << "\n";
}
}