Jurassic Remains(LA 2965)位运算+枚举

来自《算法竞赛入门经典训练指南》

1.题目原文

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

md，英语根本读不下去啊啊啊啊啊啊啊啊。 给定n个大写字母组成的字符串，选择尽可能多的字符串，使得每个大写字母都能出现偶数次。

2.解题思路

在一个字符串中，每个字母的出现次数无关紧要，重要的是出现次数的奇偶性。因此想到可以用一个二进制的位表示一个字母(1表示出现奇数次，0表示出现偶数次)。 样例写成二进制如下: A B C D E F G H …… 1 1 0  1  0 0  0  0…… A B D 0 0 0  0  1 0  1  0 ……E G 0 0 0  0  1 0  1  0…… E G 1 1 0  0  1 0  0  0……A B E 1 0 1  0  0 0  0  0……A C  0 1 1  1  0 0  0  0……B C D 此问题转化为求尽可能多的数，使得它们得xor值为0. 可以最容易想到的是直接穷举，时间复杂度为O(2^n)，有些偏大。注意到xor值为0的两个数必须完全相等。因此，我们可以把字符串分成两部分:首先计算前半部分字符串所有的xor值，并将其保存到一个映射S(xor值→ 前n/2个字符串的一个子集)中，后半部分字符串枚举所有能得到的xor值，并每次都在S中查找。 如果映射用map实现，总时间复杂度为O(2^(n/2)logn)=O(1.414^n*logn)。这样的策略成为中途相遇法(Meet-in-the-Middle)。密码学中著名的中途相遇攻击(Meet-in-the-Middle-attack)就是基于这个原理。

3.AC代码

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
#include<cmath>
#include<bitset>
#include<sstream>
using namespace std;
using namespace std;
#define INF 0x7fffffff
typedef long long ll;
const int maxn=30;
map<int,int> table;
int n;
int A[maxn];
char s[1000];

//整数x在二进制表示下有多少位是1
int bitcount(int x)
{
    return x==0?0:bitcount(x/2)+(x&1);
}

int main()
{
    while(scanf("%d",&n)!=EOF&&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'));
            }
        }

        //计算前一半元素的所有子集的xor值
        //table[x]保存的是xor值为x的，bitcount尽量大的值
        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&(1<<j)) x^=A[j];
            }
            if(!table.count(x)||bitcount(table[x])<bitcount(i)) table[x]=i;
        }

        //枚举后n2个元素，并在table中查找
        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;
}