LA 2965 Jurassic Remains / 中途相遇法 - c++编程基础

求尽量多的字符串每种大写字母出现偶数次

每个字符串可以看成一个长度为26 出现奇数次对应位置为1 偶数为0

就是求一些字符串他们的异或为0

n最大为24

2^24超时

可以枚举前一半n/2所以的子集存在map里

然后枚举后一半看是否有和它相同的相同的异或就为0

枚举一半时间可以接受

#include 
  
   
#include 
   
     #include 
     using namespace std; const int maxn = 30; map 
     
       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<