uva 1326 Jurassic Remains(中途相遇法)-白红宇

uva 1326 Jurassic Remains(中途相遇法)

阅读量：4073 次

发布时间：2019-05-25

本文共 2430 字，大约阅读时间需要 8 分钟。

：

题目大意：

给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
   
    #include
    
     #include
     
      #include
      
       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

代码2：中途相遇法（递归版本）：

#include
   
    #include
    
     #include
     #include
      
       using namespace std;const int MAXN = 30;int n, vis;int st[MAXN];char str[MAXN];map
       
        table;map
        
         ::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<
         
          second); if(cnt > ansCnt){ ansCnt = cnt; ansVis = vis+table[sta]; } } if(cur < n){ dfs2(cur+1, n, vis|(1<
          
           >1), 0, 0); ansCnt=0, ansVis=0; dfs2(n/2, n, 0, 0); printf("%d\n", ansCnt); bool first=true; for(i=0; i
           
            >i)&1){ first ? first=false : putchar(' '); printf("%d", i+1); } putchar('\n'); } return 0;}

版本3中途相遇法（直接枚举二进制的状态而不用递归）：

#include
   
    #include
    
     #include
     #include
      
       using namespace std;const int MAXN = 30;int n, vis;int st[MAXN];char str[MAXN];map
       
        table;map
        
         ::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
         
          >1)); for(i=0; i
          
           >1); ++j)if(i & (1<
           
            second) < bitCount(i)){ it->second = i; } }else{ table[sta] = i; } } ansCnt=0, ansVis=0; end = (1<<(n-n/2)); for(i=0; i
            
             >1); j
             
              >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
              
               >i)&1){ first ? first=false : putchar(' '); printf("%d", i+1); } putchar('\n'); } return 0;}

你可能感兴趣的文章