日期: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)))