題目大意：
給出n個字符串，字符串僅由大寫字母組成，問你用最多的字符串使得這些字符串里面的字符出現的總次數為偶數次
解題思路：
poj1741。1.dfs+位運算
2.中途相遇法
第一種思路就是普通的搜索，因為數據規模不是非常大，所以用搜索加上位運算也是可以通過所有數據的。
第二種思路是中途相遇法，先考慮這n個字符串的前n/2個，把每個字符串的狀態記錄到map里面，再枚舉后面的所有字符串的狀態，在map中尋找是否存在這個狀態。然后找到答案，時間復雜度是O(2^(n/2) * logn)或者更低
poj2352、代碼：
dfs+位運算
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;string str;
int ans, status, num[26];
void dfs(int n, int flag, int cnt, int st) {if (n == 0) {if (cnt < ans) return;if (!flag) {ans = cnt; status = st;}return;}dfs(n-1, flag ^ num[n], cnt + 1, st | (1 << (n-1)));dfs(n-1, flag, cnt, st);
}
int main() {ios::sync_with_stdio(false); cin.tie(0);int n, len, pos;while (cin >> n) {vector<int> vec; vec.clear();memset(num, 0, sizeof(num));for (int i = 1; i <= n; ++i) {cin >> str;len = str.length();for (int j = 0; j < len; ++j) {num[i] ^= (1 << (str[j] - 'A'));}}ans = 0, status = 0, pos = 1;dfs(n, 0, 0, 0);cout << ans << endl;while (status) {if (status & 1) vec.push_back(pos);++pos; status >>= 1;}pos = vec.size();for (int i = 0; i < pos; ++i) {if (i) cout << " ";cout << vec[i];}cout << endl;}return 0;
}#include <map>
#include <vector>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;string str;
vector<int> vec;
map<int, int> mp;
map<int, int>::iterator it;int num[26];inline int bitCount(int st) {int cnt = 0;while (st) {if (st & 1) ++cnt;st >>= 1;}return cnt;
}
int main() {ios::sync_with_stdio(false); cin.tie(0);int n, len, pos;while (cin >> n) {vec.clear(); mp.clear();int ans, res, status, half;memset(num, 0, sizeof(num));for (int i = 0; i < n; ++i) {cin >> str;len = str.length();for (int j = 0; j < len; ++j) {num[i] ^= (1 << (str[j] - 'A'));}}half = (1 << (n >> 1));for (int i = 0; i < half; ++i) {int flag = 0;for (int j = 0; j < (n >> 1); ++j) {if (i & (1 << j)) flag ^= num[j];}it = mp.find(flag);if (it == mp.end()) {mp[flag] = i;} else {if (bitCount(it -> second) < bitCount(i)) {it -> second = i;}}}ans = 0; res = 0;status = (1 << (n - (n >> 1)));for (int i = 0; i < status; ++i) {int flag = 0;for (int j = n >> 1; j < n; ++j) {if (i & (1 << (j - (n >> 1)))) {flag ^= num[j];}}it = mp.find(flag);if (it != mp.end()) {half = i << (n >> 1);int cnt = bitCount(half + it -> second);if (ans < cnt) {ans = cnt;res = half + it -> second;}}}cout << ans << endl;ans = 1;while (res) {if (res & 1) vec.push_back(ans);++ans;res >>= 1;}ans = vec.size();for (int i = 0; i < ans; ++i) {if (i) cout << " ";cout << vec[i];}cout << endl;}return 0;
}
