UVa1326 - Jurassic Remains (雙向搜尋-Meet in the middle、位元運算)

題目大意：

考古學家們挖到恐龍化石，但恐龍化石太大沒有辦法被載送回來，於是考古學家就將化石切成零件，並做上標記，載回博物館；但遇到了一個麻煩，同時有另外一批化石也被送回博物館，同時也是將化石切稱 零件，運氣不好的是他們的零件標記與我們使用的符號相同，我們的目標就是找出我們的恐龍化石，並且透過我們的零件組回化石。

有五點需要特別注意：

• 零件組合必須是兩個相同的標籤組成
• 每一個化石標籤，都必須都有相同的化石標籤且不一定是另外一個零件，也可以是自己的
• 我們找回的化石必須要是零件配對數量最大的，也就是零件配對數量必須要最高
• 一個零件中的所有標籤，每一個都必須被使用到
• 零件最多不會超過 25

懶人包題目大意：

是不是覺得上面很煩不想看？因此我有特別寫一個簡單版的。

利用題目測試資料的 x 行選出 y 行能夠將每一個字母的數字總合為偶數，且 y 必須是最大。好懂了八

分析：

由於必須輸出最大的行數且必須要輸出有哪些行，因此這裡 brute force 會是最好的選擇。

這題 Udebug 沒有提供測資，好難過啊QwQ。

時間複雜度

我們先來分析一下時間複雜度，如果使用 brute force 時複雜度會是 \(O(2^24)\)，選或不選並且有至少有 24 個英文字母，時間複雜度會太高，因此我們這邊使用雙向搜尋-Meet in the middle，將時間複雜度優化至\(O(2^{12} * 12) \)，選或不選有 12 個英文字母，且每一個都可以在與另外 12 個英文字母考慮選或不選，

• 時間複雜度 \(O(2^{24})\)，運行時間為 1.110s
  程式碼由JeraKrs 提供
• 時間複雜度 \(O(2^{12} * 12\)，運行時間為 0.3s

雙向搜尋-Meet in the middle

透過雙向搜尋-Meet in the middle，我們將 12 個字母分成一組，再將兩組合併，只要這兩組的字母合起來為偶數並偶數數量為最大值時則代表我們搜尋成功。

字母 Hash

稍微複習一下，左移(a << b )，為 \(a * 2 ^ b\)、右移(a >> b)，為 \(a / 2 ^ b\)

在這題，我們將運用到全新的黑科技(神奇的寫法)，透過二進位來 hash 每一個字母，A 為 1、B 為 2、C 為 4、D 為 8，想必大家都看的出來了，沒錯，那就是透過二進位的位數來進行 hash，因此程式碼會這樣寫

1 << (string[j] - 'A') //找出該字母的 hash

再聰明一點的朋友肯定會更多想一步，那這樣我就可以透過加法來給出每一行字串的 hash 了，這時候要請大家再回去看題目大意需要注意的第二點，那些標籤也可以跟自己的字串組合，因此這裡我們不使用加法而是使用 xor，來解決此問題，透過 xor 在兩個字母的 hash 都一樣時會變回 0，就可以方便處理到加法會進位的問題。

舉例： 3 xor 3 = 0

因此我們的 hash 字母可以這樣寫：

memset(mark,0,sizeof(mark)); //mark 為每一行存的 hash 值
for(int i = 0 ; i < n ; i++){
    cin >> temp ;
    x = 0 ;
    for(int j = 0 ; j < temp.length() ; j++)
        x ^= 1 << (temp[j] - 'A'); //字母 hash 並檢查奇偶數
    mark[i] = x ;
}

雙向搜尋-Meet in the middle 實作

這裡也要用到 2 進位，2 進位真的好用。

透過二進位的關係，可以寫出一種組合為全部的資料運用，我們用舉例的應該大家會比較好懂：

舉例：n = 3，我們想要輸出 3 的全部組合

n = 3，於是我們找到二進位位數等於 3 的最大值 = 7，並透過 for(i <= 8)，對 i 變數中位元為 1 的值紀錄可以發現以下有趣的事：

數字	位元為 1 的值紀錄
0	0
1	0
2	1
3	0,1
4	2
5	0,2
6	1,2
7	0,1,2
8	3

透過紀錄每一個數字位元為 1 的值，竟然可以將每一行的組合都找到！太神了拉！

其實是利用二進位的數字增加，透過此方式來找出全部的組合。

回歸焦點

我們現在已經可以找出全部的組合了，再來就是要每個組合進行 xor，並且保存記錄下來，值得注意的地方則是假如有兩個的 hash 值為一樣時，題目要求的是組合行數最大，因此當兩個 hash 值相同時我們則要找出使用最多行的 hash 值作為標準(最多行的組合)，因此我們再透過__builtin_popcount函數可以幫助我們找出此數字內有多少個 1，來完成此判斷。

map<int,int> m1 , m2 ; //紀錄 m1 為拆開的前半圖、m2為拆開的後半圖
int div1 = n/2 , div2 = n - n/2 ; //div1 為前半圖的寬度,div2 為後半圖的寬度
for(int i = 0 ; i < ( 1 <<div1) ; i++ ){ // 1 << div1 找到最大位數
    x = 0 ;
    for(int j = 0 ; j < div1 ; j++ ){ //div1 檢查這三位數即可
        if((i >> j ) & 1) x ^= mark[j] ; //紀錄有 1 的位數，並且讓他與那行進行 hash
    }
    if(!m1.count(x) || __builtin_popcount(m1[x]) < __builtin_popcount(i) ) 
    //比較是否有更多行的組合
        m1[x] = i ; //紀錄用到的行數，之後可以用位元為 1 的值回推
}
for(int i = 0 ; i < (1 << div2) ; i++){ // 1 << div2 的最大位數
    x = 0 ;
    for(int j = 0 ; j < div2 ; j++){ //div2 檢查這三位數即可
        if((i >> j ) & 1) x ^= mark[j + div1]; 
        //紀錄有 1 的位數，並且讓他與那行進行 hash，並且 mark[j + div1]，
        //需要加 div1 是因為這是後半張的圖，且我們 index 從 0 開始，因此只需要加 dvi1，不須 +1
    }
    if(!m2.count(x) || __builtin_popcount(m2[x]) < __builtin_popcount(i) )
    //比較是否有更多行的組合
        m2[x] = i ; //紀錄用到的行數，之後可以用位元為 1 的值回推
}

結合兩張圖，找出答案

現在我們將兩張圖都執行完畢也得到結果了，那是時候進行合併了！要怎麼合併呢？我們只需要查詢 m1 的資料有沒有在 m2 裡面就可以了！

為甚麼只需要這樣做呢？是因為我們 m1,m2 分別存了兩張圖的所有組合，我們只要找出這兩張圖組合起來最大的值即可，所以不需要檢查前半圖某一的組合裡面的某幾行是否有跟後半圖的某幾行形成偶數，因為這樣就會是前半圖的另外一個組合選項，故此不用。

並且記錄最大配對數量與最多配對行的 hash 即可

int resMask = 0 , resCnt = 0 ; //resCnt 最大的配對數量
//resMask 紀錄我們用到的值，hash 狀態，方便我們之後透過位元為1的位數來回推用到的行數 
for(auto it : m1){ //不斷進行配對
    if(m2.count(it.first)){ //找到適合的配對
        x = (m2[it.first] << div1) | it.second ; 
        //(m2[it.first] << div1) 我們先前存的資料行數是假設為這是一張獨立分開的圖，
        //因此現在我們進行合併，就要將資料行數返回題目原本正確的行數，因此幫她 << div1 
        if(resCnt < __builtin_popcount(x)) resCnt = __builtin_popcount(x) , resMask = x ;
        //如果有比當前配對最大數量還高時，我們就將 resCnt , resMask 換成現在的值
    }
}

hash resMask

這時候我們將記錄好的 resMask，解密成我們原本要的值，透過之前的表格可以得知，假如我們的 resMask = 7，則我們用到的行數則是 1,2,3，因此我們只需要將紀錄的 resMask 找出所有位數為 1 的值就能將值解密成功。

需要注意的是，在輸出時，每行的最後一個都必須是數字，而不是空格。

int flag = 1 ; //紀錄第一個值是否已經被印出
cout << resCnt << '\n' ; //印出最大配對數量
for(int i = 0 ; i < n ; i++){
    if((resMask >> i) & 1){ //判斷 i 位數是否為 1
        if(flag) cout << i+1 ;
        else cout << ' ' << i+1 ;
        flag = 0 ; //被輸出因此設成 0
    }
}

tips

記住如果是要判斷字典是否有此值時請使用，if(map.count(i))，而不是if(map[i])，在現在的 UVa Judge 中，只有第一種可以被允許使用，第二種目前不行，因此請不要隨意亂使用

心得

老實講，難的不是雙向搜尋，而是位元運算阿…，特別是那個透過二進位加法來找出全部的組合真的是跟神一樣，這是我從來沒有想過的解決方案，讓我在這邊學到了，算是非常開心呢！雖然自學演算法真的是一件非常痛苦的事情，但學習成功的成就感以及能讓腦袋智力快速上升的感覺真的事非常痛快呢！

也希望我可以在比賽中成功使用到我所學習到的演算法，或是在生活中用到，那是再好不過的了！

參考連結

[UVA-1326] （暴力+位运算+中间相遇法）
UVa 1326 - Jurassic Remains
uva 1326 - Jurassic Remains(暴力+位运算+中间相遇法）

題目程式碼

其實就是沒有附上說明的程式碼，看得懂跟說得出來真的是兩回事，也許還有人覺得我說的很差，不過我已經盡力解釋。希望可以幫助到各位。

也希望大家想要學習的知識都可以快速學習而成，不要因為自身的環境不足而學習不到。

於是這裡就補述一些題目給的資料範圍限制與標頭檔了。

#include <bits/stdc++.h>
#include <iostream>
#define LOCAL
#define MAXN 30
using namespace std ;
int n , mark[MAXN] , x ;
string temp ;

int main(){
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL

    while(cin >> n){
        memset(mark,0,sizeof(mark));
        for(int i = 0 ; i < n ; i++){
            cin >> temp ;
            x = 0 ;
            for(int j = 0 ; j < temp.length() ; j++)
                x ^= 1 << (temp[j] - 'A');
            mark[i] = x ;
        }
        map<int,int> m1 , m2 ;
        int div1 = n/2 , div2 = n - n/2 ;
        for(int i = 0 ; i < ( 1 <<div1) ; i++ ){
            x = 0 ;
            for(int j = 0 ; j < div1 ; j++ ){
                if((i >> j ) & 1) x ^= mark[j] ;
            }
            if(!m1.count(x) || __builtin_popcount(m1[x]) < __builtin_popcount(i) )
                m1[x] = i ;
        }
        for(int i = 0 ; i < (1 << div2) ; i++){
            x = 0 ;
            for(int j = 0 ; j < div2 ; j++){
                if((i >> j ) & 1) x ^= mark[j + div1];
            }
            if(!m2.count(x) || __builtin_popcount(m2[x]) < __builtin_popcount(i) )
                m2[x] = i ;
        }
        int resMask = 0 , resCnt = 0 ;
        for(auto it : m1){
            if(m2.count(it.first)){
                x = (m2[it.first] << div1) | it.second ;
                if(resCnt < __builtin_popcount(x)) resCnt = __builtin_popcount(x) , resMask = x ;
            }
        }
        int flag = 1 ;
        cout << resCnt << '\n' ;
        for(int i = 0 ; i < n ; i++){
            if((resMask >> i) & 1){
                if(flag) cout << i+1 ;
                else cout << ' ' << i+1 ;
                flag = 0 ;
            }
        }
        cout << '\n' ;
    }


}

在寫 UVa 1326 的紙筆紀錄

因為只是自己在思考過程中隨手做的筆記，覺得不是對讀者這麼有幫助，因此放在文章最下面。

有時候用想或用看的可能不太能夠懂這演算法，那就用寫的吧！這是大衛我自己學習的手稿，紀錄者我的學習過程。