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

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條評論
主站蜘蛛池模板: 亚洲精品国产第一区二区尤物 | 天天做天天爱天天爽综合网 | 香蕉尹人 | 欧美高清国产 | 国产视频福利 | 成人免费在线视频 | 欧美大片天天免费看视频 | 亚洲精品一区二区三区婷婷月 | 91中文字幕yellow字幕网 | 国产成人a视频在线观看 | 色综合久久加勒比高清88 | 天天做天天爱天天操 | 中文国产成人久久精品小说 | 尹人香蕉久久99天天拍欧美p7 | 女人精69xxxxx免费无毒 | 久久精品国内一区二区三区 | 四虎影视永久免费视频观看 | 激情综合视频 | 天天擦天天干 | 97在线视频网站 | 天天狠狠色噜噜 | 99精品久久久久久 | 亚洲中午字幕 | 伊人久久综合影院首页 | 欧美日本成人 | 久久精品国产只有精品6 | 国产欧美日韩看片片在线人成 | 亚洲韩精品欧美一区二区三区 | 婷婷国产天堂久久综合五月 | 免费日韩精品 | 天天干夜夜操视频 | 波多野结衣在线观看3人 | 欧美刺激午夜性久久久久久久 | 男女啪视频大全1000 | 日本不卡二 | 婷婷激情综合网 | 久久免费观看爱情动作片 | 中文字幕在线免费视频 | 真人毛片免费拍拍拍aa视频 | 天天操天天干天天插 | 四虎成人永久地址 |