首页 > 代码库 > HDU 4876 ZCC loves cards(暴力剪枝)

HDU 4876 ZCC loves cards(暴力剪枝)

HDU 4876 ZCC loves cards

题目链接

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

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

代码:

#include <cstdio>
#include <cstring>
#include <algorithm>
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;
}