题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5331
题意：在区间[x,y]区间内找二进制下为ABABAB...AB或者ABAB...ABA的数，A为n个1，B为m个0，A部分的个数不能为0，B部分的个数可以为0，且n,m>=1。
思路：直接枚举n和m，如果凑成的最长长度等于最大范围，就比较一下大小，否则长度小的直接累加上。
#include <cstdio> #include <cmath> #include <cstring> #include <string> #include <cstdlib> #include <iostream> #include <algorithm> #include <stack> #include <map> #include <set> #include <vector> #include <sstream> #include <queue> #include <utility> using namespace std; #define rep(i,j,k) for (int i=j;i<=k;i++) #define Rrep(i,j,k) for (int i=j;i>=k;i--) #define Clean(x,y) memset(x,y,sizeof(x)) #define LL long long #define ULL unsigned long long #define inf 0x7fffffff #define mod 100000007 ULL x,y; LL cal( ULL n ) //[1~n]范围内合法的数量 { int len = 0; if ( n <= 0 ) return 0; ULL temp = n; while( temp ) len++ , temp/=2; LL ans = 0; rep(i,1,len-1) rep(j,1,len-i) { //计算ABAB形式 int k = len/(i+j); int ret = len - k * (i+j); if ( ret ) ans+=k; else { ULL m = 0; ULL now = 0; rep(ii,1,i) now = now << 1 | 1; rep(ii,1,j) now = now << 1; rep(ii,1,k) m = (m<<(i+j)) + now; if ( m > n ) ans += k - 1; else ans += k; } //计算ABABA形式 k = (len-i)/(i+j); if ( k * (i+j) + i < len ) ans+=k; else { ULL m = 0; ULL now = 0; rep(ii,1,i) now = now << 1 | 1; rep(ii,1,j) now = now << 1; rep(ii,1,k) m = (m<<(i+j)) + now; rep(ii,1,i) m = m << 1 | 1; if ( m > n ) ans += k-1; else ans += k; } } //计算单独的A形式 ans+=len-1; if ( (ULL)1<<len == n+1 ) ans++; return ans; } int main() { while( cin>>x>>y ) { if ( x == 0 ) printf("%lld\n",cal(y)); else printf("%lld\n",cal(y)-cal(x-1)); } return 0; }
