算法合集之《浅谈数位类统计问题》

《算法合集之《浅谈数位类统计问题》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浅谈数位类问题刘聪浅谈数位类统计问题山东省青岛第二中学刘聪【摘要】在信息学竞赛中，有一类与数位有关的区间统计问题。这类问题往往具有比较浓厚的数学味道，无法暴力求解，需要在数位上进行递推等操作。本文通过几个例子，简要介绍了解决此类问题的基本思想和方法。【关键字】数位区间统计递推树二进制【正文】在信息学竞赛中，有这样一类问题：求给定区间中，满足给定条件的某个D进制数或此类数的数量。所求的限定条件往往与数位有关，例如数位之和、指定数码个数、数的大小顺序分组等等。题目给定的区间往往很大，无法采用朴素的方法求解。此时，我们就需要利

2、用数位的性质，设计log(n)级别复杂度的算法。解决这类问题最基本的思想就是“逐位确定”的方法。下面就让我们通过几道例题来具体了解一下这类问题及其思考方法。【例题1】Amountofdegrees(ural1057)题目大意：求给定区间[X,Y]中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意：4017=2+2，4118=2+2，4220=2+2。输入：第一行包含两个整数X和Y。接下来两行包含整数K和B。输出：只包含一个整数，

3、表示满足条件的数的个数。31数据规模：1≤X≤Y≤2−1，1≤K≤20，2≤B≤10。分析：所求的数为互不相等的幂之和，亦即其B进制表示的各位数字都只能是0和1。因此，我们只需讨论二进制的情况，其他进制都可以转化为二进制求解。很显然，数据范围较大，不可能采用枚举法，算法复杂度必须是log(n)级别，因此我们要从数位上下手。第1页，共12页浅谈数位类问题刘聪本题区间满足区间减法，因此可以进一步简化问题：令count[i..j]表示[i..j]区间内合法数的个数，则count[i..j]=count[0..j]-count[

4、0..i-1]。换句话说，给定n，我们只需求出从0到n有多少个符合条件的数。假设n=13，其二进制表示为1101，K=3。我们的目标是求出0到13中二进制表示含3个1的数的个数。为了方便思考，让我们画出一棵高度为4的完全二叉树：0010101010101010101010101010101为了方便起见，树的根用0表示。这样，这棵高度为4的完全二叉树就可以表示所有44位二进制数（0..2-1），每一个叶子节点代表一个数。其中，红色路径表示n。所有小于n的数组成了三棵子树，分别用蓝色、绿色、紫色表示。因此，统计小于13的数，

5、就只需统计这三棵完整的完全二叉树：统计蓝子树内含3个1的数的个数、统计绿子树内含2个1的数的个数（因为从根到此处的路径上已经有1个1），以及统计紫子树内含1个1的数的个数。注意到，只要是高度相同的子树统计结果一定相同。而需要统计的子树都是“右转”时遇到的。当然，我们不能忘记统计n本身。实际上，在算法最初时将n自加1，可以避免讨论n本身，但是需要注意防止上溢。剩下的问题就是，如何统计一棵高度为i的完全二叉树内二进制表示中恰好含有j个1的数的个数。这很容易用递推求出：设f[i,j]表示所求，则分别统计左右子树内符合条件数的个

6、数，有f[i,j]=f[i-1,j]+f[i-1,j-1]。这样，我们就得出了询问的算法：首先预处理f，然后对于输入n，我们在假想的完全二叉树中，从根走到n所在的叶子，每次向右转时统计左子树内数的个数。下面是C++代码：voidinit()//预处理f{f[0][0]=1;for(inti=1;i<=31;++i){f[i][0]=f[i-1][0];for(intj=1;j<=i;++j)f[i][j]=f[i-1][j]+f[i-1][j-1];}}intcalc(intx,intk)//统计[0..x]内二进制表示

7、含k个1的数的个数{inttot=0,ans=0;//tot记录当前路径上已有的1的数量，ans表示答案for(inti=31;i>0;--i){if(x&(1<k)break;第2页，共12页浅谈数位类问题刘聪x=x^(1<

8、、1的数位，将它变为1，并将右面所有数位设为1。将得到的B进制表示视为二进制进行询问即可。2预处理递推f的时间复杂度为O(log(n))，共有O(log(n))次查询，因此总时间复杂度为2O(log(n))。实际上，最终的代码并不涉及树的操作，我们只是利用图形的方式来方便思考。因此也可以只从数位的角度考虑：对于询问n