【FZSZ2017暑假提高组Day6】bd

问题描述

S(1)=B

S(2)=BBD

S(3)=BBDBBDD

S(n)=S(n−1)+B+reverse(flip(S(n−1))

其中，reverse(s)指将字符串翻转，比如reverse(BBD)=DBB，flip(s)指将字符串中的B替换为D，D替换为B，比如flip(BBD)=DDB。求：S(2^1000)的第L位（下标从1开始）到第R 位，含有的B的个数？

输入格式

第一行一个整数T表示数据组数T。每行2个整数L，R。（1<=L<=R<=Si）Si范围见数据规模。

输出格式

每组数据输出一行。

输入样例

输出样例

2
4
3

数据规模与约定

测试点1：T=10，Si= $10^{6}$

测试点2：T=100，Si= $10^{6}$

测试点3：T=1000，Si= $10^{6}$

测试点4：T=1，Si= $5 * 10^{7}$

测试点5：T=1000，Si=50000000

测试点6：T=1，Si= $10^{18}$

测试点7：T=10，Si=1000000000000000000

测试点8：T=100，Si=1000000000000000000

测试点9：T=1000，Si=1000000000000000000

测试点10：T=1000，Si=1000000000000000000

题解

吴大爷出的题越来越不清真，神特么分治，半天没想出来。看来还是我太弱了啊23333.

这题问的是b的个数，所以可以预处理出S1， S2.....S62的个数，然后就可以通过分治来求解了。

这里要注意一下，求[l, r]区间内的答案等于求[1,r] - [1,l-1]的答案，这样写代码比较舒服。

然后为什么是62因为2^62>10^18

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define LL long long
 6 using namespace std;
 7 const int M = 63;
 8 LL b[M], al[M], ans;
 9 int T;
10 LL solve(LL r, int now)
11 {
12     if(r == al[now-1]) return b[now-1];
13     if(r == al[now-1] + 1) return b[now-1] + 1;
14     if(r < al[now-1]) return solve(r, now-1);
15     LL tmp = al[now-1] - (r - al[now-1] - 1);
16     return al[now-1]- (tmp - solve(tmp, now-1)) + 1;
17 }
18 void init()
19 {
20     b[1] = al[1] = 1;
21     for(int i=2; i<=62; ++i)
22         al[i] = al[i-1] * 2 + 1, b[i] = al[i-1] + 1;
23 }
24 int main()
25 {
26     LL l, r;
27     init();
28     scanf("%d", &T);
29     while(T--)
30     {
31         scanf("%lld %lld", &l, &r);    
32         ans = solve(r, 62) - solve(l-1, 62);
33         printf("%lld
", ans);
34     }
35     return 0;
36 }