uva 1326 Jurassic Remains(中途相遇法)

题目链接：

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

题目大意：

给n个大写字母组成的字符串，选择尽量多的串，使得每个大写字母都能出现偶数次。

思路：

一看到Time limit: 18.000 seconds， 很high地无任何优化直接暴力写了一个，9s多过了，估计是自己有史以来耗时最久的一次AC

然后想着怎样优化一下，发现所有字母出现的次数可以用二进制来表示，0表示偶数，1表示奇数。这样的话，把所有选择的字符串状态进行抑或运算一次，结果为0就表示全部是偶数。

这样就从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中途相遇法（直接枚举二进制的状态而不用递归）：

#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个所有组合状态
        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;
}