神奇的位操作

&, |, ^.<<, >>

1.快速判重。　　数组A， B分别由 010111, 111001, 取& 为 010001，即为相同。（如果用数组，所用空间为此方法的n倍，具体使用利弊看具体问题）

2.快速取状态　　数组A， B分别由 010111, 111001, A的第3个数是否为一：A & (1 << (3-1)) .

3.状态快速相加。数组A， B分别由 010111, 111001，和状态为　　A | B = 　　111111。

适用: 数组暴力，枚举的只是状态（1 or 0）。

例: uva 690 流水线，

　　每个unit不能同一时刻处理两个程序。状态：有程序和没程序。暴力dfs加剪枝。暴力枚举每个程序的起始时间，然而中间处理过程太过繁琐，且优化不算明显故超时。看题解得：枚举当前所需要考虑的长度编号与上一个的起始时间的相差时间（提前处理不能枚举的数据），另取数组保留当前状态（而不是储存起始时间）。

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <queue>
 5 #include <algorithm>
 6 #include <cstdlib>
 7 #include <iostream>
 8 #include <map>
 9 #include <set>
10 #define LL long long
11 #include <vector>
12 #define mst(a, b) memset(a, b, sizeof(a))
13 //freopen(in.txt, "r", stdin);
14 //freopen(out.txt, "w", stdout);
15 using namespace std;
16 int n, unit[6], jump[25], num_jump, ans;
17 bool Judge(int *A, int x)
18 {
19     for(int i = 0; i < 5; i++)
20     {
21         if((A[i] >> x) & unit[i]) return false; //one unit has only one program
22     }
23     return true;
24 }
25 void init()
26 {
27     char str[25];
28     for(int i = 0; i < 5; i++)
29     {
30         scanf("%s", str);
31         for(int j = 0; j < n; j++)
32         {
33             if(str[j] == 'X') unit[i] |= (1 << j);
34         }
35     }
36     num_jump  =0;
37     for(int i = 0; i <= n; i++)
38     {
39         if(Judge(unit, i))
40             jump[num_jump++] = i;
41     }
42 
43 }
44 
45 bool dfs(int *A, int cur, int sum)
46 {
47     if(sum + jump[0] * (10 - cur) > ans) return false;
48     if(cur == 10)
49     {
50         ans = min(ans, sum);
51         return true;
52     }
53     for(int i = 0; i < num_jump; i++)
54     {
55         if(Judge(A, jump[i]))
56         {
57             int B[6];
58             for(int j = 0; j < 5; j++)
59             {
60                 B[j] = (A[j] >> jump[i]) ^ unit[j];
61             }
62             dfs(B, cur+1, sum + jump[i]);
63         }
64     }
65     return false;
66 }
67 int main()
68 {
69     while(scanf("%d", &n) != EOF && n)
70     {
71         mst(unit, 0);
72         mst(jump, 0);
73         init();
74 //        int A[6] = {0};
75 //        memcpy(A, unit, sizeof(unit));
76         ans = n * 10;
77         dfs(unit, 1, n);
78         printf("%d
", ans);
79     }
80     return 0;
81 }

View Code

：数据小可暴力枚举，状态储存。

神奇操作：

1. 获得该数上的1的个数： int nums(int m) { return m == 0 ? 0 : nums(m / 2) + (m & 1); }

2. 获得1的最低位　　　　　　int lowbit(int x) { return x & -x; }　　