long long ans = 0;
for(int i = 1; i <= n; i ++)
ans += lowbit(i)
lowbit(i)的意思是將i轉化成二進制數之後，只保留最低位的1及其後面的0，截斷前面的內容，然後再轉成10進制數
比如lowbit(7),7的二進制位是111，lowbit(7) = 1
6 = 110(2),lowbit(6) = 2,同理lowbit(4) = 4,lowbit(12) = 4,lowbit(2) = 2,lowbit(8) = 8
每輸入一個n，求ans
1 2 3
1 3 4
大致題意：中文的，都能看懂吧。。。
解題思路：這裡利用了數論的一些小技巧，關於lowbit的規律。我發現這類題數論題上來直接暴力嚴重超時的，一般來說都有規律！！！
開始做的時候直接暴力打表，結果打個表都跑了十幾秒，還是算了。。。
然後就潛心於找規律了，先隨便輸出了從1開始的幾個連續數的lowbit值，還沒啥感覺，後來又多輸出了幾組，才漸漸發現了規律——奇數的lowbit都是1；偶數的lowbit是先增後減的而且還是對稱的，並且從兩邊向中間看的話，都是公比為2的等比數列。這樣就可以計算了。如果n為偶數，偶數的可以轉化為2*dp[n/2]，然後再加上奇數的n/2個1，就可以了； n為奇數時，偶數的還是轉化成2*dp[n/2]，但是奇數的現在不是n/2個了,而是n/2 + 1個了。要想方便的總結一下，就可以寫成dp[n] = 2*dp[n/2] + n/2 + (n%2)；但是最近又發現了一種新的寫法，那就是位運算的寫法，位運算也可以實現乘除，而且比乘除運算要快，當然也能判別一個數的奇偶，可能是因為計算機本來就只能識別0和1的緣故吧，這些位運算就是直接對二進制數操作，所以更快。於是狀態轉移方程就可以寫成dp[n] = 2*dp[n>>1] + (n>>1) + (n&1).
AC代碼：
#include#include #include using namespace std; long long dp(int x){ if(x == 1) return 1; return 2*dp(x>>1) + (x>>1) + (x&1); } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif int n; while(~scanf("%d",&n)){ printf("%lld\n", dp(n)); } return 0; }
