UVALive 2965 侏罗纪

清疚 2022-10-01 00:39 115阅读 0赞

**题目链接:[https://vjudge.net/problem/34853/origin][https_vjudge.net_problem_34853_origin]**

**题意 :** 给定n(1 <= n <= 24)个大写字母组成的串.选择尽量多的串,使得每个大写字母都能出现偶数次.

**Sample Input**

1  
ABC  
6  
ABD  
EG  
GE  
ABE  
AC  
BCD

**Sample Ouput**

0  
5  
1 2 3 5 6

分析 : 在一个字符串中,每个字符出现的次数本身是无关紧要的,重要的是这些次数的奇偶性,可以用一个二进制位来表示一个字母(1表示出现奇数次,0表示出现偶数次 ) 那么一个字符串就可以用一个32位整数来表示,问题转换为异或(xor)为0的最多整数的组合.

直接穷举复杂度为O(2^n),注意到异或为0的两个数一定相等,可以首先计算前n/2个字符串所能得到的xor值,并将其保存到一个映射中S,然后枚举后n/2个字符串所能得到的所有xor值,并每次都在S中查找.

这样的策略称为用中途相遇法.

#include <iostream>
    #include <cstdio>
    #include <map>
    using namespace std;
    
    const int maxn = 24;
    
    int A[maxn];
    map<int, int> table;
    
    int bitcount(int x)
    {
        return x == 0 ? 0 : bitcount(x / 2) + (x & 1);
    }
    int main()
    {
        int n;
        while(scanf("%d", &n) != EOF && n)
        {
            char str[1000];
            for(int i = 0; i < n; i++)
            {
                scanf("%s", str);
                A[i] = 0;
                for(int j = 0; str[j] != '\0'; j++) A[i] ^= (1 << (str[j] - 'A'));
            }
            table.clear();
            int n1 = n / 2;
            int n2 = n - n1;
            // 一共1<< n1个选择方式,每个数的二进制代表一种选择,某个数的某一位为数值为1表示这一位所对应的数存在
            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];  //i的二进制第j位为1 则表示第j被选择了
                if(!table.count(x) || bitcount(i) > bitcount(table[x])) 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];
                //若table.count(x)==0,则前n1元素没有一种选择方式异或会与x异或等于0;
                if(table.count(x) && bitcount(ans)< bitcount(i) + bitcount(table[x])) 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;
    }

这里用到有关二进制的一些技巧:

0 ^ x = x, 1 ^ x =  !x

由 x ^ 1 = !x 可以统计1出现的次数奇偶性

0 ~ (1 << n)的每个数的二进制表示一种选择方案

(i << nj) ^ j 衔接i 与 j 的二进制位

[https_vjudge.net_problem_34853_origin]: https://vjudge.net/problem/34853/origin