题意: 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
- 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, 所以用二分找出端点位置即可
来源: http://www.bubuko.com/infodetail-3219399.html