f866 - DD排磁磚
題目描述
題目描述了 DD 弄亂工地磁磚後，工頭是否會生氣的情況。給定磁磚種類和數量，以及工頭希望的磁磚排列順序，計算 DD 不被罵的機率，並根據機率大小輸出結果。如果機率大於等於 1/2，則輸出 "DD真幸運!!我要下注!"，否則輸出機率（整數或最簡分數）。
解題思路
這題的核心在於計算 DD 按照工頭希望的順序排列磁磚的機率。首先，計算總的排列組合數，然後計算符合工頭要求的排列組合數。由於磁磚種類有限，且總數不大，可以採用貪心策略，逐步計算每個位置上放置正確磁磚的機率。程式碼中，mp 儲存每種磁磚的數量，迴圈模擬 DD 按照目標字串 s 放置磁磚的過程，並計算成功的機率。最後，將機率化簡為最簡分數，並與 1/2 比較，輸出結果。
複雜度分析
- 時間複雜度: O(N)，其中 N 是字串
s的長度。迴圈遍歷字串s，進行機率計算。 - 空間複雜度: O(M)，其中 M 是磁磚種類的數量。
mp儲存每種磁磚的數量。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,sl,t,v;
string s;
char c;
long long gcd( long long a, long long b ){
if( b==0 )
return a;
return gcd( b, a%b );
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
cin >> t;
while(t--){
cin >> n >> s;
sl=s.size();
int tot=0;
map <char,int> mp;
for(int i=0;i<n;++i){
cin >> c >> v;
mp[c]=v;
tot+=v;
}
if(tot<sl){
cout << "1\n";
}
else{
long long sn=1,mm=1;
for(int i=0;i<sl;++i){
sn*=mp[s[i]];
mm*=tot;
mp[s[i]]--;
tot--;
}
sn=mm-sn;
if(sn%mm==0){
cout << sn/mm << " ";
if(sn/mm==0){
cout << "DD真幸運!!我要下注!\n";
}
else{
cout << "\n";
}
}
else{
long long g=gcd(sn,mm);
sn/=g;
mm/=g;
cout << sn << "/" << mm << " ";
if(sn*2<=mm){
cout << "DD真幸運!!我要下注!\n";
}
else{
cout << "\n";
}
}
}
}
}