題目連結:
題目大意:
給定一正整數 N,代表接下來有 N 行。每行代表一個集合(從 A 開始編號)的內容。
並定義:
A + B,為 A 與 B 的聯集。
A * B,為 A 與 B 的交集。
A - B,為 A 與 B 的差集。
A >= B,代表 A 包含 B 。
求這 N 個集合彼此依序做上述集合運算的結果,意義重複的不用再做一次。
而 N=0,請結束程式,不用對這行做任何處理。
註:原題就沒有給 N 的範圍,甚至還沒有給「意義重複的不用再做」(但要注意,儘管本人照此 AC 了,但其實只是本人的擅自臆測)。
範例輸入:
2
abcdef
cfehi
2
34abcef
34
0
範例輸出:
Test Case 1:
A: {abcdef}
B: {cefhi}
A+B: {abcdefhi}
A*B: {cef}
A-B: {abd}
B-A: {hi}
A does not contain B
B does not contain A
Test Case 2:
A: {34abcef}
B: {34}
A+B: {34abcef}
A*B: {34}
A-B: {abcef}
B-A: {}
A contains B
B does not contain A
解題思維:
這題可以用 C++ 內建的 set 直接下去做。但是本人還是自己寫了一個類別。
本人的做法是:
在類別裡面宣告一個 bool 陣列,用以儲存相應位置的字元有無出現。
例:48 在 ASCII 裡面代表「0」這個字元,如果有出現「0」,就把 bool 陣列的第 48個位置設為 true。就算多次出現「0」,也只會當作出現一次(跟數學的集合一樣)。
然後各自定義 +、* 、- 和 >= 四個運算子,分別代表聯集、合集、差集和包含。
聯集的情況,就只是把兩者的 bool 陣列重疊在一起。
合集則是,要把兩者皆有的元素抓出來。
差集就是,自己有的,而對方(第二個運算元,像是 A - B的 B)沒有。
最後的包含,只要看對方所擁有的元素是否自己都有。
然後,多個集合的運算順序,本人是依照以下(以 N = 3為例):
A + B
A + C
B + C
A * B
A * C
B * C
A - B
A - C
B - A
B - C
C - A
C - B
A >= B
A >= C
B >= A
B >= C
C >= A
C >= B
以此類推。簡單來說就是,做起來結果會一樣的就不用做了,然後按照字典序(A 先,B 則後等等)。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。