LA 2965 Jurassic Remains 中途相遇法 .

题目地址：http://vjudge.net/problem/UVALive-2965

题目就是在n行中任意组合，是的他们代表的数值异或为0；

很明显直接暴力，列出1~（1<<N）的所有子集 ，为了加快速度用中途相遇法

#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
int A[25]; char str[1000];
std::map<int, int> table;
int bitCount(int x){return x?bitCount(x>>1)+(x&1):0;
}
int main(int argc, char const *argv[])
{int N;while(scanf("%d",&N)==1){REP(i,0,N-1){scanf("%s",str);A[i]=0;for(int j=0;str[j];++j) A[i]|=1<<(str[j]-'A');}table.clear();int n1=N/2,n2=N-n1;REP(i,0,(1<<n1)-1) {  //计算1~n1的xor bitCount 大的 子集合int x=0;REP(j,0,n1-1) if((1<<j)&i) x^=A[j];if(!table.count(x)||bitCount(table[x])<bitCount(i)) table[x]=i;}int ans=0;REP(i,0,(1<<n2)-1){int x=0;REP(j,0,n2-1) if((1<<j)&i) x^=A[n1+j];if(table.count(x)&&bitCount(table[x])+bitCount(i)>bitCount(ans)) ans=table[x]^(i<<n1);}printf("%d\n", bitCount(ans));REP(i,0,N) if((1<<i)&ans) printf("%d ", i+1);putchar('\n');}return 0;
}