当前位置:   article > 正文

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

常见竞赛算法

二进制状态压缩

  • 二进制状态压缩,是指将一个长度为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

递归和递推

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

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

枚举形式状态空间规模一般遍历方式
多项式n^k, k为常数循环for、递推
指数k^n,k为常数递归、位运算
排列n!递归
组合C m n递归+剪枝

前缀和与差分

前缀和

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

差分

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

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/728754
推荐阅读
相关标签
  

闽ICP备14008679号