ZeroJudge 解題筆記：e420. 灰姑娘的新衣

作者：王一哲
日期：2025年9月20日


ZeroJudge 題目連結：e420. 灰姑娘的新衣

解題想法

我用字典 color_idx 儲存各種顏色對應的衣服編號，另一個字典 idx_color 儲存各種衣服編號有的顏色，顔色不重複。最後再計算所有的組合數，輸出最多顔色的衣服，輸出完美搭配的顔色。

Python 程式碼

使用時間約為 22 ms，記憶體約為 3.7 MB，通過測試。

import sys
from collections import defaultdict

color_idx = defaultdict(list)  # 各種顏色對應的衣服編號，可重複
idx_color = defaultdict(set)  # 各種衣服編號有的顏色，不重複
cnt = 0  # 衣服編號
for line in sys.stdin:
    line = line.strip()  # 刪除最後的 \n
    cnt += 1  # 衣服編號加 1
    color_idx[line].append(cnt)  # 顏色 line 有的編號加上 cnt
    idx_color[cnt].add(line)  # 編號 cnt 有的顏色加上 line
    for s in sys.stdin:
        s = s.strip()  # 讀取一行字串，刪除最後的 \n
        if s == "@" or s == "#": break  # 讀到 # 或 @，中止迴圈
        color_idx[s].append(cnt)  # 顏色 s 有的編號加上 cnt
        idx_color[cnt].add(s)  # 編號 cnt 有的顏色加上 s，不重複
comb = 1  # 組合數
for v in idx_color.values(): comb *= len(v)
print(comb)
most_color = []
n = len(idx_color)  # 編號數量
perfect = []
imax = max([len(v) for v in color_idx.values()])
for k, v in color_idx.items():
    if len(v) == imax:
        most_color.append(k)
    if len(set(v)) == n:
        perfect.append(k)
print(",".join(sorted(most_color)))
print(",".join(sorted(perfect)))

C++ 程式碼

使用時間約為 2 ms，記憶體約為 344 kB，通過測試。

#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    map<string, vector<int>> color_idx;  // 各種顏色對應的衣服編號，可重複
    map<string, set<int>> color_idx_set;  // 各種顏色對應的衣服編號，不重複
    map<int, set<string>> idx_color;  // 各種衣服編號有的顏色，不重複
    int cnt = 0;  // 衣服編號
    string s;  // 暫存資料用的字串
    while(getline(cin, s)) {
        cnt++;  // 衣服編號加 1
        color_idx[s].push_back(cnt);  // 顏色 s 有的編號加上 cnt
        color_idx_set[s].insert(cnt);  // 顏色 s 有的編號加上 cnt
        idx_color[cnt].insert(s);  // 編號 cnt 有的顏色加上 line
        while(getline(cin, s)) {
            if (s == "@" || s == "#") break;  // 讀到 # 或 @，中止迴圈
            color_idx[s].push_back(cnt);  // 顏色 s 有的編號加上 cnt
            color_idx_set[s].insert(cnt);  // 顏色 s 有的編號加上 cnt
            idx_color[cnt].insert(s);  // 編號 cnt 有的顏色加上 line
        }
    }
    int comb = 1;  // 組合數
    for(auto it : idx_color) comb *= (int)it.second.size();
    cout << comb << "\n";
    vector<string> most_color, perfect;  // 最多衣服的顏色，完美搭配的顏色
    int n = (int)idx_color.size();  // 編號數量
    int imax = 0;  // 同顏色最多的衣服數量
    for(auto it : color_idx) imax = max(imax, (int)it.second.size());
    for(auto it : color_idx) {
        if ((int)it.second.size() == imax) most_color.push_back(it.first);
    }
    for(auto it : color_idx_set) {
        if ((int)it.second.size() == n) perfect.push_back(it.first);
    }
    for(int i=0; i<(int)most_color.size(); i++) {
        cout << most_color[i] << ",\n"[i == (int)most_color.size()-1];
    }
    for(int i=0; i<(int)perfect.size(); i++) {
        cout << perfect[i] << ",\n"[i == (int)perfect.size()-1];
    }
    return 0;
}