【ybt高效进阶强化训练1-1-3】无限序列
序列 高效 进阶 无限 ybt
2023-09-27 14:28:28 时间
无限序列
题目链接:ybt高效进阶强化训练1-1-3
题目
我们按以下方式产生序列:
1、 开始时序列是: “1” ;
2、 每一次变化把序列中的 “1” 变成 “10” ,“0” 变成 “1”。
经过无限次变化,我们得到序列"1011010110110101101…"。
总共有 Q 个询问,每次询问为:在区间A和B之间有多少个1。
任务:写一个程序回答Q个询问
输入
第一行为一个整数Q,后面有Q行,每行两个数用空格隔开的整数a, b。
输出
共Q行,每行一个回答
输入样例
1
2 8
输出样例
4
数据范围
1 <= Q <= 5000
1 <= a <= b < 263
思路
这道题我们可以用斐波那契来做。
我们发现每一次变化出来的序列中,它的长度和1的个数都是斐波那契数列。
那么我们就可以先预处理出斐波那契数列的前很多项(反正我这里是前100项,这样够大,而且不够存就会自动溢出),接着我们可以用一些项拼成区间 1~a-1 和 1~b,同时计算出这两个区间1的个数。
那么这样我们就可以用前缀和的思想求出区间a~b的1的个数了。
代码
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
unsigned long long t,a[101],x,y;
unsigned long long find(unsigned long long now)//求区间1和now之间有多少个1
{
unsigned long long ans=0,j;//初始化
while (now)//还可以拆分
{
j=1;
while (a[j+2]<=now) j++;//寻找可以减的
ans+=a[j];//加上一的个数
now-=a[j+1];//减(拆分)
}
return ans;
}
int main()
{
scanf("%llu",&t);//读入
a[1]=1; a[2]=1;//初始化
for (int i=3;i<=100;i++)
a[i]=a[i-1]+a[i-2];//斐波那契
for (unsigned long long i=1;i<=t;i++)
{
scanf("%llu%llu",&x,&y);//读入
printf("%llu\n",find(y)-find(x-1));//利用前缀和求出答案,然后输出
}
return 0;
}
相关文章
- 动态模态分解 DMD | 做高维时间序列数据短时预测
- 动手学深度学习实践—文献阅读(双头序列到序列(attention)插补水质模型dual-SSIM)
- 异常检测:综述(基本都是无监督算法)【时间序列算法:AR/MA/ARMA】【传统机器学习算法:孤独森林、One Class SVM】【深度学习算法:AutoEncoder、LSTM、DeepLog】
- AI-蛋白质-结构预测-2020:AlphaFold【输入:氨基酸序列】【输出:结构的性质(氨基酸之间两两的距离分布,氨基酸链的夹角分布)】【根据预测的性质构建约束,从而求解出拓扑结构】
- 推荐模型-序列推荐-2016:GRU4Rec、GRU4RecF、GRU4RecKG
- 推荐模型-序列推荐-2022:CORE
- SE、GRE序列
- 序列相关的趣题 之中的一个
- 算法-最长子序列和C/C++实现(三个复杂度)
- AcWing 895. 最长上升子序列
- 【ybt高效进阶4-1-2】【luogu P1631】序列合并
- 【ybt高效进阶强化训练1-1-4】序列个数(分类讨论)
- 【ybtoj高效进阶 21171】简单序列(DP)
- 【ybtoj高效进阶 21274】相似序列(主席树)(哈希)(二分)
- 【ybtoj高效进阶 21175】DNA 序列(SAM)
- 四十六、python学习之Django框架(DRF框架二):序列/反序列化器的定于与使用