首页 > 代码库 > hdu4876
hdu4876
题意：有n（<=20）个数，在n个数中挑出k(<=6)个数组成一个环。给出一个L，这个环中的数（可以是1个，2个....k个）异或操作（只能是连续的几个数异或）会得到一系列的值，求这些值包含L并且向L+1,L+2延伸，所能取到的最大R。（L--R之间所有的数都必须取得到）
基础思路：就是先取出k个数，然后对这k个数进行全排列，在去找最大的R--这样必然超时。
标程给出的思路：先取k个数，最多有C(20,6)种取法，但是这些取法中有绝大部分是不符合要求的，这样，可以先不进行全排列，先对这6个数进行异或操作，把所有可以取得到的抑或值全部取出来，然后求出它最长的连续的包含L的r，然后与最终的结果R比较（R一开始等于L-1），如果这样取得到的r还<=R，那么这一组取法肯定是不行的。
如果r>R，那么就对这取得的k个数进行全排列，这里需要注意，在全排列的时候，由于k个数组成一个圆，那么只要对第一个数之后的k-1个数进行全排列就好，如果不这样，那么超时无疑。
然后找出一个符合条件的r,如果这个r大于R，那么我们需要更新R（也就是一边搜索，一遍把已经搜索到的结果拿来剪枝）。
我自己按照标程给出的思路编写的时候，TLE\WA了一整天，弄得都快崩溃了--最后还是ac了，然后发现是自己sb了。。。。。
反思：在进行取数的时候，在比赛时，我是用dfs回溯写的，时间复杂度那叫一个大，是队友提醒不用回溯的......这里也2b了，话说不就是取与不取的关系么？回溯干嘛呢？
在写取连续的值的时候，我是少取了一些数，虽然测出来了，但是这不是应该出现的错误，一个圈的话，那不只是取到最后一个数就可以了，要取完一个圈。
ac代码：
#include<iostream>#include<cstdio>#include<cstring>#include<vector>using namespace std;const int inf=300;int n,m,ll,maxn;int s[inf];int tol[53259][8],f[8],cnt=0;bool vist[inf],p[inf];int xx[17500][8],cntx=0;bool zt[(2<<8)];void dfs(int num,int step) //取k个数，C(n,k){ if(step==m) { for(int i=0; i<m; i++) tol[cnt][i]=f[i]; cnt++; return; } if(num>n) return; dfs(num+1,step); //取，或者不取，吐槽一下，为什么我总喜欢写 f[step]=s[num]; //for循环？这绝对是做记忆化搜索留下的 dfs(num+1,step+1);}void dfs1(int wz,int num,int ans) //标记k个数，所有能取到的异或值{ p[ans]=true; if(wz==m) return; if(wz>m) return; dfs1(wz+1,num,ans); dfs1(wz+1,num,ans^tol[num][wz]);}void dfs2(int num,int step) //求全排列，这里是绝对要回溯的{ if(step>0&&!vist[0]) return; //这样是表示，第一个数是固定的 if(step==m) //由于是一个圈，所以，只需要求出 { //后面k-1个数的全排列就好 for(int i=0;i<m;i++) xx[cntx][i]=f[i]; cntx++; return; } for(int i=0;i<m;i++) { if(!vist[i]) { vist[i]=true; f[step]=tol[num][i]; dfs2(num,step+1); vist[i]=false; } }}void deal(int num) //这是求连续的抑或值{ int ans=0; for(int i=0;i<m;i++) { int ans=xx[num][i]; vist[ans]=true; int j=1,h=i+j; while(1) //一开始这里2b了，写成了for(j=i+1;j<m;j++),少取了很多数据 { if(j==m) break; ans^=xx[num][h%m]; vist[ans]=true; j++; h=i+j; } }}int main(){ while(scanf("%d%d%d",&n,&m,&ll)>0) { for(int i=1;i<=n;i++) scanf("%d",&s[i]); cnt=0; dfs(1,0); //printf("dfs\n"); int rr=ll-1; //初始化rr，一开始应该等于ll-1 for(int i=0;i<cnt;i++) { memset(p,false,sizeof(p)); maxn=ll-1; dfs1(0,i,0); memset(vist,false,sizeof(vist)); for(int j=ll;j<=150;j++) { if(p[j]) maxn++; else break; } if(maxn<=rr) continue; //剪枝，rr表示最终的结果 cntx=0; dfs2(i,0); for(int j=0;j<cntx;j++) { int right=ll-1; memset(vist,false,sizeof(vist)); deal(j); for(int k=ll;k<=150;k++) { if(vist[k]) right++; else break; } if(rr<right) rr=right; //更新rr值 } } if(rr<ll) printf("0\n"); else printf("%d\n",rr); } return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。