Acw339.圆形数字

题意：

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

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

思路：

数位dp+记忆化搜索。

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

$det$是这个二进制数$0$的数量减去$1$的数量。

当然需要注意的是，$1$的数量可能大于$0$的数量导致$det$为负，所以我们加上一个$35$作为基值。

同时要注意前导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;
}