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面试专

    悠悠悠悠/ 0 赞/ 240 阅读

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

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

    桃扇骨桃扇骨/ 0 赞/ 149 阅读

    相关 Codeforces 1101D 点分治

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

    Myth丶恋晨Myth丶恋晨/ 0 赞/ 350 阅读

    相关 codeforces 278Div1 B题

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

    痛定思痛。痛定思痛。/ 0 赞/ 355 阅读