中途相遇法（侏罗纪，LA 2965）
发布时间
阅读量：
阅读量
几个需要注意的套路：
当你有N个物品时（给定一组物品），每个物品都有被选择或不被选择的两种可能性（二元选择），其组合总数等于2的N次方（即2^N种可能）。当N较小时（对于较小规模的问题），可以通过将一个整数的每一位来表示各个物品的状态（选取与否），这正是典型的位向量表示法（bit vector representation）。
如果对所有元素进行穷举可能会导致计算时间过长，则可以通过中间相遇技术来优化。这种方法允许我们通过中间相遇技术将时间复杂度从O(2N)降低到O(2(N/2) log N)。
如果想要检测奇偶性，并且特别针对位向量的话，使用异或运算将是一个高效的手段。
代码
#include<bits/stdc++.h>
#define maxn 30
using namespace std;
int N;
char str[maxn][maxn];
int A[maxn];
map<int,int>tb;
int ct(int x)
{
return x==0?0:ct(x>>1)+(x&1);
}
int main()
{
while(scanf("%d",&N)==1&&N)
{
tb.clear();
for(int i=0;i<N;i++)
{
scanf("%s",str[i]);
A[i]=0;
int l=strlen(str[i]);
for(int j=0;j<l;j++)
A[i]^=(1<<(str[i][j]-'A'));
}
int n1=N>>1;
int 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(!tb.count(x)||ct(i)>ct(tb[x])) tb[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(tb.count(x)&&ct(ans)<ct(tb[x])+ct(i))
ans=tb[x]^(i<<n1);
}
printf("%d\n",ct(ans));
for(int i=0;i<N;i++)
if(ans&(1<<i)) printf("%d ",i+1);
puts("");
}
return 0;
}
cpp
全部评论 (0)
还没有任何评论哟~