【题解】P6218 [USACO06NOV] Round Numbers S

【P6218】题解

一：【题意】

求f(l)+f(l+1)+...+f(r)
f(x):x二进制表示下，去掉前导0，0的个数是否比1多

二：【解法】

需要用到的关键信息有，0的个数，1的个数
所以把 当前位，前导零，数位限制，0的个数，1的个数 压成一个状态

三：【代码】

#include<bits/stdc++.h>
using namespace std;
vector<int> a;
int dp[64][2][2][64][64];
int Dp(int now,int st,int lim,int s0,int s1){if(now==a.size()) return s0>=s1;if(dp[now][st][lim][s0][s1]!=-1) return dp[now][st][lim][s0][s1];int maxn=lim?a[now]:1;int ans=0;for(int i=0;i<=maxn;i++){ans+=Dp(now+1,st&&(i==0),lim&&(i==maxn),s0+(st==1?0:(i==0)),s1+(i==1));}dp[now][st][lim][s0][s1]=ans;return ans;
}
int cl(int x){a.clear();while(x){a.push_back(x&1);x>>=1;}reverse(a.begin(),a.end());memset(dp,-1,sizeof dp);return Dp(0,1,1,0,0);
}
int main(){int l,r;cin>>l>>r;cout<<cl(r)-cl(l-1)<<"\n";return 0;
}