hdu 4876
2024-09-03 05:35:44
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.
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.
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
2 3 4 5
Sample Output
7
Hint
⊕ means xor
Author
镇海中学
Source
Recommend
搜索
首先找到k个元素后,枚举这k个元素的所有子集,看能不能超过当前得到的最大的R,如果不能,就没有必要在检查
我们容易发现 假如要选出3个元素则编号为1 2 3 2 3 1 3 1 2 这三种排列在检查时是一样的因此枚举全排列时只需要枚举全排列的1 / k即可
最后一个剪枝是 把a数组事先按从大到小排列,若枚举的第一个元素的将所有位置1都无法超过当前最大值,则没有必要从这个元素枚举下去
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <queue> using namespace std; #define read() freopen("sw.in", "r", stdin) const int MAX_N = ;
const int MAX = ( << );
int N, K, L;
struct node {
int st[];
bool operator < (const node &rhs) const {
for (int i = ; i < K; ++i) {
if (st[i] != rhs.st[i]) return st[i] < rhs.st[i];
}
return ;
}
}; int x[MAX_N];
bool vis[MAX];
int ele[MAX_N];
int _max;
int len = ;
node p[]; int cal(int n) {
int ret = ;
if (n == ) ret = ;
while (n > ) {
++ret;
n >>= ;
} return ( << ret) - ;
} void check() {
int t = , _max1 = ;
/*for (int i = 0; i < K; ++i) printf("%d ", ele[i]);
printf("\n");*/
memset(vis, , sizeof(vis));
int cnt = ;
for (int s = ; s < ( << K); ++s) {
t = ;
for (int i = ; i < K; ++i) {
if (s >> i & ) {
t ^= ele[i];
}
}
if (!vis[t]) {
vis[t] = ;
if (t >= L && t <= _max + ) ++cnt;
} _max1 = max(_max1, t);
} if (_max1 <= _max || cnt < (_max + - L)) return; for (int i = ; i < len; ++i) {
memset(vis, , sizeof(vis));
cnt = ;
for (int start = ; start < K; ++start) {
int v;
for (int l = ; l <= K; ++l) {
v = ;
for (int pos = start, num = ; num <= l; pos = (pos + ) % K, ++num)
v ^= ele[ p[i].st[pos] ];
if (!vis[ v ]) {
vis[v] = ;
if (v >= L && v <= _max + ) ++cnt;
}
} }
int k = _max + ;
if (cnt < (_max + - L)) continue;
while (vis[k] == ) ++k;
_max = max(_max, k - );
} } void dfs(int id, int num) {
if (num >= K) {
//printf("fuck\n");
check();
return ;
}
if (id >= N) return ; if (num == && cal(x[id]) <= _max) return;
ele[num] = x[id];
dfs(id + , num + );
dfs(id + , num);
} int main()
{
//read();
while (scanf("%d%d%d", &N, &K, &L) != EOF) {
for (int i = ; i < N; ++i) scanf("%d", &x[i]);
set <node> Set;
len = ;
int id[] = {, , , , , };
sort(x, x + N, greater<int>());
_max = L - ; do {
node st;
for (int i = ; i < K; ++i) st.st[i] = id[i];
if (Set.find(st) != Set.end()) continue;
// for (int i = 0; i < K; ++i) printf("%d ", id[i]);
//printf("\n");
for (int i = ; i < K; ++i) p[len].st[i] = id[i];
len++;
for (int i = ; i < K; ++i) {
for (int m = , j = i; m < K; ++m, j = (j + ) % K) {
st.st[m] = id[j];
}
Set.insert(st);
} }while (next_permutation(id, id + K)); dfs(, );
printf("%d\n", _max < L ? : _max); }
//cout << "Hello world!" << endl;
return ;
}
最新文章
- Linux 平台GCC使用小结
- linux常用命令积累
- mybatis xml 中的特殊符转义字符号和模糊查询
- Jquery ajax调用webservice总结
- Codeforces 546E Soldier and Traveling(最大流)
- js身份证验证-超级准!!!
- [LeetCode]题解(python):035-Search Insert Position
- lintcode:在二叉查找树中插入节点
- Java Concurrency - Concurrent Collections
- #BeginLibraryItem 的疑问...
- jquery mobile 栅格化
- MFC下调试日志的打印
- zf-分页后台代码
- centos7之zabbix3.2搭建
- 协方差(Covariance)
- springboot + mybatis-pagehelper 参数查询不分页的bug。。。
- 转转转![Spring MVC] - 500/404错误处理-SimpleMappingExceptionResolver
- day3.python 学习之列表
- 哦这。。!C语言scanf输入的坑爹之处
- 【探讨】linux环境,执行重启了php后php.ini依然不生效
热门文章
- C#程序猿学习 Python
- 设计模式之五:工厂方法模式(Factory Method)
- 模块化开发(三)---通过node.js学习模块化开发
- ios dyld: Library not loaded: @rpath/xxx.framework/xxx 之根本原因
- YTU 2706: 编写一个函数求最大的n值
- 预编译头文件pch
- restrict关键字
- flux,redux,vuex状态集管理工具之间的区别
- [App Store Connect帮助]三、管理 App 和版本(2.3)输入 App 信息:提供自定许可协议
- webview加载本地页面