网站开发工具安卓版,做网站就是做信息整合,国内外网站开发的现状,男女直接做视频教学视频网站无限序列
题目大意#xff1a;
有这样一个规则#xff1a;1.把“1”变成“10” 2.把“0”变成“1” 一个序列的第一位是“1” 然后是#xff1a;“10”#xff0c;“101”…… 序列无限次操作后会得到“1011010110110101101……” 问某一个区间内有多少个“1”
原题
有这样一个规则1.把“1”变成“10” 2.把“0”变成“1” 一个序列的第一位是“1” 然后是“10”“101”…… 序列无限次操作后会得到“1011010110110101101……” 问某一个区间内有多少个“1”
原题
题目描述
我们按以下方式产生序列 1、 开始时序列是 “1” 2、 每一次变化把序列中的 “1” 变成 “10” “0” 变成 “1”。 经过无限次变化我们得到序列1011010110110101101…。 总共有 Q 个询问每次询问为在区间A和B之间有多少个1。 任务 写一个程序回答Q个询问
输入
第一行为一个整数Q后面有Q行每行两个数用空格隔开的整数a, b。
输出
共Q行每行一个回答
输入样例
1
2 8 输出样例
4 数据范围
1⩽Q⩽50001⩽a⩽blt;2631 \leqslant Q \leqslant 5000 1 \leqslant a\leqslant b lt; {2}^{63}1⩽Q⩽50001⩽a⩽b263
解题思路
首先暴力是不可能的 我们可以发现这就是一个斐波那契
1 10 101 10110 10110101
1 10 101 10110 10110101然后写上1的个数和长度
1 1 1
10 1 2
101 2 3
10110 3 5
10110101 5 8可以发现他们都是斐波那契数列而且长度为下一个数的1的个数 我们就可以先预处理前100项第100项⩾263\geqslant {2}^{63}⩾263然后可以用其中的一些项拼成1~A-1B的1的个数然后用前缀和原理一减就可以了
代码
#includecstdio
#define ull unsigned long long
using namespace std;
int n;
ull x,y,a[105];
ull ask(ull dep)
{ull js,ans0,nowdep;while (now){js1;while (a[js2]now) js;//先找最大的可拼的now-a[js1];//减去ansa[js];//计算结果}return ans;
}
int main()
{a[1]1;a[2]1;for(int i3;i100;i)a[i]a[i-1]a[i-2];//预处理scanf(%d,n);for (int i1;in;i){scanf(%llu %llu,x,y);printf(%llu\n,ask(y)-ask(x-1));//前缀和}
}
