资源描述：
《算法合集之《数位计数问题解法研究》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数位计数问题的解法研究北京市清华附中高逸涵引言数位计数问题主要与数的各位数字构成有关统计一段连续区间内的数的性质完全模拟题目描述会严重超时引言此类问题的一般性解法：将整个区间划分为若干子段对于每个子段，通过子段性质直接求解合并各子段结果，得到总结果以上为解决此类问题的总原则，接下来我们通过两道例题说明如何利用上述原则解决具体问题。例题1：TheSum（SPOJKPSUM）将1~N内所有数按照从小到大顺序从左到右依次写下，然后在每一数位之前依次插入加号和减号(循环)，求结果。数据范围：1<=N<=1015举例：
2、N=11时，答案为+1-2+3-4+5-6+7-8+9-1+0-1+1=4例题1：TheSum显然直接模拟题目叙述并不是一个可行的策略，需要找到一种高效的算法。因为加减符号的改变与数字个数相关，因此为了让规律更加明显，我们尽量将1~N划分为若干段区间，使得每个区间内的数的数字个数相同。例题1：TheSum按照上述原则将[1,N]划分为若干子区间：（这里以N=123456为例）[1,9]U[10,99]U[100,999]U[1000,9999]U[10000,99999]U[100000,123456]例题1
3、：TheSum那么，原问题转化为一个新问题：询问[A,B]的结果，其中A和B包含相同的数字个数。根据数字个数的奇偶性，这里分为两种情况讨论。例题1：TheSum数字个数为奇数的情况：(这里以[10000,56789]为例进行研究)+1-0+0-0+0-1+0-0+0-1+1-0+0-0+2-1+0-0+0-3……………-5+6-7+8-9可以看到，相邻两项基本都互相抵消了，只有个位相差1例题1：TheSum数字个数为偶数的情况：(这里以[100000,456789]为例进行研究)+1-0+0-0+0-0+1-
4、0+0-0+0-1+1-0+0-0+0-2+1-0+0-0+0-3……………+4-5+6-7+8-9可以看到，每一列的符号都是固定的，因此只需要对每一列分别进行求和即可例题1总结原区间询问同位数区间询问奇数位数区间询问偶数位数区间询问可以直接解决可以直接解决算法的本质是将复杂的问题逐步划分为简单问题的并，这正是解决数位计数问题的核心思想例题2：GraduatedLexicographicalOrdering（ZOJ2599）定义两个数的大小比较方法为首先比较各位数字之和，如果不相等则和大的数比较大，否则按字典
5、序比较两个数的大小关系。例如120小于4，因为120的数字之和为3，而4的数字之和为4。555小于78，因为在字典序意义下”555”<”78”。20小于200，因为在字典序意义下”20”<”200”例题2：GraduatedLexicographicalOrdering（ZOJ2599）求1~N中第K大的数；K在1~N中的位置范围：1<=K<=N<=10151，11，2，12，21，3，……K例题2：算法分析原问题内有两问，事实上两问之间可以互相转化，因此首先考虑解决较为容易的一问。对于原问题的两问，事实上似
6、乎求K在1~N中的位置较为容易求出，因为它比较符合我们的解题思路。我们可以将求K在1~N的位置换一种方式提出，即求[1,N]中有多少个数比K小，这个问题可以通过区间划分的方法转化为更小的问题并加以解决。例题2：算法分析尝试分解区间，我们发现，似乎怎样将区间拆分都不能将问题简化。原因在于，对于比较两数的首要元素——数字和，在任何连续区间内，都没有很好的规律，可以直接利用。那么，不妨转化思路，首先固定数字和，进而简化并解决问题。例题2：算法分析首先固定数字和，问题转化为在区间[A,B]内所有数字和为S的数当中，有
7、多少个小于K。显然，当K的数字和大于S时，答案等于[A,B]区间内所有数字和为S的数的总数，当K的数字和小于S时，答案等于0。于是，我们只需解决两者相等时的情况。例题2：算法分析新问题：当K的数字和为S时，在[A,B]中所有数字和为S的数中，有多少个比K小。这样，在数字和相同的情况下，只需考虑字典序，我们成功的简化了问题。例题2：算法分析那么，下一步的区间划分主要考虑字典序的因素，因此按照首位的不同数字进行划分。这里以[345,45678]为例(K=2457)：[345,45678]=[345,399]U[4
8、00,499]U…U[900,999]U[1000,1999]U[2000,2999]U…U[9000,9999]U[10000,19999]U[20000,29999]U[30000,39999]U[40000,45678]例题2：总结原区间询问数字和为S1数字和为S2数字和为S3首位数字为A1首位数字为A2首位数字为A3可以直接解决可以直接解决可以直接解决可以直接解决可以递归解决若问题较为复杂，
