国家集训队2009论文集数位计数问题解法研究.pptVIP

数位计数问题的解法研究 北京市清华附中 高逸涵 引言 数位计数问题 主要与数的各位数字构成有关 统计一段连续区间内的数的性质 完全模拟题目描述会严重超时 引言 此类问题的一般性解法： 将整个区间划分为若干子段 对于每个子段，通过子段性质直接求解 合并各子段结果，得到总结果 以上为解决此类问题的总原则，接下来我们通过两道例题说明如何利用上述原则解决具体问题。 例题1：The Sum（SPOJ KPSUM） 将1~N内所有数按照从小到大顺序从左到右依次写下，然后在每一数位之前依次插入加号和减号(循环)，求结果。 数据范围：1=N=1015 举例：N=11时，答案为+1-2+3-4+5-6+7-8+9-1+0-1+1=4 例题1：The Sum 显然直接模拟题目叙述并不是一个可行的策略，需要找到一种高效的算法。 因为加减符号的改变与数字个数相关，因此为了让规律更加明显，我们尽量将1~N划分为若干段区间，使得每个区间内的数的数字个数相同。 例题1：The Sum 按照上述原则将[1,N]划分为若干子区间：（这里以N=123456为例） [1,9]U[10,99]U[100,999]U[1000,9999]U[10000,99999]U[100000,123456] 例题1：The Sum 那么，原问题转化为一个新问题：询问[A,B]的结果，其中A和B包含相同的数字个数。 根据数字个数的奇偶性，这里分为两种情况讨论。 例题1：The Sum 数字个数为奇数的情况：(这里以[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：The Sum 数字个数为偶数的情况：(这里以[100000,456789]为例进行研究) +1-0+0-0+0-0 +1-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：Graduated Lexicographical Ordering（ZOJ 2599） 定义两个数的大小比较方法为首先比较各位数字之和，如果不相等则和大的数比较大，否则按字典序比较两个数的大小关系。 例如120小于4，因为120的数字之和为3，而4的数字之和为4。555小于78，因为在字典序意义下”555””78”。20小于200，因为在字典序意义下”20””200” 例题2：Graduated Lexicographical Ordering（ZOJ 2599） 求1~N中第K大的数；K在1~N中的位置 范围：1=K=N=1015 1，11，2，12，21，3，…… K 例题2：算法分析 原问题内有两问，事实上两问之间可以互相转化，因此首先考虑解决较为容易的一问。 对于原问题的两问，事实上似乎求K在1~N中的位置较为容易求出，因为它比较符合我们的解题思路。 我们可以将求K在1~N的位置换一种方式提出，即求[1,N]中有多少个数比K小，这个问题可以通过区间划分的方法转化为更小的问题并加以解决。 例题2：算法分析 尝试分解区间，我们发现，似乎怎样将区间拆分都不能将问题简化。 原因在于，对于比较两数的首要元素——数字和，在任何连续区间内，都没有很好的规律，可以直接利用。 那么，不妨转化思路，首先固定数字和，进而简化并解决问题。 例题2：算法分析 首先固定数字和，问题转化为在区间[A,B]内所有数字和为S的数当中，有多少个小于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[400,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