解題區/解題區 - UVa

UVa 1326 - Jurassic Remains

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

博物館對於骨頭化石進行拼湊作業，每一個骨頭上用 A - Z 去標記。兩片骨頭可以連接則表示具有相同的英文字母。

現在有數組骨頭，上面會有數個街口。現在找一組骨頭集合，使得每一個接口都有其連接的對象，盡可能使集合越大越好。

Sample Input

1
2
3
4
5
6
7
6
ABD
EG
GE
ABE
AC
BCD

Sample Output

1
2
5
1 2 3 5 6

Solution

題目相當於問找一個集合，使得每一個字母數量出現偶數次。

由於 N = 24，這個數量使用$O(2^{24})$ 相當消耗時間。使用中間相遇法 (在密碼學中可以見到，有點雙向 Bfs 的味道)，也就是分治算法的概念，將問題對切，從兩個統計結果中找交集。算法降至$O(2^{12} \times 12)$

考慮前 N/2 個骨頭 A、後 N/2 個骨頭 B，分別找到在字母集出現狀態為 S 的最佳解 A1, B1，若將兩個相同狀態組合$S \text{ XOR } S = 0$ 符合出現偶數次的條件。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <stdio.h> 
#include <string.h>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
int main() {
    int n;
    char s[128];
    while (scanf("%d", &n) == 1) {
        int mask[32] = {};
        for (int i = 0; i < n; i++) {
            scanf("%s", s);
            int x = 0;
            for (int j = 0; s[j]; j++)
                x ^= (1<<(s[j] - 'A')); 
            mask[i] = x;
        }
        
        // D&C, dp, bitmask
        map<int, int> dp1, dp2;
        int div1 = n/2, div2 = n - n/2;
        for (int i = 0; i < (1<<div1); i++) {
            int x = 0;
            for (int j = 0; j < div1; j++) {
                if ((i>>j)&1)
                    x ^= mask[j];
            }
            if (dp1.count(x) || __builtin_popcount(dp1[x]) < __builtin_popcount(i))
                dp1[x] = i;			
        }
        for (int i = 0; i < (1<<div2); i++) {
            int x = 0;
            for (int j = 0; j < div2; j++) {
                if ((i>>j)&1)
                    x ^= mask[j + div1];
            }
            if (dp2.count(x) || __builtin_popcount(dp2[x]) < __builtin_popcount(i))
                dp2[x] = i;			
        }
        
        int retCnt = 0, retMask = 0;
        for (map<int, int>::iterator it = dp1.begin();
            it != dp1.end(); it++) {
            if (dp2.count(it->first)) {
                int x = it->second | ((dp2[it->first]) << div1);
                if (__builtin_popcount(x) > retCnt) {
                    retCnt = __builtin_popcount(x);
                    retMask = x;
                }
            }
        }
        printf("%d\n", retCnt);
        for (int i = 0, f = 0; i < n; i++) {
            if ((retMask>>i)&1) {
                if (f)	putchar(' ');
                f = 1;
                printf("%d", i+1);
            }
        }
        puts("");
    }
    return 0;
}