C - Count The Carries
时间限制: | 3000 Ms |
内存限制: | 65535 Kb |
问题描述
One day, Implus gets interested in binary addition and binary carry. He will transfer all decimal digits to binary digits to make the addition. Not as clever as Gauss, to make the addition from a to b, he will add them one by one from a to b in order. For example, from 1 to 3 (decimal digit), he will firstly calculate 01 (1)+10 (2), get 11,then calculate 11+11 (3),lastly 110 (binary digit), we can find that in the total process, only 2 binary carries happen. He wants to find out that quickly. Given a and b in decimal, we transfer into binary digits and use Implus's addition algorithm, how many carries are there?
输入说明
About 100000 cases, end with EOF.
Two integers a, b(0<=a<=b<1000000000).
输出说明
For each case, print one integers representing the number of carries per line.
输入样例
1 2 1 3 1 4 1 6
输出样例
0 2 3 6
(转)
比赛的时候思路马上出来了..但很多地方没考虑清楚..搞了好久才过....值得注意的...要用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的情况...
所以0加到10的不进位二进制数为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的不进位二进制数..用后者减去前者之后..再进行进位统计...
注意:用%lld提交
#include<iostream> #include<cstdio> #include<cstring> #include<map> using namespace std; long long a,b,ans; long long digit1[64],digit2[64]; void cal(long long digit[],long long x){ //memset(digit,0,sizeof(digit)); for(int i=0;i<64;i++) digit[i]=0; int p=30; while(x>0){ while(x<(1<<p)-1) p--; for(int i=0;i<p;i++){ //printf("@@@%d\n",digit[i]); digit[i]+=(1<<(p-1)); //printf("---%d\n",digit[i]); } digit[p]+=x-((1<<p)-1); x-=(1<<p); } } int main(){ //freopen("input.txt","r",stdin); while(~scanf("%lld%lld",&a,&b)){ ans=0; cal(digit1,a-1); cal(digit2,b); for(int i=0;i<64;i++) digit2[i]-=digit1[i]; for(int i=0;i<64;i++){ ans+=digit2[i]/2; digit2[i+1]+=digit2[i]/2; } printf("%lld\n",ans); } return 0; }
相关推荐
- FIX: In "Windows ClearType" font rendering mode (OS Windows mode) the "garbage" pixels can appear from the right and from the bottom sides of the painted rectangle of the TFlexText object....
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow Mac OS X to boot * Fix vmwarebase .dll or .so to allow Apple ...
It carries this out using unique 'Run-time Monitoring and Manipulation Technology' (RMMT) developed over many years, and which has culminated in this highly original product. Mask for Windows - ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow Mac OS X to boot * Fix vmwarebase .dll or .so to allow Apple ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow Mac OS X to boot * Fix vmwarebase .dll or .so to allow Apple ...
PHP also makes it simple to parse form data and make HTTP requests. This web-specific focus carries over to the recipes and examples in the PHP Cookbook. This book is a collection of solutions to ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow macOS to boot * Fix vmwarebase .dll or .so to allow Apple to ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow macOS to boot * Fix vmwarebase .dll or .so to allow Apple to ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow Mac OS X to boot * Fix vmwarebase .dll or .so to allow Apple ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow macOS to boot * Fix vmwarebase .dll or .so to allow Apple to ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow Mac OS X to boot * Fix vmwarebase .dll or .so to allow Apple ...
pixel carries one bit of information, and a function of the two pixel values carries another bit of information. Therefore, the modified method allows embedding the same payload as LSB matching but ...
This function enables an IME to get the lock count of the input method context (IMC) component. ImmGetIMCCSize This function enables an IME to get the size of the input method context (IMC) ...
The patch code carries out the following modifications dependent on the product being patched: * Fix vmware-vmx and derivatives to allow Mac OS X to boot * Fix vmwarebase .dll or .so to allow Apple ...
-C language does books management system management system this procedure can realize to a book carries on picks enrolls the storehouse, the elimination stock, borrows the books, returns the books ...
But because the gear relative to the bearing of the two-stage cylindrical gear reducer is arranged asymmetrically, the load distribution along the tooth direction is uneven, and the shaft stiffness ...
Ftrace has its origins from the -rt patch [1] latency tracer, and still carries the capabilities to track down latencies. It can catch the maximum wake up latency for the highest priority task. This ...
The Java Server Pages(JSP) is a kind of according to web of the script plait distance technique, similar carries the script language of Java in the server of the Netscape company of server- side ...
carries the packet until a new vehicle moves into its vicinity and forwards the packet. Different from existing carry and forward solutions, we make use of the predicable vehicle mobility, which is ...
To the button, the relay, the switch, the frequency changer and so on other some I/O spot carries on the control, realized the washer to wash clothes the process automation. Because spreads every ...