首页 > 代码库 > 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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。