喜爱
时间限制: 1 Sec 内存限制: 128 MB
[提交] [状态]
题目描述
小s最近对数字情有独钟。他又发现了一种神奇的数字。对于数x，如果它二进制表示中只有一位是0，则x就会被小s所喜爱。比如5，二进制为101，则它被小s所喜爱。
现在，小s想知道，对于一个区间[L,R]，有多少数是他所喜爱的。
输入
输入包含多组数据。
输入第一行T，表示数据组数。
每组数组仅有一行，包含两个正整数[L,R]。
输出
对于每组数据输出一行，表示答案。
样例输入 Copy
2
5 10
2015 2015
样例输出 Copy
2
1
提示
对于30%的数据:L,R≤106，T≤10
对于60%的数据:L,R≤1010，T≤100
对于100%的数据:L,R≤1018，T≤10000
规律题（太搞心态了）
写出前几项就找出规律来了，其实还是进制的运用
好像这题挺水？（手动划掉）
#include<bits/stdc++.h> typedef unsigned long long ll; using namespace std; const int maxn=1e6+7,mod=1e9+7,inf=0x3f3f3f3f; ///0:0 2 ///10:2 4 ///110:6 ///1 ///101:5 8 ///1110:14 ///1 ///1101:13 ///2 ///1011:11 16 ///11110:30 ///1 ///11101:29 ///2 ///11011:27 ///4 ///10111:23 ll a[maxn],cnt; map<ll,bool>mp; void init(){ ll k=2,tot=1; a[cnt++]=0; for(ll i=2;i<1e19;i+=k){ ll m=1,last=i; a[cnt++]=i; mp[i]=1; for(ll j=1;j<tot;j++){ a[cnt++]=last-m; mp[last-m]=1; m=m*2; last=a[cnt-1]; //cout<<"%"<<i<<" "<<j<<" "<<m<<endl; } // cout<<"&"<<i<<" "<<k<<" "<<tot<<endl; k*=2;tot++; // cout<<i<<" "<<k<<" "<<tot<<endl; } } void AC(){ init(); sort(a,a+cnt); ///for(int i=0;i<cnt;i++) cout<<a[i]<<" "; int t;scanf("%d",&t); ll l,r; while(t--){ cin>>l>>r; if(l==r){ if(mp.count(l)) puts("1"); else puts("0"); continue; } if(l>r) swap(l,r); ///对于左边界：找第一个大于等于左边界的数 ///对于右边界：找第一个大于右边界的数再减一 ll posl=lower_bound(a,a+cnt,l)-a; ll posr=upper_bound(a,a+cnt,r)-a-1; //cout<<posl<<" "<<posr<<endl; printf("%llu\n",posr-posl+1); } } int main(){ AC(); return 0; }
学长的数位DP：博客友链
还有种纯模拟的和高级打表方法的，明天等大佬更完后附上友链~
就先这样~
