http://acm.hdu.edu.cn/showproblem.php?pid=5694
众所周知,度度熊喜欢的字符只有两个:B和D。
今天,它发明了一种用B和D组成字符串的规则:
S(1)=BS(1)=B
S(2)=BBDS(2)=BBD
S(3)=BBDBBDDS(3)=BBDBBDD
…
S(n)=S(n−1)+B+reverse(flip(S(n−1))S(n)=S(n−1)+B+reverse(flip(S(n−1))
其中,reverse(s)reverse(s)指将字符串翻转,比如reverse(BBD)=DBBreverse(BBD)=DBB,flip(s)flip(s)指将字符串中的BB替换为DD,DD替换为BB,比如flip(BBD)=DDBflip(BBD)=DDB。
虽然度度熊平常只用它的电脑玩连连看,这丝毫不妨碍这台机器无与伦比的运算速度,目前它已经算出了S(21000)S(21000)的内容,但度度熊毕竟只是只熊,一次读不完这么长的字符串。它现在想知道,这个字符串的第LL位(从1开始)到第RR位,含有的BB的个数是多少?
Input
第一行一个整数TT,表示T(1≤T≤1000)T(1≤T≤1000) 组数据。
每组数据包含两个数LL和R(1≤L≤R≤1018)R(1≤L≤R≤1018) 。
Output
对于每组数据,输出S(21000)S(21000)表示的字符串的第LL位到第RR位中BB的个数。
Sample Input
3 1 3 1 7 4 8
Sample Output
2 4 3
首先用a[i] 存储第i个字符串的长度, 因为l ,r 小于10^18, 所以只需要开到a[60] 就可以了 (2^60 > 10^18)
get(x) 求 1 ~ x中B的个数
举个例子:
第一个红框中B的个数为c, 第二个为a, 第三个为b;
如果我要求箭头处(x)的前缀的B的个数 sum = c + a + 1 + b
因为取反再反转,所以 a和b是互补的, 所以 a 和 b 中 B 的个数 等于 len(a), 也就是a的长度
而 len(a) = x - a[3] - 1 , 加上中间的一个B,可以抵消 - 1
c中B的个数就用递归求
所以 get(x) = get(a[i] - x ) + (x - a[i] - 1 ) + 1 == x - a[i-1] + get(a[i] - x);
#include <bits/stdc++.h>
using namespace std;
using lon = long long;lon a[65];lon get(lon x)
{if(x == 0) return 0;for(int i = 1; i <= 60; i++){if(a[i] == x)return x / 2 + 1;if(x < a[i])return x - a[i-1] + get(a[i] - x);}
}int main()
{for(int i = 1; i <= 60; i++)a[i] = a[i-1] * 2 + 1;int T;cin >> T;while(T--){lon l, r;cin >> l >> r;// cout << get(l-1) << endl;cout << get(r) - get(l-1) << endl;}return 0;
}