首页 > 代码库 > hdu 4876

hdu 4876

2024-07-13 22:36:41   225人阅读

ZCC loves cards

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 828    Accepted Submission(s): 184


Problem Description
ZCC loves playing cards. He has n magical cards and each has a number on it. He wants to choose k cards and place them around in any order to form a circle. He can choose any several consecutive cards the number of which is m(1<=m<=k) to play a magic. The magic is simple that ZCC can get a number x=a1⊕a2...⊕am, which ai means the number on the ith card he chooses. He can play the magic infinite times, but once he begin to play the magic, he can’t change anything in the card circle including the order.
ZCC has a lucky number L. ZCC want to obtain the number L~R by using one card circle. And if he can get other numbers which aren’t in the range [L,R], it doesn’t matter. Help him to find the maximal R.
 

 

Input
The input contains several test cases.The first line in each case contains three integers n, k and L(k≤n≤20,1≤k≤6,1≤L≤100). The next line contains n numbers means the numbers on the n cards. The ith number a[i] satisfies 1≤a[i]≤100.
You can assume that all the test case generated randomly.
 

 

Output
For each test case, output the maximal number R. And if L can’t be obtained, output 0.
 

 

Sample Input
4 3 12 3 4 5
 

 

Sample Output
7
Hint
⊕ means xor
 

 

Author
镇海中学
 

 

Source
2014 Multi-University Training Contest 2
 

 

Recommend
We have carefully selected several similar problems for you:  4882 4881 4880 4879 4878 
 
搜索
首先找到k个元素后，枚举这k个元素的所有子集，看能不能超过当前得到的最大的R，如果不能，就没有必要在检查
我们容易发现 假如要选出3个元素则编号为1 2 3   2 3 1   3 1 2 这三种排列在检查时是一样的因此枚举全排列时只需要枚举全排列的1 / k即可
最后一个剪枝是 把a数组事先按从大到小排列，若枚举的第一个元素的将所有位置1都无法超过当前最大值，则没有必要从这个元素枚举下去
 
  1 #include <iostream>  2 #include <cstdio>  3 #include <cstring>  4 #include <algorithm>  5 #include <cmath>  6 #include <set>  7 #include <map>  8 #include <queue>  9  10 using namespace std; 11  12 #define read() freopen("sw.in", "r", stdin) 13  14 const int MAX_N = 25; 15 const int MAX = (1 << 7); 16 int N, K, L; 17 struct node { 18         int st[6]; 19         bool operator < (const node &rhs) const { 20                 for (int i = 0; i < K; ++i) { 21                         if (st[i] != rhs.st[i]) return st[i] < rhs.st[i]; 22                 } 23                 return 0; 24         } 25 }; 26  27 int x[MAX_N]; 28 bool vis[MAX]; 29 int ele[MAX_N]; 30 int _max; 31 int len = 0; 32 node p[720]; 33  34  35 int cal(int n) { 36         int ret = 0; 37         if (n == 0) ret = 1; 38         while (n > 0) { 39                 ++ret; 40                 n >>= 1; 41         } 42  43         return (1 << ret) - 1; 44 } 45  46 void check() { 47         int t = 0, _max1 = 0; 48         /*for (int i = 0; i < K; ++i) printf("%d ", ele[i]); 49         printf("\n");*/ 50         memset(vis, 0, sizeof(vis)); 51         int cnt = 0; 52         for (int s = 0; s < (1 << K); ++s) { 53                 t = 0; 54                 for (int i = 0; i < K; ++i) { 55                         if (s >> i & 1) { 56                                 t ^= ele[i]; 57                         } 58                 } 59                 if (!vis[t]) { 60                         vis[t] = 1; 61                         if (t >= L && t <= _max + 1) ++cnt; 62                 } 63  64                 _max1 = max(_max1, t); 65         } 66  67         if (_max1 <= _max || cnt < (_max + 2 - L)) return; 68  69         for (int i = 0; i < len; ++i) { 70                 memset(vis, 0, sizeof(vis)); 71                 cnt = 0; 72                 for (int start = 0; start < K; ++start) { 73                         int v; 74                         for (int l = 1; l <= K; ++l) { 75                                 v = 0; 76                                 for (int pos = start, num = 1; num <= l; pos = (pos + 1) % K, ++num) 77                                 v ^= ele[ p[i].st[pos] ]; 78                                 if (!vis[ v ]) { 79                                         vis[v] = 1; 80                                         if (v >= L && v <= _max + 1) ++cnt; 81                                 } 82                         } 83  84                 } 85                 int k = _max + 1; 86                 if (cnt < (_max + 2 - L)) continue; 87                 while (vis[k] == 1) ++k; 88                 _max = max(_max, k - 1); 89         } 90  91  92  93  94 } 95  96 void dfs(int id, int num) { 97         if (num >= K) { 98                 //printf("fuck\n"); 99                 check();100                 return ;101         }102         if (id >= N) return ;103 104         if (num == 0 && cal(x[id]) <= _max)  return;105         ele[num] = x[id];106         dfs(id + 1, num + 1);107         dfs(id + 1, num);108 }109 110 111 112 int main()113 {114     //read();115     while (scanf("%d%d%d", &N, &K, &L) != EOF) {116             for (int i = 0; i < N; ++i) scanf("%d", &x[i]);117             set <node> Set;118             len = 0;119             int id[6] = {0, 1, 2, 3, 4, 5};120             sort(x, x + N, greater<int>());121             _max = L - 1;122 123             do {124                     node st;125                     for (int i = 0; i < K; ++i) st.st[i] = id[i];126                     if (Set.find(st) != Set.end()) continue;127                    // for (int i = 0; i < K; ++i) printf("%d ", id[i]);128                     //printf("\n");129                     for (int i = 0; i < K; ++i) p[len].st[i] = id[i];130                     len++;131                     for (int i = 0; i < K; ++i) {132                             for (int m = 0, j = i; m < K; ++m, j = (j + 1) % K) {133                                     st.st[m] = id[j];134                             }135                             Set.insert(st);136                     }137 138             }while (next_permutation(id, id + K));139 140             dfs(0, 0);141             printf("%d\n", _max < L ? 0 : _max);142 143 144     }145     //cout << "Hello world!" << endl;146     return 0;147 }
View Code

 

 


联系
我们