Codeforces 768B - Code For 1(分治思想)

喜欢ヅ旅行 2021-12-22 08:07 682阅读 0赞

768B - Code For 1

思路:类似于线段树的区间查询。

代码:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define mem(a,b) memset((a),(b),sizeof(a))
  5. int query(ll L,ll R,ll n,ll l,ll r)
  6. {
  7. if(L>r||R<l||!n)return 0;
  8. if(n==1)return 1;
  9. ll m=(l+r)>>1;
  10. return query(L,R,n/2,l,m-1)+query(L,R,n%2,m,m)+query(L,R,n/2,m+1,r);
  11. }
  12. int main()
  13. {
  14. ios::sync_with_stdio(false);
  15. cin.tie(0);
  16. ll n,l,r;
  17. cin>>n>>l>>r;
  18. ll L=0,x=n;
  19. while(x)L=L*2+1,x>>=1;
  20. cout<<query(l,r,n,1,L)<<endl;
  21. return 0;
  22. }

转载于:https://www.cnblogs.com/widsom/p/7345521.html

发表评论

表情:
评论列表 (有 0 条评论,682人围观)

还没有评论,来说两句吧...

相关阅读

    相关 算法思想-分治算法

    tip:作为程序员一定学习编程之道,一定要对代码的编写有追求,不能实现就完事了。我们应该让自己写的代码更加优雅,即使这会费时费力。 推荐:[体系化学习Java(Java面试专

    相关 归并排序——主要思想分治

    归并排序——主要思想分治 1.随机取其中的一个值,将其分为两边,最后两边分别进行递归排序 2.归并,把两个有序的序列合并成一个有序的序列 ![在这里插入图片描述][w

    相关 Codeforces 1101D 点分治

    题意:有一颗树,每个点有一个点权,边权都是1,问路径上的所有点的gcd不是1的最长路径是多少? 思路:之前补这道题的时候,用分解质因数 + 树形DP做的,其实用点分治可以更暴

    相关 codeforces 278Div1 B

    虚拟参赛的时候没想到是线段树,看到很多人都过了,也蛮着急的。 首先用二分+线段树的方法更新DP\[i\]:它表示以A\[i\]为结尾可以最前到哪个位置; 再用线段树计算an