区间覆盖 & 线段覆盖 & 二分

这篇具有很好参考价值的文章主要介绍了区间覆盖 & 线段覆盖 & 二分。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

4195. 线段覆盖 - AcWing题库

P2082 区间覆盖(加强版) - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

做法:

void solve() {
    int n; cin>>n;
    vector<array<LL,2>> seg(n);
    for(auto &t: seg) cin>>t[0]>>t[1];
    sort(all(seg), [](array<LL,2> pre, array<LL,2> suf) {
        if(pre[0] == suf[0]) return pre[1] < suf[1];
        return pre[0] < suf[0];
    });
    vector<array<LL,2>> last;
    last.push_back(seg[0]);
    for(int i = 1; i < n; ++i) {
        if(seg[i][0] <= last.back()[1]) last.back()[1] = max(last.back()[1], seg[i][1]);
        else last.push_back(seg[i]);
    }
    LL ans = 0;
    for(auto &t: last) ans += t[1] - t[0] + 1;
    cout<<ans;
}

差分解决区间覆盖:(这题不能过,但是感觉这个做法有用)

void solve() {
    int n; cin>>n;
    vector<int> dif(1000 + 1);
    int rl = 0;
    rep(i,1,n) {
        int l, r; cin>>l>>r;
        dif[l]++;
        dif[r+1]--; rl = max(rl, r); 
    }
    int sum = 0;
    int now = 0;
    rep(i,1,rl) {
        now += dif[i];
        if(now > 0) sum++;
    }
    cout<<sum;
}

4195. 线段覆盖 - AcWing题库

问题描述: 坐标轴中共有多少个整数坐标的点满足恰好被 k条线段覆盖。

思路:离散化差分,用map(。根据差分可以找线段被多少哥线段覆盖。

代码:

void solve() {
    int n; cin>>n;
    map<LL,LL> mll;
    vector<LL> ans(n + 1);
    rep(i,1,n) {
        LL l,r; cin>>l>>r;
        mll[l]++;
        mll[r+1]--;
    }
    LL last = -1,sum = 0;
    for(auto t: mll) {
        LL f = t.vf, s = t.vs;
        if(last != -1) ans[sum] += f - last;
        sum += s;
        last = f;
    }
    rep(i,1,n) cout<<ans[i]<<" ";
}

二分 (nowcoder.com)

问题描述:根据对话,找可能的最多正确的对话。

思路:

​ 如果是 val +,说明猜的数val比答案要大,此时,答案在区间(-inf, val)

​ 如果是val -,说明猜的数val比答案要小,此时,答案在区间(val, inf)

​ 如果是val .,说明猜的数val等于答案,此时,答案在区间[val, val + 1)

​ 可以用差分求最大覆盖区间。数据离散,可以用map代替差分离散化。

代码:

void solve() {
    LL inf = LONG_LONG_MAX - 123456789;
    int n; cin>>n;
    map<LL,LL> mll;
    char op[2];
    rep(i,1,n) {
        int v; cin>>v>>op;
        if(op[0] == '.') { // 等于 [val, val + 1)
            mll[v]++, mll[v+1]--;
        }
        else if(op[0] == '+') { // 大 (-inf, v)
            mll[-inf]++;
            mll[v]--; 
        } else { // 小 (v+1, inf)
            mll[v+1]++;
            mll[inf]--;
        }
    }
    int ans = 0, sum = 0;
    for(auto t: mll) {
        sum += t.vs;
        ans = max(sum, ans);
    }
    cout<<ans;
}

【2023陕西训练营】day1 枚举和枚举优化 - Virtual Judge (vjudge.net)文章来源地址https://www.toymoban.com/news/detail-655372.html

到了这里,关于区间覆盖 & 线段覆盖 & 二分的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 线段树 区间赋值 + 区间加减 + 求区间最值

    线段树好题:P1253 扶苏的问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 区间赋值 + 区间加减 + 求区间最大。 对于区间赋值和区间加减来说,需要两个懒标记,一个表示赋值 cover ,一个表示加减 add 。 区间赋值的优先级大于区间加减。 对于区间赋值来说,需要将区间加减的

    2024年02月06日
    浏览(34)
  • 【枚举区间+线段树】CF Ehu 152 E

    Problem - E - Codeforces 题意: 思路: 感觉是个套路题 对区间计数,按照CF惯用套路,枚举其中一个端点,对另一个端点计数 对于这道题,枚举右端点,对左端点计数 Code:  

    2024年02月10日
    浏览(33)
  • 2023-07-26力扣每日一题-区间翻转线段树

    链接: 2569. 更新数组后处理求和查询 题意: 给两个等长数组nums1和nums2,三个操作: 操作1:将nums1的 [l,r] 翻转(0变1,1变0) 操作2:将 nums2[any] 变成 nums2[any]+nums1[any]*p ,p由操作给出,any表示数组里的每一位 操作3:查询nums2的和 解: 由于每次更新nums2的时候,不需要考虑

    2024年02月15日
    浏览(39)
  • 【leetcode难题】2569. 更新数组后处理求和查询【线段树实现01翻转和区间求和模版】

    关键就是记录每次操作2时,nums1中的1的个数 这就需要实现线段树进行区间反转以及区间求和

    2024年02月15日
    浏览(41)
  • 区间覆盖问题

    区间覆盖问题,一般可以抽象为给定一些小区间 ,从中选择一些区间,能够覆盖 ,求最少选择多少个小区间的问题。 一般有两种做法: 贪心、动态规划。 贪心法基于这样的考虑: 因为x=s这个点是必须要被覆盖的,在可以覆盖到s的小区间里,选择右端点最大的小区间,是最优

    2024年02月09日
    浏览(33)
  • 华为OD机试 - 最少数量线段覆盖 - 二叉树(Java 2023 B卷 100分 考试抽中题)

    华为OD机试 2023B卷题库疯狂收录中,刷题 点这里

    2024年02月11日
    浏览(48)
  • C++知识精讲15 | 三类基于贪心思想的区间覆盖问题【配套资源详解】

      博主主页:Yu·仙笙 配套资源:三类基于贪心算法覆盖问题-C++文档类资源-CSDN下载 专栏:C++知识精讲 目录 三类基于贪心思想的区间覆盖问题 情形1:区间完全覆盖问题 描述: 样例: 解题过程: 例题: 题意: 例题: 例题二: 思路: 情形2:最大不相交区间数问题 例题:

    2023年04月09日
    浏览(36)
  • 【算法】树状数组和线段树

    O ( l o g n ) O(logn) O ( l o g n ) :单点修改、区间查询 与前缀和的区别: 前缀和是离线的,每次动态修改原数组某个元素,都需要重新求一遍前缀和,因此单点修改是 O ( n ) O(n) O ( n ) 的,区间查询则是 O ( 1 ) O(1) O ( 1 ) 树状数组是在线的,单点修改和区间查询都是 O ( l o g n ) O(

    2024年02月19日
    浏览(46)
  • Segment Tree 线段树算法(java)

    什么是线段树算法: 线段树(Segment Tree)是一种基于树结构的数据结构,用于解决区间查询问题,例如区间最大值、最小值、区间和等。线段树是一种高度平衡的二叉树,每个节点都代表了一个区间。下面我们来详细了解一下线段树算法。 线段树的构建 线段树的构建过程可

    2024年02月16日
    浏览(40)
  • 算法41:掉落的方块(力扣699题)----线段树

    题目: https://leetcode.cn/problems/falling-squares/description/ 在二维平面上的 x 轴上,放置着一些方块。 给你一个二维整数数组  positions  ,其中  positions[i] = [lefti, sideLengthi]  表示:第  i  个方块边长为  sideLengthi  ,其左侧边与 x 轴上坐标点  lefti  对齐。 每个方块都从一个比目

    2024年02月22日
    浏览(42)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包