LA 2965 Jurassic Remains / 中途相遇法

本文主要是介绍LA 2965 Jurassic Remains / 中途相遇法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求尽量多的字符串 每种大写字母出现偶数次

每个字符串可以看成一个长度为26 出现奇数次对应位置为1 偶数为0

就是求一些字符串 他们的异或为0

n最大为24

2^24超时

可以枚举前一半n/2所以的子集 存在map里

然后枚举后一半看是否有和它相同的 相同的异或就为0

枚举一半时间可以接受

#include <cstdio>
#include <cstring>
#include <map>
using namespace std;const int maxn = 30;
map <int, int> table;
int n, a[maxn];int bitcount(int x)
{return x == 0 ? 0 : bitcount(x/2) + (x&1);
}
int main()
{char s[1000];while(scanf("%d", &n) == 1 && n){for(int i = 0; i < n; i++){a[i] = 0;scanf("%s", s);for(int j = 0; s[j]; j++)a[i] ^= (1<<(s[j]-'A'));}int n1 = n/2;int n2 = n-n1;table.clear();for(int i = 0; i < (1<<n1); i++)//前半 枚举了所有n1个元素的子集 {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))//bitcount求i的2进制中1的个数 table[x] = i;}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))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;
}

 

这篇关于LA 2965 Jurassic Remains / 中途相遇法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---