HDU 4876 ZCC loves cards

题目链接

题意：给定一些卡片，每个卡片上有数字，现在选k个卡片，绕成一个环，每次可以再这个环上连续选1 - k张卡片，得到他们的异或和的数，给定一个L，问能组成[L,R]所有数字的情况下，R的最大值是多少

思路：暴力C(20, 6)，然后对于每个序列去全排后模拟计算值， 不过之前要有个剪枝，全排前，先把k个数随机取数（即不用连续），然后如果这样还满足不了，那么连续的情况肯定也满足不了，直接结束，不进入全排。这样一来由于满足不了的情况实际上是占绝大多数的，所以总体的时间复杂度不会很高，又由于这题是随机数据，所以还是能过的

代码：

#include 
  
   
#include 
   
     #include 
    
      using namespace std; int n, k, l, r, a[25], save[25], have[25], v[205], Max, vis[205]; void calmax(int num, int sum) { vis[sum] = 1; if (num == k) return; calmax(num + 1, sum ^ save[num]); calmax(num + 1, sum); } bool Maxcal() { memset(vis, 0, sizeof(vis)); calmax(0, 0); for (int i = l; i <= r; i++) if (!vis[i]) return false; return true; } void cal() { if (!Maxcal()) return; for (int i = 0; i < k; i++) have[i] = save[i]; do { memset(v, 0, sizeof(v)); for (int i = 0; i < k; i++) { int ans = 0; for (int j = i; j < k + i; j++) { ans ^= have[(j % k)]; v[ans] = 1; } } for (int i = l; i <= l + k * k; i++) if (!v[i]) { r = max(r, i - 1); break; } } while(next_permutation(have + 1, have + k)); } void dfs(int now, int num) { if (num == k) { cal(); return; } for (int i = now; i < n; i++) { save[num] = a[i]; dfs(i + 1, num + 1); } } int main() { while (~scanf("%d%d%d", &n, &k, &l)) { for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); r = l - 1; dfs(0, 0); if (r < l) printf("0\n"); else printf("%d\n", r); } return 0; }