5-8 补题 第七次训练

UVA12670 Counting ones

首先把n转换成2进制，然后枚举上限变成1.

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
ll a[200];
ll dp[200];
ll dfs(int pos, bool limit, ll now){
    if (pos==-1)    return now;
    if (!limit && dp[pos]!=-1)  return now*pow(2,pos+1)+dp[pos];
    int up = limit? a[pos]:1;
    ll ans = 0;
    for (int i=0;i<=up;i++){
        ans += dfs(pos-1, limit && i==a[pos], now+i);
    }
    if (!limit) dp[pos] = ans;
    return ans;
}
ll solve(ll n){
    memset (dp, -1, sizeof dp);
    memset (a, 0, sizeof a);
    int pos = 0;
    a[0] = n;
    while (a[pos]){
        a[pos+1] += a[pos] / 2;
        a[pos] %= 2;
        pos++;
    }
    return dfs(pos-1, true, 0);
}
int main(){
    ll l,r;
    while (cin >> l >> r){
        cout << solve(r) - solve(l-1) << endl;
    }
    return 0;
}