给定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; }