POJ 1903 & ZOJ 2469 & UVA 1326 Jurassic Rema

題意：給定n個只有大寫字母組成的字符串，選取盡可能多的字符串，使得這些字符串中每個字母的個數都是偶數。n<=24

思路：直接枚舉每個字符串的選或不選，復雜度是O(2^n)。其實還有更簡便的方法。

對於每個字母，其實具體出現了多少次並不重要，重要的是奇數次還是偶數次，我們用0對應奇數次，1對應偶數次。對於每個字符串，我們就可以計算出對應的二進制數，方法如下。如果A出現奇數次，那麼二進制數第一個位置為1，偶數次為0；如果B出現奇數次，那麼二進制數第二個位置為1，偶數次為0……以此類推，每個位置都有一個對應的0或1。這樣就組成了一個二進制數。所以我們就可以將題意轉化為找到盡量多的數字，使得他們的異或和為0。

直接枚舉復雜度是O(2^n)，但是我們不妨枚舉前n/2個數字的選或不選，將所有可以得到的異或值存在一個STL的map中（鍵為異或和，值為得到這個異或和的選或不選的狀態集合，對於同一個鍵，保留選取的數字最多的情況），然後枚舉後n/2個數字的選或不選，計算出每個異或和，在map中查找是否有異或和等的鍵（因為兩個相同的數字異或值為0），更新答案。

這樣的復雜度只有O(2^[n/2] * logn)。

#include<cstdio>
#include<map>
#define MAXN 30
using namespace std;

int n,a[MAXN];
char s[1005];
map<int ,int > F;

int bitcount(int x) {return x? bitcount(x/2)+(x&1):0;} //計算一個數二進制表示後所包含的1的個數
int main()
{
	while(~scanf("%d",&n))
	{
		for(int i=0;i<n;++i)
		{
			scanf("%s",s);
			a[i]=0;
			for(int j=0;s[j];++j) a[i]^=(1<<(s[j]-'A'));//將字符串轉化成數
		}
		
		F.clear();//每次記得清空映射
		int n1=n/2,n2=n-n1;
		for(int i=0;i < (1<< n1);++i) //枚舉前n/2個數的每種狀態
		{
			int x=0;
			for(int j=0;j<n1;++j) x^=((i>>j)&1)*a[j];//計算每種狀態的異或和
			if(F.count(x) || bitcount(i)>bitcount(F[x])) F[x]=i;//F記錄每個異或值所對應的字符串選取狀態
		}
		int ans=0;//答案記錄最終的選取狀態
		for(int i=0;i < (1<< n2);++i)  //枚舉後n/2個數的每種狀態
		{
			int x=0;
			for(int j=0;j<n2;++j) x^=((i>>j)&1)*a[j+n1];//計算每種狀態的異或和
			if(F.count(x) && bitcount(i)+bitcount(F[x])>bitcount(ans)) ans=(i<<n1)|F[x];
			//如果找到異或和與前n/2個數中的相同的異或和，那麼更新答案
		}
		printf("%d\n",bitcount(ans));
		for(int i=0;i<n;++i) if((ans>>i)&1) printf("%d ",i+1);
		printf("\n");
	}
	return 0;
}