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
");
107         else 
108         printf("%d
",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     do
28     {
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_permutation
74 
75         R=-1;
76         dfs(0,0);
77         if(R<L)
78             printf("0
");
79         else
80             printf("%d
",R);
81     }
82     return 0;
83 }