e420 - 灰姑娘的新衣
題目描述
題目描述了灰姑娘收到 Caido 送的衣服，並要求計算所有衣服顏色搭配的可能性數量。此外，還需要找出出現次數最多的顏色，以及構成“完美搭配”的顏色組合（即所有衣服的顏色都相同）。
解題思路
程式碼使用 map 資料結構來儲存每種顏色的出現次數。程式首先讀取輸入，並根據輸入的字串進行處理。@ 符號表示換下一種衣服，程式會計算目前所有衣服顏色的搭配數量，並將其乘到總搭配數量 ans 中。# 符號表示輸入結束。
程式還追蹤出現次數最多的顏色，並在輸入結束後輸出這些顏色。同時，程式也找出“完美搭配”的顏色，即所有衣服的顏色都相同的顏色組合，並輸出這些顏色。
程式使用 st map 儲存完美搭配的顏色，在每次遇到 @ 時，比較當前 mp 和 st 的差異，將 st 中不在 mp 中的顏色移除，以確保 st 僅包含完美搭配的顏色。
複雜度分析
- 時間複雜度: O(N * M * log M)，其中 N 是輸入字串的數量，M 是不同顏色的數量。
map的操作（插入、查找、刪除）平均時間複雜度為 log M。 - 空間複雜度: O(M)，其中 M 是不同顏色的數量。
map儲存了所有不同的顏色。
程式碼
#include <iostream>
#include <map>
using namespace std;
int n,tans,ans=1,g;
string s;
map <string,int> tot;
map <string,int> mp;
map <string,int> st;
map <string,int> :: iterator it,it2;
int main(){
cin.tie(0); cout.tie(0);ios::sync_with_stdio(false);
while(getline(cin,s)){
if(s=="@"||s=="#"){
ans*=mp.size();
if(n==0){
st=mp;
}
else{
for(it=st.begin();it!=st.end();++it){
if(mp.find(it->first)==mp.end()){
++it;
it2=it;
--it;
st.erase(it->first);
it=it2;
}
}
}
mp.clear();
++n;
}
else{
tot[s]++;
mp[s]++;
tans=max(tans,tot[s]);
}
if(s=="#")break;
}
cout << ans << "\n";
for(it=tot.begin();it!=tot.end();++it){
if(it->second==tans){
if(g)cout << ",";
g=1;
cout << it->first ;
}
}
cout << "\n";
g=0;
for(it=st.begin();it!=st.end();++it){
if(g)cout << ",";
g=1;
cout << it->first ;
}
cout << '\n';
}