题意是给定n个大写字母组成的字符串。选择尽量多的串，使得每个字母的出现次数为偶数。
可以把每个单词转化成01串，然后用异或操作处理。
这里如果枚举所有情况的话复杂度是2^n，白书上面介绍了一种中途相遇法，可以把复杂度降低到2^(n/2)*logn甚至更低
方法是先穷举前n/2异或的所有可能值，如果有相同的保留最大的，可以用hash或者map存储映射关系。
然后穷举后n/2的所有可能值，然后在前面的值中找是否有一样的，从而得出解
我写的比白书上面的挫多了==
|
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 |
#include <cstdio>#include <algorithm>#include <cstring>#include <map>using
namespace std;const
int maxn = 24;int
n,val[maxn];char
s[1000];map<int,int> table,table1;int
main() { while(~scanf("%d",&n)) { for(int
i = 0;i < n;i++) { scanf("%s",s); val[i] = 0; for(int
j = 0;s[j];j++) val[i] ^= (1 << (s[j] - ‘A‘)); } table.clear(); table1.clear(); int
n1 = n / 2,n2 = n - n1; //中途相遇法，先处理前半部分 for(int
i = 1;i <= (1 << n1);i++) { int
nowval = 0,nowc = 0; for(int
j = 0;j < n1;j++) { if(((1 << j) & i) != 0) { nowval ^= val[j]; nowc++; } } if(table.count(nowval) == 0 || table[nowval] < nowc) { table[nowval] = nowc; table1[nowval] = i; } } //后半部分 int
ans = 0,ansval = 0,ansi = 0; for(int
i = 1;i <= (1 << n2);i++) { int
nowval = 0,nowc = 0; for(int
j = 0;j < n2;j++) { if(((1 << j) & i) != 0) { nowval ^= val[j + n1]; nowc++; } } if(table.count(nowval) != 0 && table[nowval] + nowc > ans) { ans = table[nowval] + nowc; ansval = nowval; ansi = i; } } //输出结果 printf("%d\n",ans); for(int
i = 0;i < n1;i++) if((1 << i) & table1[ansval]) printf("%d ",i + 1); for(int
i = 0;i < n2;i++) if((1 << i) & ansi) printf("%d ",i + n1 + 1); printf("\n"); } return
0;} |
原文：http://www.cnblogs.com/rolight/p/3551440.html