浅谈数位类统计问题.ppt

浅浅谈数位数位类统计问题山东省青岛第二中学刘聪2024/5/21 周二1引入在信息学竞赛中，有一类与数位有关的区间统计问题。例如：求1,n中所有数的各位数字之和。求1,n中各位数字之和为定值的数的个数。将m,n中的数字分组，每组包含连续的一段数，且数字之和不能超过定值，求分组数。如何求解？n1018!2024/5/21 周二2【例题1】Amount of degrees求给定区间X,Y中满足下列条件的整数个数：这个数恰好等于K个互不相等的B的整数次幂之和。例如，设X=15，Y=20，K=2，B=2，则有且仅有下列三个数满足题意：17=24+20，18=24+21，20=24+22。数据规模：1XY2311，1K20，2B10。2024/5/21 周二3【例题1】Amount of degrees由于所求的幂互不相等，符合条件的数写成B进制一定只由0和1组成。因此我们只考虑B=2的情况。此处区间满足区间减法，即count(X,Y)=count(0,Y)-count(0,X-1)因此我们唯一需要求的就是，给定n，求出所有不超过n的正整数中，其二进制表示恰好含有K个1的有多少。2024/5/21 周二4【例题1】Amount of degrees这里，我使用一棵完全二叉树来代表一个区间内的数。例如右图中高度为4的完全二叉树就可以代表所有长度为4的二进制数。其范围为0,24-1每个叶子就代表了一个数。2024/5/21 周二5【例题1】Amount of degrees假设K=3，n=13，其二进制为1101。我们从根走到n所在的叶子每次“向右走”时，左侧的子树都是完整的完全二叉树，且所有小于n的整数都包含在其中。2024/5/21 周二6【例题1】Amount of degrees因此，我们实际上只需对这三棵子树进行统计。当然，不能忘记n本身。这棵树中有多少数含3个1？这棵树中有多少数含2个1？（因为祖先已有1个1）这棵树中有多少数含1个1？2024/5/21 周二7【例题1】Amount of degrees很容易递推求出这个问题：设fh,s表示在高度为h的完全二叉树包含的数中（范围是0,2h-1），二进制中恰含s个1的数有多少。fh,s=fh-1,s+fh-1,s-1左子树中的个数右子树中的个数2024/5/21 周二8【例题1】Amount of degrees剩下的问题就是，如何将任意进制问题转化为二进制问题。只需贪心将n的B进制表示转化为只含01：找到n的左起第一位大于1的数位，将它以及它右边所有数位赋为1。递推求f的时间复杂度为O(log2(n)，每次询问的时间复杂度为O(log(n)，因此总时间复杂度为O(log2(n)。问题得到完美解决！2024/5/21 周二9【例题1】Amount of degrees实际上，我们也可以只用“位”的思想来考虑这个问题，而不使用树的思想。我们每次找到n的1数位，将它赋为0，则其右面的数位可任取0、1。可根据组合数算出满足题意的数的个数。穷举所有“1”数位，计算组合数，即可完成询问。事实上，f的递推公式正是组合数公式！与树的思想异曲同工!2024/5/21 周二102024/5/21 周二11【例题1】Amount of degrees使用高度为h的完全B叉树表示所有长度为h的B进制数，思考起来更加直观，在处理较复杂问题时优点明显。当然，最终程序我们并不真正建树，它的作用只是帮助我们思考。无论从树结构考虑还是从数位的角度考虑，基本思想都是：2024/5/21 周二12【例题4】Tickets有一位售票员给乘客售票。对于每位乘客，他会卖出多张连续的票，直到已卖出的票的编号的数位之和不小于给定的正数K。然后他会按照相同的规则给下一位乘客售票。初始时，售票员持有的票的编号是从L到R的连续整数。请你求出，售票员可以售票给多少位乘客。数据规模：1LR1018，1K1000。2024/5/21 周二13【例题4】Tickets有了例1的基础，本题基本思路也是从特殊到一般：能否将原问题的区间拆分为一些长度为10k的子区间，再合并得到原区间的答案？亦即，将原树拆分为若干完整的完全十叉数，根据子树的信息合并得到原问题的答案。一个比较棘手的问题是，这棵树的前几个元素可能会并入之前的小组，而不是作为一个新的小组。换言之，只使用树的高度无法表示一组状态。添加状添加状态！2024/5/21 周二14【例题4】Tickets设fh,sum,rem表示对于高度为h的完全十叉树，其每个数的数位之和需要额外添加sum，在这棵树之前的最后一个小组剩余空间为rem，所能得到的小组情况。f返回值有两个：fh,sum,rem.a记录这棵树被划分成的小组数量，fh,sum,rem.b记录这些小组中的最后一组的剩余空间，以便与下一组合并。同例1一样，这里f的值也由其10棵子树合并而成：fori:=0to9dofh,sum,rem:=merge(fh,sum,rem,fh-1,sum+i,fh,sum,rem.b);也就是之前得到的b值作为下一棵子树的rem值。functionmerge(x,y);x.a:=x.a+y.a;x.b:=y.b;returnx;2024/5/21 周二15【例题4】Tickets这样，我们就解决了单个子树的情况。接下来的问题就是如何将原树分解为若干子树。本题不满足区间减法，因此对于L,R这个区间，需要直接找它们中间的子树。为了方便起见，这里以二叉树为例进行介绍，其思想与十叉树一致。2024/5/21 周二16【例题4】Tickets假设L=2,R=11。让我们从L走到R：首先从L向上走，直到L和R的最近公共祖先统计途中节点右侧的兄弟子树再向下走到R统计途中节点左侧的兄弟子树需要注意的是在LCA的下一层，两条路径是兄弟关系，需要统计它们之间的子树。LR2024/5/21 周二17【例题4】Tickets抠出这些子树：它们包含了L和R间的连续整数我们只要分别求出每个子树，再加以合并即可!这样，我们就解决了这道题目。LR2024/5/21 周二18【例题4】Tickets回顾解题过程：在处理完整子树时，为了表示状态，我们添加了新的一维。由于问题不满足区间减法，我们改“走下去”为“走上去”、“走过去”、“走下来”。其余步骤与例1相似：将待求区间分解为若干子区间（子树），每个完整子树利用递推求出，最后合并出完整答案。递推求f的复杂度为O(klog2(R)，需要询问的子树最多有O(log(R)个，因此总复杂度是O(klog2(R)。建议采用记忆化搜索实现。2024/5/21 周二19总结以上，我们通过两道例题了解了数位类的区间统计问题及其基本处理方法。只要本着“逐位确定”的思想，往往就能找到突破口，设计出log(n)级别复杂度的算法。使用树结构来思考问题，更加直观，化抽象为具体，有利于我们的思考。数形数形数形数形结结合！合！合！合！2024/5/21 周二20谢谢大家大家欢迎提迎提问!2024/5/21 周二212024/5/21 周二22