蓝桥训练之下山

下山

今天是小X跟随师父学习编程的最后一天，这天早晨师傅给了他一个列表，列表中已有一个数n(0 <= n < 2^50)。

师傅告诉小X：“从现在开始，对于列表里的每个大于1的数x，你要先删掉它，然后用 x/2 , x%2 , x/2 三个数插入他原本的位置，直到没有数大于1，

傍晚时我会给你一个区间 [ l , r ]，你要告诉我列表内下标位于此区间内的1的个数”( l >= 1 , r >= 1 )

小X想出色的完成任务让师傅放心，他已经写了大部分代码了，你能帮他完成剩下的两个空吗。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n;
ll l,r;
ll length(ll n)
{
if(n<=1) return 1;
return 2*length(n/2)+1;
}
ll cal(ll n,ll l,ll r)
{
if(l>r||l<=0||r<=0||n0)
return 0;
if(n1)
return 1;
ll len=length(n);
ll mid=len/2+1;
if(r<mid)
return cal(n/2,l,r);
else if(l>mid)
return _______________;
else
return _______________;
}
int main(int argc, char const *argv[]) {
scanf("%lld%lld%lld",&n,&l,&r);
printf("%lld\n",cal(n,l,r));
return 0;
}
思路：首先我们要明白的是函数参数代表的是什么？cal(n,l,r)，n代表的是当前要替换的数字，l和r代表的是当前n转化之后的坐标范围[l,r]。这一点要明白，如果l>mid的话说明，要去找当前n的右区间，而接着往下走的时候就变成了cal（n/2,）。我们要计算的是上一个n的[l,r]在n/2的范围是什么？这是容易混淆的一点。如果前两个条件都不符合的话，说明就要找两个区间了，还是要注意上面那一点，除此之外，还要记得判断(n%2是否为1。
代码如下：

#include <bits/stdc++.h> #define ll long long using namespace std; ll n; ll l,r; ll length(ll n) {if(n<=1) return 1;return 2*length(n/2)+1; } ll cal(ll n,ll l,ll r) {if(l>r||l<=0||r<=0||n==0)return 0;if(n==1)return 1;ll len=length(n);ll mid=len/2+1;if(r<mid)return cal(n/2,l,r);else if(l>mid)return cal(n/2,l-mid,r-mid);//elsereturn cal(n/2,l,mid-1)+cal(n/2,1,r-mid)+(n%2);// } int main(int argc, char const *argv[]) {while(~scanf("%lld%lld%lld",&n,&l,&r))printf("%lld\n",cal(n,l,r));return 0; }

努力加油a啊，(^o)/~

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的蓝桥训练之下山的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。