LA 2965 - Jurassic Remains 中途相遇法

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=12&problem=966

题意：

   给定n个字符串，求最多选几个并保证所有字母出现偶数次

  n最大为24，直接枚举2^24,对于18s的实现貌似也是可以接受的，但必然不好。想了很久降复杂度的方法都没想到好的，用中途相遇发只能降到(2^n/2)log(n),对于n很大还是无力

  中途相遇法指把原问题化为两个独立的子问题，一半通过枚举暴力完成，另一半枚举时利用map等结构查询前一半的结果，合并得出最终结果

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int count_one(int x)//分治计数
{
    x=(x&0x55555555)+(x>>1&0x55555555);
    x=(x&0x33333333)+(x>>2&0x33333333);
    x=(x&0x0F0F0F0F)+(x>>4&0x0F0F0F0F);
    x=(x&0x00FF00FF)+(x>>8&0x00FF00FF);
    x=(x&0x0000FFFF)+(x>>16&0x0000FFFF);
    return x;
}
int org[26],n;
map<int,int> table;
int main()
{
    while(~scanf("%d",&n))
    {
        char s[50];
        int i,j,len;
        for(i=0;i<n;i++)
        {
            scanf("%s",s);
            len=strlen(s);
            org[i]=0;
            for(j=0;j<len;j++)
            {
                org[i]^=1<<(s[j]-'A');
            }
        }
        int n1=n>>1,n2=n-n1,tmp,t,now;
        tmp=1<<n1;now=0;
        table.clear();
        for(i=0;i<tmp;i++)//枚举一半
        {
            t=i;j=0;
            now=0;
            while(t)
            {
                if(t&1)now^=org[j];
                j++; t>>=1;
            }
            if(count_one(table[now])<count_one(i))table[now]=i;//记录最大值
        }
        tmp=1<<n2;
        int ans=0;
        for(i=0;i<tmp;i++)
        {
            t=i;j=0;
            now=0;
            while(t)
            {
                if(t&1)now^=org[j+n1];
                j++; t>>=1;
            }
            if(table[now]!=0&&count_one(ans)<(count_one((i<<n1)^table[now])))//题目没说多组情况，用<可以过
            {
                ans=(i<<n1)^table[now];
            }
        }
        printf("%d\n",count_one(ans));

        for(i=0;ans;i++,ans>>=1)
            if(ans&1) printf("%d%c",i+1,ans>>1?' ':'\n');
    }

}