2013南京邀请赛C题/njustOJ 1739 - Count The Carries

2013南京邀请赛C题/njustOJ 1739 - Count The Carries

比赛的时候思路马上出来了..但很多地方没考虑清楚..搞了好久才过....值得注意的...要用long long...再一个..a加到b的二进制数长度可能到达64位.....

此类问题..常规的把握是求0~a-1的..与0~b的.... 再用后者减去前者得到答案...

通过观察..问题可以转化为..求a加到b的不进位二进制数..然后再通过至右向左的进位统计二进制的进位次数...再转化..就是求从a~b这些数...每一位有多少个1.....

如从0~3...表示成不进位的二进制数位22...再对22进位成合法的二进制数...22 -> 30 , 30 -> 110...一共进位两次.....

那么如何统计每一位上1的个数呢？通过几次演算..不难发现..从0+1+2+....x...当x为2^p-1时...该二进制数为2^p 2^p 2^p...

如0加到3为22.....0加到7为444...0加到15为8888.....

那么如何求不是2^p-1的数呢？

比如说10....比10小的最大2^p-1数是7...所以可以先得到0加到7的情况...444...还剩下了8,9,10没有加..而8,9,10若是去掉最高位的1..不就是0加到2的情况...

444(0加到7)+300(8,9,10的高位)+011(0加到2)=755...

但注意...结果并不是数出0加到a-1的进位数s1...数出0到b的进位数s2...s2-s1....而是算出0加到a-1和0到b的不进位二进制数..用后者减去前者之后..再进行进位统计...

Program:

//ll long longusing namespace std;ll ss[80],s[80];void getdata(ll x){ ll i,p; memset(s,0,sizeof(s)); p=30; while (x>0) { while (x<(1<

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。