首页 > 代码库 > HDU 5694 分治+规律
HDU 5694 分治+规律
http://acm.hdu.edu.cn/showproblem.php?pid=5694
此题一开始我也找到了规律,也知道是分治可是,,,想的太复杂了没写开,
我一直想的通过L,R两个参数分治,可是由于左右的不对称,分治写起来感觉有点力不从心,,,最后看到别人的容斥才恍然大悟= =
答案不就是R之前的个数减去L-1之前的吗,一个参数写起来就简单了,将在右边的部分转化为左边然后加加减减就是答案啦!
注意2幂的打表,之前用的qpow()结果T了= =
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 LL f[65]={1}; 5 LL solve(LL x,LL n) 6 { 7 if(!x) return 0; 8 if(x==1) return 1; 9 LL mid=f[n-1]; 10 if(x>mid){ 11 return 1+f[n-2]+((x-mid)-(f[n-2]-solve(f[n-1]-1-x+mid,n-1))); 12 } 13 else if(x==mid) return 1+f[n-2]; 14 else return solve(x,n-1); 15 } 16 int main() 17 { 18 int t,i; 19 for(i=1;i<=60;++i) f[i]=f[i-1]*2; 20 LL L,R; 21 scanf("%d",&t); 22 while(t--){ 23 scanf("%lld%lld",&L,&R); 24 printf("%lld\n",solve(R,60)-solve(L-1,60)); 25 } 26 return 0; 27 }
HDU 5694 分治+规律
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。