HDU 5587 Array 规律+递归

HDU 5587
题意:初始序列a为{1},操作:在序列a末尾添加一个0之后,复制一遍0前面的数 然后将0之后的数+1(包括0).
现在对序列a重复操作100次.Q次询问 每次询问一个m 求出序列a前m个数之和, Q<=2e3,m<=1e16.


初始长度为1 每次操作后序列长度*2+1 len[i]=2^i(i+1) -1
容易知道第i次操作后 序列的和为 s[i]=2*s[i-1]+len[i-1] 第i次添加2^i个数字 总和f[i]=s[i-1]+2^i.
前m个数=f[1]+f[2]+...f[i] + r 

因为第i+1段可以递归分解 剩下r个数递归求解即可.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5e2+5,M=59;
ll n,pw2[N],f[N],s[N];
void init()
{
pw2[0]=1;
for(int i=1;i<M;i++)
pw2[i]=pw2[i-1]*2ll;
f[0]=1,s[0]=1;
for(int i=1;i<M;i++)
{
s[i]=s[i-1]*2ll+pw2[i];
f[i]=s[i-1]+pw2[i];
//	printf("%d %lldn",i,f[i]);
}
}
ll calc(int i,ll x)
{
if(x==0)
return 0;
if(x==pw2[i])
return f[i];
if(x<pw2[i-1])
return calc(i-1,x);
//
pw2[i-1]=<x<pw2[i]
return f[i-1]+calc(i-1,x-pw2[i-1])+x-pw2[i-1];
}
int main()
{
int T;
init();
cin>>T;
while(T--)
{
scanf("%lld",&n);
int id=0;
ll ans=0,sum=0;
while(sum+pw2[id]<n)
sum+=pw2[id],++id;
id--;
for(int i=0;i<=id;i++)
ans+=f[i];
ans+=calc(id+1,n-sum);
printf("%lldn",ans);
}
return 0;
}

最后

以上就是动听咖啡为你收集整理的HDU 5587 Array 规律+递归的全部内容，希望文章能够帮你解决HDU 5587 Array 规律+递归所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。