UVa 1326 Jurassic Remains

　　中途相遇法，新学的东西，大概意思是把数据分为两部分，先考虑第一部分，把结果保存到一个映射里，再考虑第二部分，得出结果后再在第一部分的映射里查找并进行计算。不过不明白为什么时间复杂度是O(1.44ⁿlogn)。照搬书上的代码如下：

View Code

 1 #include <cstdio>
 2 #include <map>
 3 using namespace std;
 4 
 5 int const maxn = 24;
 6 map<int, int> table;
 7 
 8 int bitcount(int x)
 9 {
10     return x == 0 ? 0 : bitcount(x/2) + (x&1);
11 }
12 
13 int main()
14 {
15 #ifdef LOCAL
16     freopen("in", "r", stdin);
17 #endif
18     int n;
19     char s[1000];
20     int a[maxn];
21     while(scanf("%d", &n) !=EOF && n)
22     {
23         for(int i = 0; i < n; i++)
24         {
25             scanf("%s", s);
26             a[i] = 0;
27             for(int j = 0; s[j] != '\0'; j++)
28                 a[i] ^= (1<<(s[j]-'A'));
29         }
30         table.clear();
31         int n1 = n/2, n2 = n - n1;
32         for(int i = 0; i < (1<<n1); i++)
33         {
34             int x = 0;
35             for(int j = 0; j < n1; j++)
36                 if(i & (1<<j))   x ^= a[j];
37             if(!table.count(x) || bitcount(i) > bitcount(table[x]))
38                 table[x] = i;
39         }
40         int ans = 0;
41         for(int i = 0; i < (1<<n2); i++)
42         {
43             int x = 0;
44             for(int j = 0; j < n2; j++)
45                 if(i & (1<<j))   x ^= a[n1+j];
46             if(table.count(x)  && bitcount(table[x]) + bitcount(i) > bitcount(ans) )
47                 ans = (i<<n1)^table[x];
48         }
49         printf("%d\n", bitcount(ans));
50         for(int i = 0; i < n; i++)
51             if(ans & (1<<i))   printf("%d ", i+1);
52         printf("\n");
53     }
54     return 0;
55 }