首页 > 代码库 > LA 2965 Jurassic Remains
LA 2965 Jurassic Remains
这是我做的第一道状态压缩的题目,而且我自己居然看懂了,理解得还算透彻。
题意:给出若干个大写字母组成的字符串,然后选取尽量多的字符串使得这些字母出现偶数次。
最朴素的想法,穷举法:每个字符串只有选和不选两种情况,那么穷举的时间复杂度是O(2n)
优化:将这n个字符串分成两半,先后枚举前n1个字符串所有可能的情况,计算xor值并保存在table中
再枚举后半部分的xor值并在table中查找(因为如果两者的异或值相同,则进行异或运算后的值为0),如果找到,将ans更新为bitcount较大的那种方案。
1 //#define LOCAL 2 #include <cstdio> 3 #include <map> 4 using namespace std; 5 6 const int maxn = 24; 7 map<int, int> table; 8 9 int bitcount(int x)10 {//求x对应二进制中1的个数11 return (x == 0 ? 0 : (x&1) + bitcount(x>>1)); 12 }13 14 int main(void)15 {16 #ifdef LOCAL17 freopen("2965in.txt", "r", stdin);18 #endif19 20 int n, a[maxn];21 char s[1000];22 while(scanf("%d", &n) == 1 && n)23 {24 for(int i = 0; i < n; ++i)25 {26 scanf("%s", s);27 a[i] = 0;28 for(int j = 0; s[j] !=‘\0‘; ++j) //a[i]为字符串对应的二进制向量29 a[i] ^= (1 << (s[j] - ‘A‘));30 }31 int n1 = n / 2, n2 = n - n1;32 33 //枚举前n1个字符串所有可能组成的异或值34 table.clear();35 for(int i = 0; i < (1 << n1); ++i)36 {37 int x = 0;38 for(int j = 0; j < n1; ++j)39 if(i & (1 << j))40 x ^= a[j];41 if(!table.count(x) || bitcount(table[x]) < bitcount(i))42 //如果x没有重复或者xor值相同在第i中情况下选择的字符串更多43 table[x] = i;44 }45 //枚举后n2个元素所有组合情况并在table中查找46 int ans = 0;47 for(int i = 0; i < (1 << n2); ++i)48 {49 int x = 0;50 for(int j = 0; j < n2; ++j)51 if(i & (1 << j))52 x ^= a[n1 + j];53 if(table.count(x) && bitcount(ans) < (bitcount(table[x]) + bitcount(i)))54 //x值存在 且 该方案下所选的字符串更多,更新ans的值55 ans = (i << n1) ^ table[x];56 }57 //输出结果58 printf("%d\n", bitcount(ans));59 for(int i = 0; i < n; ++i)60 {61 if(ans & (1 << i))62 printf("%d ", i + 1);63 }64 printf("\n");65 }66 return 0;67 }
这里顺便还模糊地学习了一下map的用法。。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。