题目
( exttt{[USACO06NOV] Round Numbers S})
分析
数位 (dp) 入门题
一般我们需要当前位置 (pos),有无前导零 (lead),高位标记 (limit)
然后就依题弄
(Code)
#include<cstdio>
#include<cstring>
using namespace std;
int l , r , f[40][40][40] , a[40] , len;
int dfs(int pos , int s0 , int s1 , int lead , int limit)
{
if (!pos) return s0 >= s1;
if (f[pos][s0][s1] != -1 && !lead && !limit) return f[pos][s0][s1];
int res = 0;
for(register int i = 0; i <= (limit ? a[pos] : 1); i++)
{
if (!i && lead) res += dfs(pos - 1 , s0 , s1 , 1 , limit && (i == a[pos]));
else res += dfs(pos - 1 , s0 + (i == 0) , s1 + (i == 1) , 0 , limit && (i == a[pos]));
}
if (!lead && !limit) f[pos][s0][s1] = res;
return res;
}
int solve(int x)
{
len = 0;
while (x) a[++len] = x & 1 , x >>= 1;
memset(f , 255 , sizeof f);
return dfs(len , 0 , 0 , 1 , 1);
}
int main()
{
scanf("%d%d" , &l , &r);
printf("%d
" , solve(r) - solve(l - 1));
}