切換
舊版
前往
大廳
主題

ZeroJudge - b050: 1. 集合運算 解題心得

Not In My Back Yard | 2018-10-12 19:25:18 | 巴幣 0 | 人氣 445

題目連結:


題目大意:
給定一正整數 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 則後等等)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作