CF 768B

CF 768B
题意：
In each operation Sam must remove any element x, such that x>1, from the list and insert at the same position x/2,x%2,x/2 sequentially. He must continue with these operations until all the elements in the list are either 0 or 1.
给定一个数N，对大于1的数在原来的位置拆分为N/2，N%2，N/2三个数。对拆分出的大于1的数同样进行拆分，直至所有的数均为0或1。
Now the masters want the total number of 1s in the range l to r (1-indexed).
对拆分后的0/1序列，询问L到R区间中1的数量

类似于线段树的区间查询
思路1：简单题，递归思想。对于给定的N，可以计算出最终0/1序列的长度。递归模拟，一层层往下分解，将得到的数分解到序列的对应指定位置中，当无法分解时则返回值，最后递归得到区间内所有的1的个数
      这里我担心被卡，用了一个位运算小优化。其实不用也可以。
Code：
#include<cstdio>
typedef long long ll;
ll n,ql,qr,len=1,ans;
ll dfs(ll n,ll l,ll r){
   if(n==0||l>qr||r<ql) return 0;
   if(n==1) return 1;
   ll mid=l+r>>1;
   return dfs(n>>1,l,mid-1)+dfs(n&1,mid,mid)+dfs(n>>1,mid+1,r);
}
int main(){
   scanf("%I64d%I64d%I64d",&n,&ql,&qr);
   for(ll x=n;x>1;x>>=1,len=len<<1|1);
   ans=dfs(n,1,len);
   printf("%I64d\n",ans);
   return 0;
}
思路2：求出区间端点的前缀和相减，拆分的个数符合f(n)=2*f(n-1)+1，而n拆后的区间和一定是n，所以用二分找出端点位置即可

巴特西

CF 768B

最新文章

热门文章