首页 > 代码库 > LA 2965 Jurassic Remains
LA 2965 Jurassic Remains
虽说是暴力题，但还是有很多很多的技巧与细节。
这题：
1、熟悉了位运算符，感觉异或操作的逼格有高了一级
2、可以用一个数的2进制来表示集合(这个需要多用)
3、中途相遇法。。。其实就是把总的集合拆成两半，降低指数使得暴力可解。(前段时间的中南校赛，好像也有个这种方法的题)
#include <cstdio>#include <map>using namespace std;const int maxn = 25;int a[maxn];map<int,int>tab;int bitcnt(int x){ return x?bitcnt(x>>1)+(1&x):0;}int main(){// freopen("in.txt","r",stdin); int n; while(~scanf("%d",&n)) { char s[1005]; 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‘)); } tab.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(!tab.count(x) || bitcnt(tab[x])<bitcnt(i))tab[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[j+n1]; if(tab.count(x) && bitcnt(ans)<bitcnt(tab[x])+bitcnt(i)) ans = tab[x]^(i<<n1); } printf("%d\n",bitcnt(ans)); for(int i = 0;i<n;++i)if(ans&(1<<i)) printf("%d ",i+1); puts(""); } return 0;}
LA 2965 Jurassic Remains
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。