下山

今天是小X跟隨師父學習編程的最后一天，這天早晨師傅給了他一個列表，列表中已有一個數(shù)n(0 <= n < 2^50)。

師傅告訴小X：“從現(xiàn)在開始，對于列表里的每個大于1的數(shù)x，你要先刪掉它，然后用 x/2 , x%2 , x/2 三個數(shù)插入他原本的位置，直到?jīng)]有數(shù)大于1，

傍晚時我會給你一個區(qū)間 [ l , r ]，你要告訴我列表內(nèi)下標位于此區(qū)間內(nèi)的1的個數(shù)”( l >= 1 , r >= 1 )

小X想出色的完成任務讓師傅放心，他已經(jīng)寫了大部分代碼了，你能幫他完成剩下的兩個空嗎。

#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;
}
思路：首先我們要明白的是函數(shù)參數(shù)代表的是什么？cal(n,l,r)，n代表的是當前要替換的數(shù)字，l和r代表的是當前n轉(zhuǎn)化之后的坐標范圍[l,r]。這一點要明白，如果l>mid的話說明，要去找當前n的右區(qū)間，而接著往下走的時候就變成了cal（n/2,）。我們要計算的是上一個n的[l,r]在n/2的范圍是什么？這是容易混淆的一點。如果前兩個條件都不符合的話，說明就要找兩個區(qū)間了，還是要注意上面那一點，除此之外，還要記得判斷(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)/~

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的蓝桥训练之下山的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。