本文共 1426 字，大约阅读时间需要 4 分钟。
奇偶性转成xor问题
map的应用，xor到集合的映射使问题大大简化。
bitcount()的写法
中途相遇法的应用。
#include #include using namespace std;const int maxn = 30;map table;int n;int a[maxn];char s[1005];int bitcount(int x){ return x == 0 ? 0 : bitcount(x / 2) + (x & 1);//统计有多少个1 //一定要写成(x & 1)的形式。 }int main(){ while(~scanf("%d", &n)) { for (int i = 0; i < n; i++) { scanf("%s", s); a[i] = 0; for (int j = 0; s[j] != '\0'; j++) a[i] ^= (1 << (s[j] - 'A')); } table.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 (!table.count(x) || bitcount(table[x]) < bitcount(i)) table[x] = i;//table[x]表示的是xor值为x的bitcount最大的集合。 } 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 (table.count(x) && bitcount(ans) < bitcount(table[x]) + bitcount(i))//tabel.count(x) != 0意味着两个集合配对可以成立。 ans = (i << n1) ^ table[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;}
转载于:https://www.cnblogs.com/yohanlong/p/7715640.html