题目链接:hdu 4876 ZCC loves cards
题目大意:给出n,k,l,表示有n张牌,每张牌有值。选取其中k张排列成圈,然后在该圈上进行游戏,每次选取m(1≤m≤k)张连续的牌,取牌上值的亦或和。要求找到一个圈,使得L~R之间的数都可以得到,输出R。如果R < L输出0.
解题思路:暴力,首先预处理出来每种选取的亦或值,然后在该基础上从可以组成L的状态中挑选一个,L+1的状态中挑取一个,知道说总的挑取出所有状态中选中的牌的个数大于K为值,然后用全排序去查找最大的R。
#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 200;
const int maxc = 25;
const int maxs = 1<<20;
const int maxt = 20005;
bool flag;
int ans, rec, dp[maxs+5];
int N, K, L, arr[maxc];
int vec[maxn][maxt], c[maxn];
inline int bitcount (int s) {
return s == 0 ? 0 : bitcount(s/2) + (s&1);
}
void dfs (int d, int s, int val, int f) {
if (d == K + 1)
return;
vec[val][c[val]++] = s;
for (int i = f + 1; i < N; i++)
dfs (d+1, s|(1<<i), val^arr[i], i);
}
void init () {
flag = true;
ans = rec = 0;
memset(c, 0, sizeof(c));
memset(dp, 0, sizeof(dp));
for (int i = 0; i < N; i++)
scanf("%d", &arr[i]);
dfs(0, 0, 0, -1);
}
int check (int* a) {
int v[maxn];
memset(v, 0, sizeof(v));
for (int m = 1; m <= K; m++) {
int tmp = a[0];
for (int i = 1; i < m; i++)
tmp ^= a[i];
for (int i = 0; i < K; i++) {
v[tmp] = 1;
tmp ^= (a[i] ^ a[i+m]);
}
}
int ans = L;
while (v[ans] && ans < maxn)
ans++;
return ans - 1;
}
void judge (int s) {
int cnt = 0, a[2*maxn];
for (int i = 0; i < N; i++) {
if (s&(1<<i))
a[cnt++] = arr[i];
}
sort(a + 1, a + cnt);
do {
for (int i = 0; i < cnt; i++)
a[i+cnt] = a[i];
ans = max(ans, check(a));
} while (next_permutation(a + 1, a + cnt));
}
void solve (int d, int s) {
int cnt = bitcount(s);
rec = max(d, rec);
if (cnt >= K || d >= maxn) {
if (cnt == K) {
judge(s);
flag = false;
}
return;
}
for (int i = 0; i < c[d]; i++) {
int s0 = (s | vec[d][i]);
if (dp[s0]) continue;
solve(d+1, s0);
dp[s0] = 1;
}
}
int main () {
while (scanf("%d%d%d", &N, &K, &L) == 3) {
init();
solve(L, 0);
if (flag)
ans = rec - 1;
printf("%d\n", ans < L ? 0 : ans);
}
return 0;
}
分享到:
相关推荐
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类
HDU图论题目分类
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
Hdu 1237 解题代码