算法竞赛进阶指南-基本算法_常见竞赛算法

二进制状态压缩

• 二进制状态压缩，是指将一个长度为m的bool数组用一个m位二进制整数表示并存储的方法。理由下列位运算操作可以实现原bool数组中对应下标元素的存取。
• 取出整数n在二进制表示下的第k位(从右往左) （n >> k) & 1
• 取出整数n在二进制表示下的第0~k-1位 ，n & ((1 << k) - 1)
• 把整数n在二进制表示下的第k为取反 ，n ^ (1 << k)
• 把整数n在二进制表示下的第k为赋值为0，n & (~（1 << k))

lowbit运算

• lowbit(n)定义为非负整数n在二进制表示下“最低位的1及其后边所有的0”构成的数值。例如n=10的二进制表示为1010，则lowbit(n) = 2 = ‘10’，
• lowbit(n) = n & (~n +1) = n & (-n)
  (树状数组的一个基本运算)

• lowbit运算配合Hash可以找出整数二进制表示下所有是1的位，所花费的时间与1的个数同级。
• 为了打到这一目的，只需不断把n赋值为n - lowbit(n)，直到n==0.

例如： n = 9 = ‘1001’，则lowbit(9) = 1

1. 把n赋值为9 - lowbit(9) = 8 = ‘1000’，此时8 - lowbit(8) = 0，停止循环。
2. 在整个过程中我们减掉1和8（‘1000’）两个数，他们恰好是n每一位上的1后面补0的数值。
3. 取1和8的对数，log2 1和 log2 8(以2为底)，即可知n的第0位和第3位都是1.

java里的log函数是以e为底的，并且复杂度常数较大。所以想要取以2为底，可以使用换底公式，但是这样复杂度还是很高。

• 可以通过预处理一个数组，通过hash的方法代替log运算。
• 当n很小的时候可以直接建立一个数组H，令H[2^k] = k。

 			int maxN = 1 << 20;
	       int[] H = new int[maxN+1];
	       for (int i = 0; i <= 20; i++) {
	           H[1 << i] = i;
	       }
	       int n = 100;
	
	       while (n > 0) {
	           System.out.println(H[n & -n]);
	           n = n - (n & -n);
	       }
1
2
3
4
5
6
7
8
9
10
11

稍微复杂但效率更高的方法是建立一个长度为37的数组H，令H[2^k mod 37] = k。这里利用率一个数学小技巧：对于任意 k属于[0,35]，2^k mod 37互不相等，且恰好取遍整数1~36.

		int[] H = new int[37];
        for (int i = 0; i < 36; i++) {
            H[(int) (((long)1 << i) % 37)] = i;
        }
        int n = 100;

        while (n > 0) {
            System.out.println(H[(n & -n) % 37]);
            n = n - (n & -n);
        }
1
2
3
4
5
6
7
8
9
10

递归和递推

• 以已知的“问题边界”为起点向“原问题”正向推到的扩展方式就是递推。
• 很多时候正向推到的路线很难找到，这时以“原问题”为起点尝试寻找把状态空间缩小到已知的“问题边界”的路线，在通过该路线反向回溯的遍历方式就是递归。

在使用枚举算法蛮力探索为的整个“状态空间”时，经常需要递归。按照规模大小，有如下几种常见的枚举形式和遍历方式。

前缀和与差分

前缀和

对于一个给定的数列A，它的前缀和数列S是通过递推能求出的基本信息之一：
$$S[i]=\sum _{i=1}^{r}A[j]$$一部分和，即数列A某个下标区间内的数的和，可表示为前缀和相减的形式：
$$sum(l,r)=\sum _{i=1}^{r}A[i]=S[r]-S[l-1]$$在二维数组（矩阵）中，可类似地求出二维前缀和，进一步计算出二维部分和。

差分

对于一个给定的数列A，它的差分数列B定义为：
$$B[1]=A[1],B[i]=A[i]-A[i-1]（2<=i<=n）$$容易发现，“前缀和”和“差分”是一对互逆运算，差分序列B的前缀和序列就是原序列A，前缀合序列S的差分序列也是原序列A。