首页 > 其他分享 >ABC349D题解

ABC349D题解

时间:2024-08-09 11:05:54浏览次数:15  
标签:int 题解 long 枚举 ABC349D now

[ABC349D] Divide Interval 题解

传送门:
luogu | atcoder

题目简述

给定非负整数 \(l\) 和 \(r\)(\(l<r\)),令 \(S(l,r)\) 表示序列 \((l,l+1,\ldots,r-2,r-1)\),其中包含从 \(l\) 到 \(r-1\) 的所有整数。此外,一个序列被称为“好序列”,当且仅当它可以表示为 \(S(2^i j,2^{i}(j+1))\),其中 \(i\) 和 \(j\) 是非负整数。

解题思路

容易看出,使用贪心可以求解这个问题。即从左到右划分序列,每次划分的序列都是最大的即可。具体地,重复执行以下步骤:

  • 当前起点为 now。
  • 找到最大的合法 \(i\) 值,并反求 \(j\) 值。
  • 分离序列 \((2^ij,2^i(j+1))\)。
  • 将 now 更新为 \(2^i(j+1)\)。

如何找到最大的合法 \(i\) 值?

我们可以枚举 \(i\),然后判断反推出的 \(j\) 是否合法,当 \(j\) 不合法或此时右边界越界时,就退出枚举。

因为 \(2^i\) 是指数级增长的,所以枚举的次数不会超过 \(60\),不会超时。

注意:

  1. 需要使用 long long 存储数据。

  2. 如果使用位运算求解 \(2^i\) ,需要使用 (1LL << i),否则会因为爆出 int 范围而返回错误值 \(0\)。

AC 代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
int l, r;
signed main() {
    cin >> l >> r;
    int now = l, num = 0;
    queue<pair<int,int>>ans; 
    while (now < r) {
        int i = 0;
        do { // 枚举 i 值
            int pow = (1LL << i);
            // 判断合法性
            if (now % pow != 0) break;
            if (pow * ((now / pow) + 1) > r) break;
        } while (++i);
        i--, num++;
        int pow = (1LL << i);
        int j = now / pow;
        ans.emplace(pow * j, pow * (j + 1));
        now = pow * (j + 1);
    }
    cout << num << endl;
    while (!ans.empty()) {
        cout << ans.front().first << " " << ans.front().second << endl;
        ans.pop();
    }
    return 0;
}

标签:int,题解,long,枚举,ABC349D,now
From: https://www.cnblogs.com/Xiang-he/p/18350421

相关文章

  • AT_past202010_m 筆塗り 题解
    题目传送门前置知识线段树|树链剖分解法观察到要维护树上信息,且更改的呈链状,考虑进行树链剖分。将边权转化成点权,钦定边权给了深度更深的那个点,注意更新时不能更新\(\operatorname{LCA}\)。区间赋值和单点查询用线段树维护即可。代码#include<bits/stdc++.h>usingnam......
  • 如何避免自己问题解决缓慢导致项目周期延长
    在公司实习期间,我发现自己对业务的熟悉程度不足,导致在预期时间和实际完成时间上存在差异。虽然这种情况在后期有所改善,但前期的压力相对较大。为此,我总结了以下几点经验和改进措施:1.问题描述与现有分析我们今天的工作进展如何?当前诊断的调查进展如何?如果进展缓慢,是什么原因?需......
  • ABC349D题解
    [ABC349D]DivideInterval题解传送门:luogu|atcoder题目简述给定非负整数$l$和$r$($l<r$),令$S(l,r)$表示序列$(l,l+1,\ldots,r-2,r-1)$,其中包含从$l$到$r-1$的所有整数。此外,一个序列被称为“好序列”,当且仅当它可以表示为$S(2^ij,2^{i}(j+1))$,其中$i$和$j$......
  • # Cocos通过Electron打包web应用后,在触屏一体机设备触摸滑动无效问题解决
    Cocos通过Electron打包web应用后,在触屏一体机设备触摸滑动无效问题解决已经很晚了,刚刚解决这个问题,还是想记录一下,因为刚刚接触cocos没多久,这个问题困扰了我很久。背景接手了一个答题小游戏,由于涉及敏感信息就不在这里截图了,交接到我手里的是用cocos开发的,之前从来没有接触......
  • P8819题解
    题目大意现在有个有向图图,共有n个点,m条边总共有四种操作:操作1:将一条边打上标记操作2:将一个点出发的所有边打上标记操作3:将一条边移除标记操作4:将一个点出发的所有边移除标记打上标记的边视为被移除每次操作进行一次询问,如果每个点出度都是1,整张图是个强连通图,那么输出"YES......
  • 题解 洛谷P1478 陶陶摘苹果(升级版)
    题目传送门https://www.luogu.com.cn/problem/P1478截图来自洛谷:这道题就是这道题的升级版而已,我们可以定义一个结构体分别存抓当前苹果的力气与高度。之后进行从第1个苹果到第n个苹果的循环,判断当前苹果高度是否够,力气是否够。最重要的是要排序,因为要摘得苹果最多,所以要先......
  • Redis连接问题解决汇总
    Redis连接失败常见解决方案1.检查Redis命令行是否可以正常连接使用命令行客户端,输入:redis-cli-h虚拟机ip地址-p6379-aredis访问密码如若连接成功,输入ping,看控制台是否返回PONG此步骤若正常,则代表虚拟机可正常连接2.Redis命令行无法正常连接1)未打开Redis6379端口......
  • 牛客多校 A 题题解
    牛客多校8-AHaitangandGameGivenaset\(\textstyleS\),dXqwqandHaitangtaketurnsperformingthefollowingoperations,withdXqwqgoingfirst:Findapair\(\textstyle(x,y)\)suchthat\(\textstylex,y\inS\)and\(\textstyle\gcd(x,y......
  • ρars/ey 题解
    给个链接:ρars/ey。我们考虑一个树上背包。设\(f_{u,i}\)表示在\(u\)号节点的子树内删除\(i\)个点的最小代价。显然有答案为\(f_{1,siz_1-1}\)。接下来我们考虑转移。看这一张图:这里红圈内的东西为当前的\(siz_u\),绿圈部分为\(siz_j\)。我们枚举\(x\)为\(u\)子......
  • CF1514D Cut and Stick 题解
    不知道会不会更不好的阅读体验题目的关键步骤为求出区间绝对众数(频率高于\(\left\lceil\frac{len}{2}\right\rceil\))的出现次数,本文仅仅对这一问题进行探讨,剩余的解题步骤不难理解,可以参考其他题解。解法1考虑一个随机化的解法,从区间中随\(40\)个数,假定其为区间绝对众......