亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

uva 1326 Jurassic Remains(中途相遇法)

系統 1928 0

題目鏈接

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;
}

  






uva 1326 Jurassic Remains(中途相遇法)


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 四虎跳转48小时 | 九九自拍 | 日本中文字幕在线观看视频 | 一区二区三区精品国产欧美 | 免费看成人频视在线视频 | 中文字幕国产 | 成人欧美一区二区三区黑人 | 亚洲欧美日韩中文字幕在线一 | 久久国产加勒比精品无码 | 亚洲精品久久久久久久网站 | 久久精品国产在热久久2019 | 欧美日韩国产高清一区二区三区 | 欧美久久久久久久一区二区三区 | 在线观看 日韩 | 久久亚洲人成国产精品 | 欧美日韩国产成人高清视频 | 四虎影视在线影院在线观看 | 99国产精品国产精品 | 欧美成人自拍 | 老子影院午夜伦不卡手机 | 97se亚洲国产综合自在线观看 | 精品91在线 | a资源在线 | 亚洲综合网在线 | 一级做a爰片久久毛片唾 | 国产毛片视频网站 | 成人在线短视频 | 欧美大片aaaa一级毛片 | 色噜噜国产精品视频一区二区 | 日韩一区精品 | 91最新91精品91蝌蚪 | 酒色网站| 亚洲有色 | 免费播放欧美毛片 | 综合欧美一区二区三区 | 日本a视频| 99在线观看视频免费精品9 | 全部费免一级毛片不收费 | 欧美成人免费公开播放 | 伊人激情久久综合中文字幕 | 欧美三级做爰视频 |