首页 > 代码库 > HDU 4876 ZCC loves cards 暴力+剪枝
HDU 4876 ZCC loves cards 暴力+剪枝
题意:n张牌,选k个排成一圈,给出L,求出最大R 使得[L,R]内任意一个数 都可以由圈内连续m个数异或得到.
n<=20,k<=6,a[i],L<=100. m为自己设定的.
暴力 总共有A(20,6)种方案 每种方案k^2算出异或数 TLE..
先C(20,6)选出方案 若能过最优性剪支,在全排列更新答案. 注意先将a排序 使得全排列从最小序开始.
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<ll,ll> ii; const int inf=0x3f3f3f3f; const int N=25; int n,k,L,a[N],b[N],c[N],vis[N],ans; int mp[N*N]; void calc_max(int num,int sum) { mp[sum]=1; if(num==k) return; calc_max(num+1,sum^b[num]); calc_max(num+1,sum); } bool check() { memset(mp,0,sizeof(mp)); calc_max(0,0); for(int i=L;i<=ans;i++) if(!mp[i]) return false; return true; } void calc() { //i?aí· j??êyμ?òì?òoí if(!check()) return; for(int i=0;i<k;i++) c[i]=b[i]; do{ memset(mp,0,sizeof(mp)); for(int i=0;i<k;i++) { int res=0; for(int j=i;j<k+i;j++) { res^=c[(j%k)]; mp[res]=1; } } for(int i=L;i<=L+k*k;i++) { if(!mp[i]) { ans=max(ans,i-1); break; } } }while(next_permutation(c+1,c+k));// } void dfs(int now,int cur) { if(cur==k) { calc(); return; } if(now==n) return; for(int i=now;i<n;i++) { b[cur]=a[i]; dfs(i+1,cur+1); } } int main() { while(cin>>n>>k>>L) { memset(vis,0,sizeof(vis)); for(int i=0;i<n;i++) scanf("%d",&a[i]); sort(a,a+n); ans=L-1; dfs(0,0); if(ans<L) ans=0; printf("%d\n",ans); } return 0; }
HDU 4876 ZCC loves cards 暴力+剪枝
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。