題目連結:
現在有 38 種角色,用字母「A」~「Z」代表前 26 個角色;「a」~「i」代表後面的 12 個。
給定兩正整數 m 、 n (m ≦ 38,n ≦ 500, 000),代表現在只探討前 m 個角色,且接下來有 n 列輸入。每列輸入有一字串(組成字母為前 m 個角色的代表字母,且長度介於 1 ~ 1, 000)其代表一個角色間的「CP」。
每個 CP 中可能出現同一字母,也就是同一角色,因此可做簡化。例如「ABB」等價於「AB」。
現在定義一組 CP 的補集意思為,此組 CP 裡以外的角色形成的集合(「以外」,依然是在前 m 個裡的角色)。
現在已知這 n 組 CP 的內容,求有多少對 CP 組互為補集?
記憶體限制:64 MB。
以下是針對 C++ 的解法(使用「map」):
直觀想法應該是用一個字串儲存簡化過後的 CP 組,然後用一個迴圈去找出這個 CP 組應有的補集。然後看 map 裡這個補集存不存在。存在的話,就將答案加上這個補集出現過的次數(也就是前面處理過的 CP 組)。
但是直接將字串丟進 map 裡雜湊會使得記憶體消耗過大。因此我們將此資訊壓到一個 long long 型態的變數裡。一個 long long 變數長度為 64 個位元,我們可以將其中的 m 位元作為有無對應角色的狀態。「1」代表有該角色;「0」代表沒有。(當然,這是可以反過來的)
對於每組 CP ,一看到有一個角色存在於此組 CP 。就將上面 long long 變數對應位元設為「1」(可以善用 OR 運算)
然後將我們挑的 m 個位元 01 反轉(0 變 1 、 1 變 0),即是該組 CP 的補集。接著,就按照原本直觀的想法去判斷即可。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。