題目鏈接 :
題目大意:
給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; }
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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