題目鏈接 ：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=460&page=show_problem&problem=4072

題目大意：

給n個大寫字母組成的字符串，選擇盡量多的串，使得每個大寫字母都能出現(xiàn)偶數(shù)次。

思路：

一看到Time limit: 18.000 seconds， 很high地無任何優(yōu)化直接暴力寫了一個，9s多過了，估計是自己有史以來耗時最久的一次AC

然后想著怎樣優(yōu)化一下，發(fā)現(xiàn)所有字母出現(xiàn)的次數(shù)可以用二進制來表示，0表示偶數(shù)，1表示奇數(shù)。這樣的話，把所有選擇的字符串狀態(tài)進行抑或運算一次，結果為0就表示全部是偶數(shù)。

這樣就從9s降到了1.692s

《競賽指南》上介紹了效率更高的“中途相遇法”： 把字符串分為2部分， 首先計算前n/2個字符串的所有組合得到的XOR 值，保存在因設map中，然后在枚舉后n/2個字符，找和前面一樣的值。

    // uva  1326  Jurassic Remains
// 直接位運算壓縮
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cctype>
using namespace std;

int n;
char str[30];
int  st[30];
bool vis[30];


int dfs(int cur, int cnt, int sta){
    if(cur==n){
        if(!sta) return cnt;
        return -1;
    }
    if(cur<n){
        vis[cur] = true;
        int res = dfs(cur+1, cnt+1, sta^st[cur]);
        if(res != -1) return res;

        vis[cur] = false;
        res = dfs(cur+1, cnt, sta);
        if(res != -1) return res;
    }
}


int main(){

    while(~scanf("%d", &n)){
        
        memset(st, 0, sizeof(st));
        for(int i=0; i<n; ++i){
            scanf("%s", str);
            for(int j=0; str[j]; ++j){
                st[i] ^= (1<<(str[j]-'A'));
            }
        }

        memset(vis, 0, sizeof(vis));
        printf("%d\n", dfs(0, 0, 0));
        bool first=true;
        for(int i=0; i<n; ++i)if(vis[i]){
            first ? first=false : putchar(' ');
            printf("%d", i+1);
        }
        putchar('\n');
    }
    return 0;
}
  

代碼2：中途相遇法（遞歸版本）：

    #include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
using namespace std;


const int MAXN = 30;
int n, vis;
int st[MAXN];
char str[MAXN];
map<int, int>table;
map<int, int>::iterator it;
int ansCnt, ansVis;

inline int bitCount(int x){
	int cnt = 0;
	while(x>0){ 
		if(x&1) ++cnt;
		x >>= 1;
	}
	return cnt;
}

void dfs1(int cur, int n, int vis, int sta){
	it = table.find(sta);
	if(it != table.end()){
		if(bitCount(it->second) < bitCount(vis)){
			it->second = vis;			
		}
	}else{
		table[sta] = vis;
	}
	if(cur < n){
		dfs1(cur+1, n, vis|(1<<cur), sta^st[cur]);
		dfs1(cur+1, n, vis, sta);
	}	
}

void dfs2(int cur, int n, int vis, int sta){
	it = table.find(sta);
	if(it != table.end()){
		int cnt = bitCount(vis+it->second);
		if(cnt > ansCnt){
			ansCnt = cnt;
			ansVis = vis+table[sta];
		}
	}
	if(cur < n){
		dfs2(cur+1, n, vis|(1<<cur),sta^st[cur]);
		dfs2(cur+1, n, vis, sta);
	}
}

int main(){
	int i,j;
	while(~scanf("%d", &n)){
		
		memset(st, 0, sizeof(st));
		table.clear();
		for(i=0; i<n; ++i){
			scanf("%s", str);
			for(j=0; str[j]; ++j){
				st[i] ^= (1<<(str[j]-'A'));
			}
		}

		dfs1(0, (n>>1), 0, 0);
		ansCnt=0, ansVis=0;
		dfs2(n/2, n, 0, 0);

		printf("%d\n", ansCnt);

		bool first=true;
		for(i=0; i<n; ++i)if((ansVis>>i)&1){
			first ? first=false : putchar(' ');
			printf("%d", i+1);
		}
		putchar('\n');
	}

	return 0;
}
  

版本3中途相遇法（直接枚舉二進制的狀態(tài)而不用遞歸）：

    #include<cstdio>
#include<cstring>
#include<map>
#include<iostream>
using namespace std;


const int MAXN = 30;
int n, vis;
int st[MAXN];
char str[MAXN];
map<int, int>table;
map<int, int>::iterator it;
int ansCnt, ansVis;

inline int bitCount(int x){
    int cnt = 0;
    while(x>0){ if(x&1) ++cnt;x >>= 1;  }
    return cnt;
}

int main(){
    int i,j;
    while(~scanf("%d%*c", &n)){
        
        memset(st, 0, sizeof(st));
        table.clear();
        for(i=0; i<n; ++i){
            gets(str);
            for(j=0; str[j]; ++j){
                st[i] ^= (1<<(str[j]-'A'));
            }
        }

        // 枚舉前n/2個所有組合狀態(tài)
        int end = (1<<(n>>1));
        for(i=0; i<end; ++i){        
            int sta = 0;
            for(j=0; j<(n>>1); ++j)if(i & (1<<j)){
                sta ^= st[j];
            }
            it = table.find(sta);
            if(it != table.end()){
                if(bitCount(it->second) < bitCount(i)){
                    it->second = i;
                }
            }else{
                table[sta] = i;
            }
        }
        
        ansCnt=0, ansVis=0; 
        end = (1<<(n-n/2));
        for(i=0; i<end; ++i){
            int sta = 0;
            for(j=(n>>1); j<n; ++j)if(i & (1<<(j-(n>>1)))){
                sta ^= st[j];
            }
            it = table.find(sta);
            if(it != table.end()){  
                int vis = i<<(n>>1);
                int cnt = bitCount(vis+it->second);  
                if(cnt > ansCnt){  
                    ansCnt = cnt;  
                    ansVis = vis+it->second;  
                }  
            }
        }

        printf("%d\n", ansCnt);
        bool first=true;
        for(i=0; i<n; ++i)if((ansVis>>i)&1){
            first ? first=false : putchar(' ');
            printf("%d", i+1);
        }
        putchar('\n');
    }

    return 0;
}

  

uva 1326 Jurassic Remains(中途相遇法)