题解
在一个字符串中，每个字符出现的次数本身是无关紧要的，重要的只是这些次数的奇偶性，因此想到用一个二进制的位表示一个字母（$1$表示出现奇数次，$0$表示出现偶数次）。比如样例的$6$个数，写成二进制后如图所示。
此时，问题转化为求尽量多的数，使得它们的$xor$值为$0$。
最容易想到的方法是直接穷举，时间复杂度为$O(2^n)$，有些偏大。注意到$xor$值为$0$的两个整数必须完全相等，我们可以把字符串分成两个部分：首先计算前$n over 2$个字符串所能得到的所有$xor$值，并将其保存到一个映射$S$（$xor$值->前$n over 2$个字符串的一个子集）中；然后枚举后$n over 2$个字符串所能得到的所有$xor$值，并每次都在$S$中查找。
如果映射用$STL$的$map$实现，总时间复杂度为$O(2^{n over 2}log_2 n)$，即$O(1.44^n log_2 n)$，比第一种方法好了很多。
1 //It is made by Awson on 2017.9.20 2 #include <set> 3 #include <map> 4 #include <cmath> 5 #include <ctime> 6 #include <queue> 7 #include <stack> 8 #include <string> 9 #include <cstdio> 10 #include <vector> 11 #include <cstdlib> 12 #include <cstring> 13 #include <iostream> 14 #include <algorithm> 15 #define Min(a, b) ((a) < (b) ? (a) : (b)) 16 #define Max(a, b) ((a) > (b) ? (a) : (b)) 17 #define lowbit(x) ((x)&(-(x))) 18 #define LL long long 19 using namespace std; 20 21 int n; 22 char ch[1000]; 23 int a[30]; 24 map<int, int> mp; 25 26 int bitcount(int x) { 27 int cnt = 0; 28 for (; x; x -= lowbit(x)) cnt++; 29 return cnt; 30 } 31 32 void work() { 33 for (int i = 0; i < n; i++) { 34 scanf("%s", ch); 35 a[i] = 0; 36 for (int j = 0; j < strlen(ch); j++) a[i] ^= 1<<ch[j]-'A'; 37 } 38 mp.clear(); 39 int mid = n/2; 40 int lim = 1<<mid; 41 for (int i = 0; i < lim; i++) { 42 int tmp = 0; 43 for (int j = 0; j < mid; j++) 44 if (i&(1<<j)) tmp ^= a[j]; 45 if (!mp.count(tmp) || bitcount(mp[tmp]) < bitcount(i)) 46 mp[tmp] = i; 47 } 48 int ans = 0; 49 lim = 1<<(n-mid); 50 for (int i = 0; i < lim; i++) { 51 int tmp = 0; 52 for (int j = mid; j < n; j++) 53 if (i&(1<<j-mid)) tmp ^= a[j]; 54 if (mp.count(tmp) && bitcount(ans) < bitcount(mp[tmp])+bitcount(i)) ans = (i<<mid)|mp[tmp]; 55 } 56 printf("%d ", bitcount(ans)); 57 for (int i = 0; i < n; i++) 58 if (ans&(1<<i)) printf("%d ", i+1); 59 putchar(' '); 60 } 61 int main() { 62 while (~scanf("%d", &n)) 63 work(); 64 return 0; 65 }