題意：給定a和b，n，讓你求b+a, b+2*a, .......b+n*a里面有多少1.

?

當(dāng)統(tǒng)計第K位的時候 可以注意到 第 B+T*A 和 B+（T+2^（K+1））*A 位是相同的

那么 第K位的時候 只需要統(tǒng)計2^(K + 1) ?- 1次就可以了

當(dāng)統(tǒng)計第K位的時候 可以注意到 連續(xù)的 (2^K)/A都是連續(xù)的0 或者連續(xù)的1 所以可以考慮直接連續(xù)記錄(2^K)/A個結(jié)果。

那么 第K位的時候 只需要統(tǒng)計N / ((2^K)/A)次就可以了
那么 第K位的時候 只需要統(tǒng)計 2^K/((2^K)/A) 復(fù)雜度 變?yōu)镺(A)

?

以上是題解。當(dāng)然，第一部分很容易想到，但是那個優(yōu)化我沒想到。。。。其實是個很簡單的優(yōu)化了吧。如，當(dāng)統(tǒng)計第K位時，第K位后面的數(shù)字決定了有多少個連續(xù)的第K位的相同的數(shù)字。最大是到后面的數(shù)字全為1。所以，只需統(tǒng)計到最大為全1的情況即可，當(dāng)然是可以小于的。這就很容易理解了。也算是一種常用的技巧了，但做的時候竟然沒想到。。。

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; typedef long long LL;void Solve(LL a,LL b,LL n) {LL cnt=0;LL max=b+a*n;for(LL i=0;i<64;i++){LL m=(LL)1<<i;LL mm=m;if(m>max) break;m<<=1;LL cur=a+b;LL j=0;while(j<m&&j<n){LL step=((mm-1)-cur&(mm-1))/a+(LL)1;if(j+step>=n) step=n-j;if(j+step>=m) step=m-j;if(cur&(LL)1<<i){cnt+=step*(n/m);if(j+step<(n%m)) cnt+=step;else if(j<(n%m)) cnt+=(n%m)-j;}cur+=a*step;j+=step;}}cout<<cnt<<endl; }int main() {int t,k=1;LL a,b,n,i,j;cin>>t;while(t--){cin>>a>>b>>n;cout<<"Case #"<<k++<<": ";Solve(a,b,n);}return 0; }

　　

轉(zhuǎn)載于:https://www.cnblogs.com/jie-dcai/p/4085313.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的HDU 4321 Contest 3的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。