首页 > 其他分享 >YACS2022年10月乙组

YACS2022年10月乙组

时间:2023-04-11 09:11:48浏览次数:58  
标签:10 int 线段 ans 乙组 last1 端点 last2 YACS2022

T1:录制节目

可以将原题转化成

有 \(n\) 条线段,可以保留若干条线段,并且可以分成两部分,使得每部分的线段互不相交

先将所有线段按右端点做升序排序,且按左端点做降序排序
然后维护两个变量 last1last2
last1:第一个部分的最后的端点
last2:第二个部分的最后的端点
尽量让 \(\min(\operatorname{last1}, \operatorname{last2})\) 更小

原题:P2255

代码实现
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using P = pair<int, int>;

struct line {
    int l, r;
    bool operator<(const line& o) const {
        if (r == o.r) return l > o.l;
        return r < o.r;
    };
};

int main() {
    int n;
    cin >> n;
    
    vector<line> d(n);
    rep(i, n) cin >> d[i].l >> d[i].r;
    
    sort(d.begin(), d.end());
    
    int ans = 0;
    int last1 = 0, last2 = 0;
    for (auto [l, r] : d) {
        if (last1 < last2) swap(last1, last2);
        if (l >= last1) {
            ans++;
            last1 = r;
        }
        else if (l >= last2) {
            ans++;
            last2 = r;
        }
    }
    
    cout << ans << '\n';
    
    return 0;
}

标签:10,int,线段,ans,乙组,last1,端点,last2,YACS2022
From: https://www.cnblogs.com/Melville/p/17305043.html

相关文章

  • 每日学习记录20230410_Bert
    20230410:BertHuggingface今天运行python-c'fromtransformersimportTFBertForTokenClassification'的时候有一个报错:Couldnotloaddynamiclibrary'libcudart.so.11.0'.查了一下发现是需要装CUDA软件,也就是英伟达调用GPU的软件,使用:condainstallcudatoolkit命......
  • 2023.4.10每日总结
    今天在课堂上未能成功完成老师布置的任务,之后在宿舍一整晚茶不思饭不想的一直在进行编程。在分页上没有遇到太大困难,但在添加条件查询之后就有点难以处理。明天一定会完美完成建民老师的这次课堂小测......
  • 1019. 链表中的下一个更大节点
    1019.链表中的下一个更大节点给定一个长度为 n 的链表 head对于列表中的每个节点,查找下一个更大节点的值。也就是说,对于每个节点,找到它旁边的第一个节点的值,这个节点的值严格大于它的值。返回一个整数数组answer,其中answer[i]是第i个节点(从1开始)的下一个......
  • 4.10今日总结
    今天学习了分页功能<!DOCTYPEhtmlPUBLIC"-//W3C//DTDXHTML1.0Transitional//EN""http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><htmlxmlns="http://www.w3.org/1999/xhtml"><head><metahttp-equiv=&qu......
  • 2023-04-10 网络流和最大流问题
    网络流和最大流问题1网络流和最大流问题阐述网络流基本概念网络流图中,从源点出发,在满足每条边容量限制的条件下,汇点t最多能接收多少流量s:sourcet:target网络流需要满足的限制容量限制平衡限制:除了源点s和汇点t,对于每一个点,流入量等于流出量从源点s流出的流量,一定......
  • 20230410 训练记录:最小瓶颈路 / lca
    初识最小瓶颈路其实是上海那道著名的铜牌题,其次就是P1396营救。P1967[NOIP2013提高组]货车运输/最小瓶颈路https://www.luogu.com.cn/problem/P1967\(\mathcalO(m\logm+(n+q)\logn)\)最大生成树(森林)两点间最小边权,直接在倍增lca向上爬的时候更新答案。问......
  • Perfect P-th Powers UVA - 10622
     给出n,写成n=x^p的形式,求p最大值#include<iostream>#include<vector>#include<cmath>#include<algorithm>usingnamespacestd;#defineintlonglongintflg=0;intgcd(intx,inty){ returny==0?x:gcd(y,x%y);}voidsov(in......
  • 2023年4月10日(软件工程日报)
    今日首先完成老师布置的课堂作业,耗时6,7个小时,主要都集中在分页显示,之前一直下滑显示,分页一直没用用过,一直想在网上直接套用代码,总是报错,最终找到一个完整讲解,进行的套用。之后是团队作业方面,今天继续学习深度学习前向传播与后向传播 ......
  • 2023.4.10
    考虑全面,int类型会导致小鸡除以3后抹去后面的小数部分,导致情况多出。 ......
  • 10-面向对象综合训练综合练习
    练习一:文字版格斗游戏需求:​ 格斗游戏,每个游戏角色的姓名,血量,都不相同,在选定人物的时候(new对象的时候),这些信息就应该被确定下来。举例:​ 程序运行之后结果为:​ 姓名为:乔峰 血量为:100​ 姓名为:鸠摩智 血量为:100​ 乔峰举起拳头打了鸠摩智一下,造成了XX点伤害,鸠摩智还剩......