713
LA 2965 - Jurassic Remains 中途相遇法
題意：
給定n個字符串，求最多選幾個並保證所有字母出現偶數次
n最大為24，直接枚舉2^24,對於18s的實現貌似也是可以接受的，但必然不好。想了很久降複雜度的方法都沒想到好的，用中途相遇發隻能降到(2^n/2)log(n),對於n很大還是無力
中途相遇法指把原問題化為兩個獨立的子問題，一半通過枚舉暴力完成，另一半枚舉時利用map等結構查詢前一半的結果，合並得出最終結果
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
int count_one(int x)//分治計數
{
x=(x&0x55555555)+(x>>1&0x55555555);
x=(x&0x33333333)+(x>>2&0x33333333);
x=(x&0x0F0F0F0F)+(x>>4&0x0F0F0F0F);
x=(x&0x00FF00FF)+(x>>8&0x00FF00FF);
x=(x&0x0000FFFF)+(x>>16&0x0000FFFF);
return x;
}
int org[26],n;
map<int,int> table;
int main()
{
while(~scanf("%d",&n))
{
char s[50];
int i,j,len;
for(i=0;i<n;i++)
{
scanf("%s",s);
len=strlen(s);
org[i]=0;
for(j=0;j<len;j++)
{
org[i]^=1<<(s[j]-'A');
}
}
int n1=n>>1,n2=n-n1,tmp,t,now;
tmp=1<<n1;now=0;
table.clear();
for(i=0;i<tmp;i++)//枚舉一半
{
t=i;j=0;
now=0;
while(t)
{
if(t&1)now^=org[j];
j++; t>>=1;
}
if(count_one(table[now])<count_one(i))table[now]=i;//記錄最大值
}
tmp=1<<n2;
int ans=0;
for(i=0;i<tmp;i++)
{
t=i;j=0;
now=0;
while(t)
{
if(t&1)now^=org[j+n1];
j++; t>>=1;
}
if(table[now]!=0&&count_one(ans)<(count_one((i<<n1)^table[now])))//題目沒說多組情況，用<可以過
{
ans=(i<<n1)^table[now];
}
}
printf("%d\n",count_one(ans));
for(i=0;ans;i++,ans>>=1)
if(ans&1) printf("%d%c",i+1,ans>>1?' ':'\n');
}
}
最後更新：2017-04-03 12:54:44