算法竞赛训练指南，57页
本题要点：
1、位运算
1）每一个字符串都是大写字母组成，因此，每一个字符串用一个整数的二进制表示，
比如： “ABD” 用二进制整数 (1011) = 11 来表示
2）字符串数量很小， n <= 24; 可以用 一个 整数 的二进制 数位表示是否选择了第i个字符串
比如： (0011001) == 25 表示选择了第 0， 第3 和 第4 个字符串
2、 先计算 前一半 n / 2 个字符串可能得到的 异或值。
n / 2 个字符串 中，选择第i个字符串或不选第i个字符串，一共有 2^(n / 2) 种选法， 每种选法用 一个二进制整数表示；
然后 map<int, int> table; // 某个异或值 --> 前 n / 2 个字符集的子集,
first ：表示某个异或值
second：这个整数的二进制，表示一种选法，这种由最多个字符串异或得到；
处理前 n / 2 个字符串, 更新 table;
然后遍历后一半 (n - n / 2)个字符串的所有选法，如果这种选法的异或值在table
中，则存在某种选法，使得所有的字母出现的次数为偶数；
找出一种选法，选择了最多的字符串；
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
const int MaxN = 25;
int n, A[MaxN]; //每一个字符串用一个二进制数表示（0 和 1 表示某个字母是否存在）
char str[1010];
map<int, int> table; // 某个异或值 --> 前 n / 2 个字符集的子集
map<int, int> pow_2; //pow_2[k] 表示 k 是 2 的多少次幂int bitcount(int x)
{
return x == 0? 0 : bitcount(x / 2) + (x & 1);
}inline int lowbit(int x)
{
return x & -x;
}int get_xor(int x, int flag) // flag == 1 , 表示后半部分
{
int step = 0;if(flag){
step += n / 2;}int sum = 0;for(int i = x; i > 0; i -= lowbit(i)){
sum ^= A[pow_2[lowbit(i)] + step]; }return sum;
}void solve()
{
table.clear();// 前 n / 2 个字符串， 计算可能的 异或值，存到 table 中int m = 1 << (n / 2);for(int x = 0; x < m; ++x) // x 的二进制的每一位，表示是否选择该位对应的字符串{
int val_xor = get_xor(x, 0); if(table.find(val_xor) == table.end()){
table[val_xor] = x; }else{
if(bitcount(x) > bitcount(table[val_xor])){
table[val_xor] = x;}}}int max_cnt = -1, left, right;// 后 n / 2 个字符串, 计算可能的 异或值m = 1 << (n - n / 2);for(int x = 0; x < m; ++x){
int val_xor = get_xor(x, 1);if(table.find(val_xor) != table.end()){
if(max_cnt < bitcount(x) + bitcount(table[val_xor])){
max_cnt = bitcount(x) + bitcount(table[val_xor]);left = table[val_xor], right = x;}}}printf("%d\n", max_cnt);int indx[MaxN];int ans_cnt = 0;for(int i = left; i > 0; i -= lowbit(i)){
indx[ans_cnt++] = pow_2[lowbit(i)];}for(int i = right; i > 0; i -= lowbit(i)){
indx[ans_cnt++] = pow_2[lowbit(i)] + n / 2;// 后半部分}for(int i = 0; i < ans_cnt; ++i){
printf("%d", indx[i] + 1);if(i + 1 < ans_cnt){
printf(" ");}else{
printf("\n");}}
}int main()
{
for(int i = 0; i <= MaxN; ++i){
pow_2[1 << i] = i;}while(scanf("%d", &n) != EOF && n){
memset(A, 0, sizeof(A));for(int i = 0; i < n; ++i){
scanf("%s", str);int len = strlen(str);for(int j = 0; j < len; ++j){
int indx = str[j] - 'A'; A[i] += (1 << indx);}}solve();}return 0;
}/* 1 ABC 6 ABD EG GE ABE AC BCD *//* 05 1 2 3 5 6 */