求尽量多的字符串 每种大写字母出现偶数次
每个字符串可以看成一个长度为26 出现奇数次对应位置为1 偶数为0
就是求一些字符串 他们的异或为0
n最大为24
2^24超时
可以枚举前一半n/2所以的子集 存在map里
然后枚举后一半看是否有和它相同的 相同的异或就为0
枚举一半时间可以接受
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int maxn = 30;
map <int, int> table;
int n, a[maxn];
int bitcount(int x)
{
return x == 0 ? 0 : bitcount(x/2) + (x&1);
}
int main()
{
char s[1000];
while(scanf("%d", &n) == 1 && n)
{
for(int i = 0; i < n; i++)
{
a[i] = 0;
scanf("%s", s);
for(int j = 0; s[j]; j++)
a[i] ^= (1<<(s[j]-‘A‘));
}
int n1 = n/2;
int n2 = n-n1;
table.clear();
for(int i = 0; i < (1<<n1); i++)//前半 枚举了所有n1个元素的子集
{
int x = 0;
for(int j = 0; j < n1; j++)
{
if(i & (1<<j))
x ^= a[j];
}
if(!table.count(x) || bitcount(table[x]) < bitcount(i))//bitcount求i的2进制中1的个数
table[x] = i;
}
int ans = 0;
for(int i = 0; i < (1<<n2); i++)
{
int x = 0;
for(int j = 0; j < n2; j++)
{
if(i & (1<<j))
x ^= a[n1+j];
}
if(table.count(x) && bitcount(ans) < bitcount(table[x]) + bitcount(i))
ans = (i<<n1)^table[x];
}
printf("%d\n", bitcount(ans));
for(int i = 0; i < n; i++)
{
if(ans & (1<<i))
printf("%d ", i+1);
}
printf("\n");
}
return 0;
}