切換
舊版
前往
大廳
主題

ZeroJudge - e288: 互補CP 解題心得

Not In My Back Yard | 2019-07-20 23:33:18 | 巴幣 0 | 人氣 752

題目連結:


題目大意:
現在有 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。



範例輸入:
3 4
ABB
AB
C
CC


範例輸出:
4


解題思維:
以下是針對 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 的補集。接著,就按照原本直觀的想法去判斷即可。

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

創作回應

更多創作