题意：求一个区间内满足化为二进制后0多于1的数的数量
#pragma comment(linker, "/STACK:10240000,10240000") #include<iostream> #include<cstdio> #include<cstring> #include<string> #include<queue> #include<set> #include<vector> #include<map> #include<stack> #include<cmath> #include<algorithm> using namespace std; const double R=0.5772156649015328606065120900; const int N=1e5+5; const int mod=1e9+7; const int INF=0x3f3f3f3f; const double eps=1e-8; const double pi=acos(-1.0); typedef long long ll; int dp[35][66]; int a[66]; int dfs(int pos,int sta,bool lead,bool limit) { if(pos==-1) return sta>=32;//转化成32-64内，分小于32和大于32不再分小于大于0 if(!limit && !lead && dp[pos][sta]!=-1) return dp[pos][sta]; int up=limit?a[pos]:1; int ans=0; for(int i=0;i<=up;i++) {//lead处理前导零问题;//注意体会lead&&i==0 if(lead && i==0) ans+=dfs(pos-1,sta,lead,limit && i==a[pos]);//有前导零就不统计在内 else ans+=dfs(pos-1,sta+(i==0?1:-1),lead && i==0,limit && i==a[pos]); } if(!limit && !lead ) dp[pos][sta]=ans; return ans; } int solve(int x) { int pos=0; while(x) { a[pos++]=x&1; x>>=1;//处理进制 } return dfs(pos-1,32,true,true);//刚开始并没有前导0 } int main() { memset(dp,-1,sizeof dp); int a,b; while(~scanf("%d%d",&a,&b)) { printf("%d\n",solve(b)-solve(a-1)); } return 0; }
