hdu 5694 BD String (递推)

el/2024/4/19 22:47:16

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;
}

 

 


http://www.ngui.cc/el/3419445.html

相关文章

hdu 5695 Gym Class (拓扑排序)

https://vjudge.net/problem/387991/origin 众所周知&#xff0c;度度熊喜欢各类体育活动。 今天&#xff0c;它终于当上了梦寐以求的体育课老师。第一次课上&#xff0c;它发现一个有趣的事情。在上课之前&#xff0c;所有同学要排成一列&#xff0c; 假设最开始每个人有一个…

hud 5689 瞬间移动(组合数+逆元)

http://acm.hdu.edu.cn/showproblem.php?pid5698 有一个无限大的矩形&#xff0c;初始时你在左上角&#xff08;即第一行第一列&#xff09;&#xff0c;每次你都可以选择一个右下方格子&#xff0c;并瞬移过去&#xff08;如从下图中的红色格子能直接瞬移到蓝色格子&#xf…

多态中成员变量的使用

Dog 继承 Animal 类&#xff0c; 多态中成员变量没有重写。

Java之数据结构

前言 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类&#xff1a; 枚举&#xff08;Enumeration&#xff09;位集合&#xff08;BitSet&#xff09;向量&#xff08;Vector&#xff09;栈&#xff08;Stack&#xff09;字典&#xff08;Dictio…

各种办法解决IntelliJ IDEA控制台输出中文乱码问题

output输出乱码 试了网上很多办法 网上流行的方法&#xff1a;https://blog.csdn.net/liu865033503/article/details/81094575 都没有解决&#xff01;&#xff01;&#xff01; 重点要在 也有可能是c盘下的C:\Users\你自己的用户名\.IntelliJIdea2019.1\config配置下还有一…

IDEA 显示Cannot resolve plugin org.apache.maven.plugins:maven-site-plugin:3.3

今天将IntellIJ IDEA 关于Maven的配置总结一下&#xff0c;方便以后可参考。 一.配置Maven环境 前提是jdk环境变量已经配置好 1.下载apache-maven文件&#xff0c;选择自己需要的版本&#xff0c;地址&#xff1a; http://maven.apache.org/download.cgi 2.解压下载文件&…

javaweb项目前端找不到后台servlet解决办法

原因是注解里面没加 urlPatterns"/XXXXX" servlet必须是3.0以上 成功运行&#xff1a;

实现简单的用户名校验,是否存在(ajax)

实现百度注册框的用户名校验功能&#xff1a; 在输入框内输入一个用户名&#xff0c;如果此用户名存在&#xff0c;则红色显示一段文字&#xff0c;否则绿色显示 用的是Jquery和jackson 目录结构&#xff1a; 前端index.html: <!DOCTYPE html> <html lang"en&…

ccf 201909-2 小明种苹果(续)

#include<bits/stdc.h> using namespace std;bool vis[20005]; //第i棵树是否掉过苹果 int main() {long n, ans_sum 0, ans_has 0, ans_con 0;cin >> n;for(int i 1; i < n; i){int start, m, x;bool flag true;cin >> m >> start;for(int j…

const位置的含义

int num 1024; const int num2 num1; //只能第一次赋值 num2 2048 // 报错const int * p &num; //const 在 * 前面时&#xff0c;指针的位置可以修改&#xff0c;但不能通过指针修改指向的变量 int const * p &num; //同上 int * const p &num;//const 在 …