BD string 百度之星初赛的题目 数学

http://acm.hdu.edu.cn/showproblem.php?pid=5694

可以说这道题目挺考验思维含量的吧

首先，这个和数位dp是差不多的方法，计算cal(l)-cal(l-1)；

然后我们可以得出，每次在2^n的时候都是要+1，然后我们计算出rest。

例如BBDBBDD B BBDDBDD 我们令R = 12，然后可以得出rest = 5，但是中间的这个B是没有啥用的，那么我们就让rest = 4，并且ans+1即可。然后记住rest = 之前的长度中的后面的rest个数字，因此假定rest之前的长度为m，那么我们就只要dfs(m) - dfs(m - rest)即可

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll inf = 1e18;
ll l, r;


ll dfs(ll x){
    if (x == 0) return 0;
    ll m = 0, ans = 0, rest = 0;
    while (m * 2 + 1 < x) m = m * 2 + 1;
    ans = (m + 1) / 2;
    rest = x - m - 1;
    //printf("m = %lld
", m);
    return ans + rest - (ans - dfs(m - rest)) + 1;
}

int main(){
    int t; scanf("%d", &t);
    while (t--){
        cin >> l >> r;
        printf("%lld
", dfs(r) - dfs(l - 1));
    }
    return 0;
}