uvalive2965Jurassic Remains

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

分析：暴力枚举O（2ⁿ）不行。采用密码学中的中途相遇攻击原理，用stl的map实现：先取得前一半的判断结果然后后一般在前一半的基础上判断

代码：

View Code

 1 #pragma warning(disable:4786)
 2 #include <stdio.h>
 3 #include <map>
 4 #define DEBUG
 5 using namespace std;
 6 
 7 const int MAXN = 24;
 8 map<int , int>table;
 9 int bitcount(int x){
10     return x==0?0:bitcount(x/2)+(x&1);
11 }
12 int main(){
13 #ifndef DEBUG
14     freopen("in.txt", "r", stdin);
15 #endif
16     int n, A[MAXN];
17     char s[1000];
18 
19     while(scanf("%d", &n)!=EOF && n){
20         int i, j;
21         for(i=0; i<n; i++){
22             scanf("%s", s);
23             A[i]=0;
24             for(j=0; s[j]!='\0'; j++) A[i]^=(1<<(s[j]-'A'));
25         }
26 
27         table.clear();
28         int n1=n/2, n2=n-n1;
29         for(i=0; i<(1<<n1); i++){
30             int x=0;
31             for(j=0; j<n1; j++) if(i&(1<<j)) x^=A[j];
32             if(!table.count(x) || bitcount(table[x])<bitcount(i)) table[x]=i;
33         }
34 
35         int ans=0;
36         for(i=0; i<(1<<n2); i++){
37             int y=0;
38             for(j=0; j<n2; j++) if(i&(1<<j)) y^=A[n1+j];
39             if(table.count(y)&&bitcount(ans)<bitcount(table[y])+bitcount(i))
40                 ans=(i<<n1)^table[y];
41         }
42 
43         printf("%d\n", bitcount(ans));
44         for(i=0; i<n; i++) if(ans&(1<<i)) printf("%d ", i+1);
45         printf("\n");
46     }
47     return 0;
48 }

代码中 if(i&(1<<j))的意思大概是这样的：（它本身的意思自己去想吧），在这两重循环中（i&（1<<j))为1的次数是sigma(2^k), k=0..n2

这应当就是简单暴力的缩小范围的模拟吧~

Greatness is never a given, it must be earned.