题意:起初,序列中仅有数n,if(n!=0 && n!=1) 在原来的位置补充3个元素n/2 n/%2 n/2 。 直至该序列用仅有0和1。现在问区间[l,r]有多少个1
思路:一开始想用vector模拟,感觉实现起来很麻烦,很繁琐。 去网上看了题解,首先要求出对于当前的n,一共能拆分成多少个元素(仅为0和1),那么区间长度就是[1,len]确定下来。接着去枚举每一个位置的值是0还是1(递归)。
数据分析:0 ≤ n < 250, 0 ≤ r - l ≤ 105, r ≥ 1, l ≥ 1
复杂度分析:递归层数最多150层
// 很少做递归的题,这题也是看了题解才会的
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans=0;
void query(ll n,ll l,ll r,ll nl,ll nr)
{
if(nr<l || nl > r || n==0) return ;
if(n==1)
{
ans++;
return ;
}
ll mid=l+r >> 1;
query(n/2,l,mid-1,nl,nr);
query(n%2,mid,mid,nl,nr);
query(n/2,mid+1,r,nl,nr);
}
int main(void)
{
ll n,l,r;
cin >> n>> l>> r;
ll len=1,n1=n;
while(n1>1)
{
len=len*2+1;
n1/=2;
}
query(n,1,len,l,r);
cout << ans << endl;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)