首页 > 代码库 > hdu 4876 暴力剪枝
hdu 4876 暴力剪枝
hdu 4876 终于过了， 之前写的代码虽然思路是这样的但是有好多可以优化的地方没有注意所以一直超时超时超时！，学习了一下别人的代码，虽然看上去没什么差别但实际上却可以节省很多时间，恩恩又学到了一些技巧~ ^_^ 。
【题意】：给定一些卡片，每个卡片上有数字，现在选k个卡片，绕成一个环，每次可以再这个环上连续选1 - k张卡片，得到他们的异或和的数，给定一个L，问能组成[L,R]所有数字的情况下，R的最大值是多少.
【思路】：暴力+剪枝 枚举在m个数里选k个数的 C(m,k)种情况，但是要先判断一下，再判断一下要不要把这个组合再排成A(k,k)种序列，这个判断就可以剪枝，要是这这个组合可以得到的所有异或值里的最大都不比上一次得到的R值大。就
写的第一个超时代码
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 int k,L,R,n,m,t; 7 bool vis[22],vis1[22]; 8 int a[22],temp[22]; 9 int xorr[100],huan[102]; 10 11 void dfs1(int step) 12 { 13 if(step==k)//d得到这个顺序的所有异或值 14 { 15 int num=0; 16 17 for(int j=0; j<k; j++) 18 { 19 int tempxor=0; 20 for(int p=0; p<k; p++) 21 { 22 tempxor^=huan[(j+p)%k]; 23 xorr[num++]=tempxor; 24 } 25 } 26 sort(xorr,xorr+num); 27 int *wei; 28 int tempR=0; 29 wei=unique(xorr,xorr+num); 30 31 bool flag=false; 32 for(int *j=xorr; j<=wei; j++) 33 { 34 if(flag) 35 { 36 if((*j-1)==tempR) 37 tempR++; 38 else break; //中间跳了一个 39 } 40 if((*j)==L) 41 { 42 flag=true; 43 tempR=L; 44 } 45 } 46 if(tempR>R) 47 R=tempR; 48 return ; 49 } 50 for(int i=0; i<k; i++) 51 { 52 if(!vis1[i]) 53 { 54 55 huan[step]=temp[i]; 56 vis1[i]=true; 57 dfs1(step+1); 58 vis1[i]=false; 59 } 60 } 61 } 62 63 void zhankai() 64 { 65 memset(vis1,false,sizeof(vis1)); 66 dfs1(0); 67 } 68 69 void dfs(int x,int p) 70 { 71 if(x==k) 72 { 73 int maxx=0; 74 for( int p=0; p<(1<<k); p++) 75 { 76 int yihuo=0;//得到每个子集的亦或值 77 for(int q=0; q<k; q++) 78 if((1<<q)&p) 79 yihuo^=temp[q]; 80 if(maxx<yihuo) 81 maxx=yihuo; 82 } 83 if(maxx>R) 84 zhankai(); 85 } 86 for(int i=p; i<n; i++) 87 if(!vis[i]) 88 { 89 temp[x]=a[i]; 90 vis[i]=true; 91 dfs(x+1,i+1); 92 vis[i]=false; 93 } 94 } 95 96 int main() 97 { 98 while(~scanf("%d%d%d",&n,&k,&L)) 99 {100 for(int i=0; i<n; i++)101 scanf("%d",&a[i]);102 memset(vis,false,sizeof(vis));103 R=-1;104 dfs(0,0);105 if(L>R)106 printf("0\n");107 else 108 printf("%d\n",R);109 }110 return 0;111 }
修改后的：
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 int k,L,R,n,m,t; 7 bool vis4[202],v[1002]; 8 int a[22],temp[22]; 9 int huan[102],kl[7];10 bool xorr[100002];11 12 void dfs1(int num,int sum) //!!!13 {14 vis4[sum]=true;15 if(num==k)16 return ;17 dfs1(num+1,sum^temp[num]); //每个点都可以选择加入异或 或者不异或 共2^k种18 dfs1(num+1,sum);19 }20 21 22 void zhankai()23 {24 int have[202];25 for (int i = 0; i < k; i++)26 have[i] = temp[i];27 do28 {29 memset(v, 0, sizeof(v));30 for (int i = 0; i < k; i++)31 {32 int ans = 0;33 for (int j = i; j < k + i; j++)//!!!! 这里j没必要从0开始34 {35 ans ^= have[(j % k)];36 v[ans] = 1;37 }38 }39 for (int i = L; i <= L + k * k; i++)40 if (!v[i])41 {42 R = max(R, i - 1);43 break;44 }45 }46 while(next_permutation(have + 1, have + k)); //!!直接调函数枚举每个序列 47 }48 49 void dfs(int x,int p)50 {51 if(x==k)52 {53 memset(vis4,false,sizeof(vis4));54 dfs1(0,0); // 之前我的方法 用的时间是(2^k)*k 这个只要2^k，而且代码还特简洁;55 for(int i=L; i<=R; i++)56 if(!vis4[i])57 return ; //！！ 这里不是找最大值而是找是否可以连续覆盖，写起来有简单点58 zhankai();59 }60 for(int i=p; i<n; i++)61 {62 temp[x]=a[i];63 dfs(x+1,i+1);64 }65 }66 67 int main()68 {69 while(~scanf("%d%d%d",&n,&k,&L))70 {71 for(int i=0; i<n; i++)72 scanf("%d",&a[i]);73 sort(a,a+n);//!!!!!拍完学后 dfs得到的是这个组合的最小序，枚举该组合的所有序列可以方便的使用 next_permutation74 75 R=-1;76 dfs(0,0);77 if(R<L)78 printf("0\n");79 else80 printf("%d\n",R);81 }82 return 0;83 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。