【题解】LA 2965 POJ 1903【Jurassic Remains】

分析

本题中,每个字符出现的次数是无关紧要的,重点是这些次数的奇偶性,然后很显然的就想到二进制。
问题就转化为求尽量多的数,使它们的$xor$值为0;
直接枚举是$O(2^n)$的,注意到$xor$值为0的两个整数必须完全相同,然后就可以把字符分成两部分,先计算前$n/2$个字符串所能得到的所有$xor$值,保存在map中;然后枚举后$n/2$个字符串所能得到的所有$xor$值,然后在map中查找。
这就是所谓的中途相遇法。

代码

#include<cstdio>
#include<map>
using std::map;

const int MAXN = 24 + 6;
map<int,int> table;

int bitcnt(int x){return x == 0 ? 0 : bitcnt(x / 2) + (x & 1);}

int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    int n,A[MAXN];
    char s[1000];

    while(scanf("%d",&n) == 1 && n){
        for(int i = 0;i < n;i++){
            scanf("%s",s);A[i] = 0;
            for(int j = 0;s[j] != '\0';j++) A[i] ^= (1 << (s[j] - 'A'));
        }

        table.clear();
        int n1 = n / 2,n2 = n - n1;
        for(int i = 0;i < (1 << n1);i++){
            int x = 0;
            for(int j = 0;j < n1;j++) if(i & (i << j)) x ^= A[j];
            if(!table.count(x) || bitcnt(table[x]) < bitcnt(i)) 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) && bitcnt(ans) < bitcnt(table[x]) + bitcnt(i)) ans = (i << n1) ^ table[x];
        }

        printf("%d\n",bitcnt(ans));
        for(int i = 0;i < n;i++) if(ans & (1 << i)) printf("%d ",i + 1);
        printf("\n");
    }

    return 0;
}