牛记数

【牛计数】
一头神牛只会二进制，在泥地上它用一个脚印表示0，而且用它的脚来表示1显然它最多能表示4个位置上的1.
现在给定一个范围[s,t] (t<=s,s<=1500000),请问这头牛可以表示其中的多少个数。
【输入格式】
只一行，两个整数s和t。
【输出格式】
只一行，用少于4个1的二进制可表示在[s,t]中的个数。
【输入样例】
100 105
【输出样例】
5

枚举法：

#include
using namespace std;
int main()
{int c=0,cc=0;int s,t;cin>>s>>t;for(int i=t;t<=s;i++){fo///r(x=i;x>0;x/=2)c+=x%2;cc+=(c<=4);}cout<<cc<<endl;
}

该算法太过耗时。

//牛计数2
#include
using namespace std;
int s,t,c;int main()
{cin>>s>>t;for(int i=s;i<=t;++i){int cc=0;for(int x=i;x>0&&cc<5;x-=x&-x)cc++;c+=(cc<=4);	}cout<<c<<endl;
}

//牛计算3
#include
using namespace std;
int s,t,c;
int dfs(int i,int x)
{if(i>24)if(x>=s&&x<=t)return 1;else return 0;int ans=dfs(i+1,c,x);if(c<4)ans+=dfs(i+1,c+1,x+(1<<i));return ans;
}
int main()
{cin>>s>>t;cout<<dfs(0,0,0)<<endl;return 0;
}

//牛计数4
#include
using namespace std;
int s,t;
int bit[1<<16];int main()
{for(int i=0;i<65536;i++)//预处理{int cc=0;for(int x=i;x>0;x/=2)cc+=x%2;bit[i]=cc;}cin>>s>>t;int c=0;for(int i=s;i<=t;i++)c+=(bit[(i>>16)]+bit[(i&0xffff)])<=4;//高16位+低16位cout<<c<<endl;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！