标签归档:中途相遇法

LA 2965 Jurassic Remains 中途相遇法 (Meet-in-the-Middle)

给定N < 25个大写字母组成的字符串, 选择最多的传, 使得每个大写字母都能出现偶数次.

显然字母出现偶数次可以转换为: 每次异或, 最后为零. 由于只有26个英文字母, 故一个字符串可用一个int类型来表示.

直接枚举显然会超时, 故使用 中途相遇法 (Meet-in-the-Middle)

又知, 异或值为零的两个数必然完全相等.故可以使用map来维护xor值及对应使用的句子

# include <iostream>
# include <algorithm>
# include <string>
# include <map>
# define rep(x, n) for(int x = 0; x < (n); ++x)
using namespace std;

int n;

int a[30];

string s;

map <int, int> table;

int bitcount(int x)
{
    return x == 0 ? 0 : bitcount(x>>1) + (x&1);
}

int main()
{
    while ( cin >> n)
    {
        rep(i, n)
        {
            cin >> s;
            a[i] = 0;
            rep(j, s.size())
                a[i] ^= (1<<(s[j]-'A'));
        }
        table.clear();
        int n1 = n / 2;
        int  n2 = n - n1;
        //枚举前n1个元素的所有子集的xor值
        //table保存xor值为x, 包含元素最多的子集s
        rep(i, 1<<n1)
        {
            int x = 0;
            rep(j, n1) if (i & (1<<j)) x ^= a[j];
            if ( !table.count(x) || bitcount(table[x]) < bitcount(i) )
                table[x] = i;
        }
        int ans = 0;
        rep(i, 1<<n2)
        {
            int x = 0;
            rep(j, n2) if (i & (1<<j)) x ^= a[n1+j];
            if ( table.count(x) && bitcount(ans) < bitcount(table[x]) + bitcount(i) )
                ans = (i<<n1) | table[x];
        }
        cout << bitcount(ans) << endl;
        rep(i, n)
            if (ans & (1<<i))
                cout <<i+1<<" ";
        cout << endl;
    }
    return 0;
}