https://vjudge.net/problem/UVALive-2965
题意：
给出若干个由大写字母组成的字符串，要求选出尽量多的字符串，使得每个大写字母出现的次数是偶数。
思路：
如果说我们把每个字母映射为不同的数字，那么每个字符串就可以用不同的数字来表示，即按照二进制位转化各个字符。
如ABCD既可以表示为1111，ABCE可以表示为11101。
那么问题就转化成了给出n个数字，那么选择尽量多的数字使得他们的异或为0（每个字符出现偶数次，则他们的异或肯定为0）。
一开始我直接用的2^N的状态压缩但是t了，参考了训练指南，之后复杂度降为1.414^(N) * log(N)。
先把前n/2个数可以得到的数字用一个map存起来，之后枚举后面n - n/2个数可以得到的结果，直接在map里面寻找位数尽量大的就可以了。
求一个数的二进制位有多少个1，这题十分巧妙的用了二分。
代码：
#include <stdio.h>
#include <string.h>
#include <vector>
#include <map>
using namespace std; int a[]; vector<int> rec;
map<int,int> mmp; int calbit(int x)
{
if (x == ) return ; return calbit(x / ) + (x & );
} int main()
{
int n; while (scanf("%d",&n) != EOF)
{
mmp.clear();
rec.clear(); for (int i = ;i < n;i++)
{
int tmp = ; char b[]; scanf("%s",b); for (int j = ;j < strlen(b);j++)
{
tmp ^= ( << (b[j] - 'A'));
} a[i] = tmp;
} int n1 = n / ;
int n2 = n - n1; for (int i = ;i < ( << n1);i++)
{
int tmp = ; for (int j = ;j < n1;j++)
{
if (i & ( << j)) tmp ^= a[j];
} if (mmp.find(tmp) != mmp.end() || calbit(mmp[tmp]) < calbit(i)) mmp[tmp] = i;
} int ans = ; for (int i = ;i < ( << n2);i++)
{
int tmp = ; for (int j = ;j < n2;j++)
{
if (i & ( << j)) tmp ^= a[n1+j];
} if (mmp.find(tmp) != mmp.end())
{
if (calbit(i) + calbit(mmp[tmp]) > calbit(ans)) ans = mmp[tmp] ^ (i << n1);
}
} for (int i = ;i < n;i++)
{
if (ans & ( << i)) rec.push_back(i);
} printf("%d\n",rec.size()); for (int i = ;i < rec.size();i++)
{
printf("%d%c",rec[i] + ,i == rec.size() ? '\n': ' ');
} printf("\n");
} return ;
}