圆形数字

定义圆形数字如下：

把一个十进制数转换为一个无符号二进制数，若该二进制数中 0 的个数大于或等于 1 的个数，则它就是一个圆形数字。

现在给定两个正整数 a 和 b，请问在区间 [a,b] 内有多少个圆形数字。

输入格式
输入占一行，包含两个整数 a 和 b。

输出格式
输出一个整数，表示圆形数字的个数。

数据范围
1≤a<b≤2×109
输入样例：
2 12
输出样例：
6

题意：
把一个十进制数字转换为一个无符号二进制数，若该二进制中的0的个数大于等于1的个数，则为一个圆形数字。

给定整数a,ba,b，问区间a,b内有多少个圆形数字。

思路：
数位dp+记忆化搜索。

设f(pos,det)f(pos,det)表示处理到pospos位，当前detdet是多少的答案。

detdet是这个二进制数00的数量减去11的数量。

当然需要注意的是，11的数量可能大于00的数量导致detdet为负，所以我们加上一个3535作为基值。

同时要注意前导0的影响：

如果当前前导0标记为1且本位也是0，表示当前位也是前导0，pos+1继续搜索。

如果当前前导0标记为1但本位不是0，表示当前位为该次搜索的最高位。、

别忘了初始化dp数组，别问我为啥知道QwQ

#include<bits/stdc++.h>
using namespace std;
int a[40];
int f[40][70];

int dfs(int pos, int det, bool limit, bool lead)
{
    if(pos == 0) return det >= 35;
    if(!limit && !lead && f[pos][det] != -1) return f[pos][det];
    int up = limit?a[pos]:1;
    int ans = 0;
    for(int i = 0; i <= up; i++)
    {
        if(i==0 && lead) ans += dfs(pos-1, 35, limit&&(i==a[pos]), true);
        else if(i) ans += dfs(pos-1, det-1, limit&&(i==a[pos]), false);
        else ans += dfs(pos-1, det+1, limit&&(i==a[pos]), false);
    }
    if(!limit && !lead) f[pos][det] = ans;
    return ans;
}

int solve(int x)
{
    int len = 0;
    while(x)
    {
        a[++len] = x&1;
        x >>= 1;
    }
    return dfs(len, 35, 1, 1);
}

int main()
{
    memset(f, -1, sizeof(f));
    int l, r; scanf("%d%d", &l, &r);
    if(l > r) swap(l, r);
    cout << (solve(r)-solve(l-1))<<endl;
    return 0;
}