算法题：uva 1326 Jurassic Remains（中途相遇法）

算法题：uva 1326 Jurassic Remains（中途相遇法）2014-03-17 csdn博客 shuangde800题目大意：

给n个大写字母组成的字符串，选择尽量多的串，使得每个大写字母都能出现偶数次。

思路：

一看到Time limit: 18.000 seconds，很high地无任何优化直接暴力写了一个，9s多过了，估计是自己有史以来耗时最久的一次AC 尴尬

然后想着怎样优化一下，发现所有字母出现的次数可以用二进制来表示，0表示偶数，1表示奇数。这样的话，把所有选择的字符串状态进行抑或运算一次，结果为0就表示全部是偶数。

这样就从9s降到了1.692s

《竞赛指南》上介绍了效率更高的“中途相遇法”：把字符串分为2部分，首先计算前n/2个字符串的所有组合得到的 XOR 值，保存在因设map中，然后在枚举后n/2个字符，找和前面一样的值。

// uva1326Jurassic Remains// 直接位运算压缩#include<cstdio>#include<cstring>#include<iostream>#include<cctype>using namespace std;int n;char str[30];intst[30];bool vis[30];int dfs（int cur, int cnt, int sta）{if（cur==n）{if（！sta） return cnt;return -1;}if（cur<n）{vis[cur] = true;int res = dfs（cur+1, cnt+1, sta^st[cur]）;if（res ！= -1） return res;vis[cur] = false;res = dfs（cur+1, cnt, sta）;if（res ！= -1） return res;}}int main（）{while（~scanf（"%d", &n））{memset（st, 0, sizeof（st））;for（int i=0; i<n; ++i）{scanf（"%s", str）;for（int j=0; str[j]; ++j）{st[i] ^= （1<<（str[j]-"A"））;}}memset（vis, 0, sizeof（vis））;printf（"%d
", dfs（0, 0, 0））;bool first=true;for（int i=0; i<n; ++i）if（vis[i]）{first ？ first=false : putchar（" "）;printf（"%d", i+1）;}putchar（"
"）;}return 0;}