简单解题思路

问题描述

给定 n 个由大写字母组成的字符串，要求找到一个最大的字符串子集，使得该子集中所有字符串的每个字母出现的总次数均为偶数次（即所有字母的异或结果为0）。

核心思想

1. 字母奇偶性编码：

   • 将每个字符串转换为一个二进制数，每位代表一个字母（A=0, B=1,..., Z=25），若字母出现奇数次则该位为1，否则为0。

2. 折半枚举（Meet-in-the-Middle）：

   • 将 n 个字符串分成两半（n1 和 n2）。
   • 枚举前一半的所有子集，计算异或值并记录最优解（用 map 存储异或值对应的子集大小）。
   • 枚举后一半的所有子集，检查其异或值是否能与前一半的某个异或值配对（两者异或为0），更新全局最优解。

3. 输出结果：

   • 输出满足条件的最大子集大小及其包含的字符串编号（从1开始）。

关键步骤

1. 输入处理：

   • 将每个字符串转换为二进制编码 a[i]，表示字母的奇偶状态。

2. 折半枚举：

   • 前一半：枚举所有子集，计算异或值 x，记录使子集最大的 x。
   • 后一半：枚举所有子集，检查是否存在前一半的 x 与当前异或值相等（即总异或为0），更新答案。

3. 结果输出：

   • 输出最大子集大小及其包含的字符串编号。

总结

• 核心算法：位运算 + 折半枚举（Meet-in-the-Middle）。
• 优化点：通过分治将指数级复杂度（O(2ⁿ)）降为 O(2^(n/2))，适合中等规模输入（n≤24）。
• 适用场景：需要满足异或性质的子集选择问题。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
 
using namespace std;
 
const int maxn=24;
map<int,int>mp;
 
int bitcount(int x)
{
    return x==0?0:(bitcount(x>>1)+(x&1));
}
 
int main()
{
    int n,a[maxn];
    char s[1111];
    while (~scanf("%d",&n))
    {
        if (n==0) break;
        getchar();
        for (int i=0;i<n;i++)
        {
            scanf("%s",s);
            a[i]=0;
            for (int j=0;s[j];j++)
            {
                a[i]^=(1<<(s[j]-'A'));
            }
        }
        mp.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 (!mp.count(x)||bitcount(mp[x])<bitcount(i))
                mp[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 (mp.count(x)&&bitcount(ans)<bitcount(mp[x])+bitcount(i))
                ans=(i<<n1)^mp[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;
}