hdu 4876

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 1 2 3 4 5

Sample Output

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("
");*/
 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
");
 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("
");
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
", _max < L ? 0 : _max);
142 
143 
144     }
145     //cout << "Hello world!" << endl;
146     return 0;
147 }

View Code