• 如果您想对本站表示支持,请随手点击一下广告即可~
  • 本站致力于提供原创、优秀的技术文章~
  • 有任何疑问或建议 均可以在站点右侧栏处 通过各种方式联系站长哦~
  • POJ3252 – Round Numbers

    ACM-POJ EXP 180阅读 1评论

    全解题报告索引目录 -> 【北大ACM – POJ试题分类


    大致题意

    输入两个十进制正整数a和b,求闭区间 [a ,b] 内有多少个Round number

    所谓的Round Number就是把一个十进制数转换为一个无符号二进制数,若该二进制数中0的个数大于等于1的个数,则它就是一个Round Number

    注意,转换所得的二进制数,最高位必然是1,最高位的前面不允许有0

    规定输入范围: 1<= a <b<=2E

    组合


    很猥琐的题,我首先说说猥琐的地方,再说说解题思路,有四点很猥琐

    (1)规定输入范围: 1<= a <b<=20E

    输入的数是一个接近大数的非大数,int可以存储

    网上看很多同学都说要用到精度,其实完全没必要,int能表示21E+的整数,精确的int极限能表示的正整数为2147483647,

    但是即使这样,面对这题也不能松懈啊! bin[]边界的最小值为35 !!。

    (2)bin[]数组若果定义为局部数组,等着WA吧!

    我找不到任何原因为什么会这样,bin不管是全局定义 还是 局部定义,本地是完全AC的,上传就出问题了,局部WA,全局AC。

    人家有强权,我被迫把传参del掉,把bin改为全局,郁闷!猥琐!

    (3)组合数打表,同(1)的猥琐,c[][]边界的最小值为33,就是说如果定义组合表的大小比 c[33][33]小的,就等着RE吧!

    还有就是这个算法有一个违背常识的处理,要把c[0][0]=1,不然某些最终结果会少1

    (4)输入不能用循环输入while(cin>>…),不然你就等着OLE (就是Output Limit Excessed,很少见吧!)。不知道数据库是怎么回事,输入竟然不会根据读取数据结束而结束,而是无限输出最后一次输入所得的结果……老老实实一次输出就end file吧!

    解题思路

    组合数学题,(也属 递推数学,是因为杨辉三角和组合数之间的关系)

    我根据我写的程序讲解好了

    要知道闭区间 [a ,b] 内有多少个Round number,只需要分别求出

    闭区间 [0 ,a] 内有T个RN

    闭区间 [0 ,b+1] 内有S个RN

    再用 S – T 就是闭区间 [a ,b] 内的RN数了

    至于为什么是 b+1,因为对于闭区间 [0 ,k] ,我下面要说的算法求出的是比k小的RN数,就是说不管 k是不是RN, 都没有被计算在内,所以若要把闭区间[a ,b]的边界a和b都计算在内,就要用上述的处理方法。


    现在问题的关键就是如何求[0 ,k]内的RN数了

    首先要把k转化为二进制数bin-k,并记录其位数(长度)len

    那么首先计算长度小于len的RN数有多少(由于这些数长度小于len,那么他们的值一定小于k,因此在进行组合时就无需考虑组合所得的数与k之间的大小了)

    可以看到,i<len-1 ,之所以减1,是因为这些长度比len小的数,最高位一定是1,那么剩下可供放入数字的位数就要再减少一个了

    这条程序得到的sum为

    1表示当前处理的二进制数的最高位,X表示该二进制数待放入数字的位

    显然这段程序把 二进制数0 排除在外了,这个是最终结果没有影响的,因为最后要把区间[a , b]首尾相减,0存不存在都一样了。

    然后计算长度等于len的RN数有多少(由于这些数长度等于len,那么他们的值可能小于k,可能大于k,因此在进行组合时就要考虑组合所得的数与k之间的大小了)

    之所以初始化i=bin[0]-1,是因为bin[]是逆向存放k的二进制的,因此要从高位向低位搜索,就要从bin[]后面开始,而要bin[0]-1 ,是因为默认以后组合的数长度为len,且最高位为1,因此最高位不再搜索了。

    那么问题的关键就是怎样使得以后组合的数小于k了

    这个很简单:

    从高位到低位搜索过程中,遇到当前位为0,则不处理,但要用计数器zero累计当前0出现的次数

    遇到当前位为1,则先把它看做为0,zero+1,那么此时当前位 后面的 所有低位任意组合都会比k小,找出这些组合中RN的个数,统计完毕后把当前位恢复为原来的1,然后zero-1,继续向低位搜索


    那么问题就剩下 当当前位为1时,把它看做0之后,怎样去组合后面的数了

    此时组合要考虑2个方面:

    (1) 当前位置i后面允许组合的低位有多少个,我的程序由于bin是从bin[1]开始存储二进制数的,因此 当前位置i后面允许组合的低位有i-1个

    (2) 组合前必须要除去前面已出现的0的个数zero

    我的程序中初始化j=(bin[0]+1)/2-(zero+1), j本来初始化为(bin[0]+1)/2就可以了,表示对于长度为bin[0]的二进制数,当其长度为偶数时,至少其长度一半的位数为0,它才是RN,当其长度为奇数时,至少其长度一半+1的位数为0,它才是RN。

    但是现在还必须考虑前面出现了多少个0,根据前面出现的0的个数,j的至少取值会相应地减少。 -(zero+1) ,之所以+1,是因为要把当前位bin[i]看做0


    然后到了最后,剩下一个问题就是怎样得到每一个 的值,这个我发现很多同学都是利用打表做的,利用的就是 组合数 与 杨辉三角 的关系(建立一个二维数组C[n], 就能看到他们之间关系密切啊!区别就是顶点的值,杨辉三角为1,组合数为0)

    其实这个“关系”是有数学公式的

    好好体会一下吧!

    其实组合数也可以直接用计算方法做(n的规模可以至少扩展到1000),不过这里n的规模只有26,打表应该是更快的,有兴趣学习用计算方法做组合数的同学可以联系我,这个要用另外的数学方法处理。

    转载请注明:EXP 技术分享博客 » POJ3252 – Round Numbers

    喜欢 (1) 分享 (0)
    发表我的评论
    取消评论

    表情

    Hi,您需要填写昵称和邮箱!

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址
    (1)个小伙伴在吐槽
    1. 区别就是顶点的值,杨辉三角为1,组合数为0)
      sdz2018-08-03 08:32 回复