首页 > 其他分享 >[SHOI2009] 会场预约 题解

[SHOI2009] 会场预约 题解

时间:2023-10-04 21:23:57浏览次数:47  
标签:SHOI2009 预约 题解 线段 会场 要么

LG


  • 任意时刻每个点最多被一条线段覆盖
  • 暴力删每条线段是对的
  • 插入 \([l,r]\) 时需要删除的线段要么被 \([l,r]\) 包含,要么覆盖 \(l\) 或 \(r\)

性质非常强所以做法非常多

一种比较神奇的:对于两条线段 \([l_{1},r_{1}],[l_{2},r_{2}]\),定义 < 为 \(r_{1}<l_{2}\),即线段 \(1\) 完全在线段 \(2\) 左边。据此定义的 == 即为两线段有交

set<pair<int,int>> 维护集合 \(S\),不断 finderase 即可

code

标签:SHOI2009,预约,题解,线段,会场,要么
From: https://www.cnblogs.com/ft61/p/17742757.html

相关文章

  • 题解 accoders::NOI 5511【漂亮轰炸(bomb)】
    题解accoders::NOI5511【漂亮轰炸(bomb)】http://47.92.197.167:5283/contest/406/problem/4BZOJ3252是弱化版。problem一棵树,边带权。\(Q\)次询问,给定\(k\)和一个首都点,选择\(k\)条路径轰炸,其中必须由一轮要轰炸首都,但没有要求每条路径都经过首都。每条边只能被炸一次,......
  • 题解 P9695【[GDCPC2023] Traveling in Cells】
    显然,询问的答案即为\(x\)所在的极长的满足颜色均在\(\mathbb{A}\)内的连续段的权值和。如果我们能维护对颜色的单点修改,以及求出某个位置所在极长连续段的左右端点\(l,r\),只需要树状数组即可求出答案。一个朴素的想法是对每种颜色开一棵线段树,单点修改是平凡的,极长连续段左......
  • 题解 P9702【[GDCPC2023] Computational Geometry】
    这题一看就不是计算几何,考虑区间DP。设凸多边形的\(n\)个顶点依次为\(P_1,P_2,\cdots,P_n\)。设\(f_{i,j}\)在\(i<j\)时表示\(P_i,P_{i+1},\cdots,P_{j-1},P_j\)组成的多边形的直径的平方,在\(i>j\)时表示\(P_i,P_{i+1},\cdots,P_n,P_1,\cdots,P_{j-1},P_j\)组......
  • 题解 P9697【[GDCPC2023] Canvas】
    好题。后面的操作会覆盖前面的操作,这东西不好处理,我们不妨时光倒流,将问题转化为一个位置一旦被填了数,就再也不会变了。如果解决了这个问题,只需将操作序列倒过来,就得到了原问题的解。显然,所有\(x_i=y_i=2\)的操作会最先被执行,所有\(x_i=y_i=1\)的操作会最后被执行。只需要给......
  • 高橋君 题解
    AtCoder天下一プログラマーコンテスト2014本戦高橋君题意给定\(n,k\),求\[\sum\limits_{i=0}^{k}\dbinom{n}{i}\]多测,\(1\len,k,T\le10^5\)。题解可以考虑使用莫队求解,下文讲述如何移动指针。\(n\rightarrown+1\)根据杨辉三角递推式\(\dbinom{n}{m}=......
  • 题解 P2674 《瞿葩的数字游戏》T2-多边形数
    题目描述给你一个正整数数\(n\),问你它是不是多边形数\(K\),如果是,设\(K_1\)是最小的\(K\),\(K_2\)是次小的\(K\),输出\(K_1\)和\(K_2\)。具体思路我们主要来看上面这张表里有什么规律。性质1:\(1\)是任何一个多边形数。性质2:\(2\)不是任何一个多边形数。性......
  • 情报破译 题解
    \(d<n\le2e5,m\le10,1\lep\le10^9,0\lea_i\le1e9\)每个位运算之间独立,所以我们可以构造一个\(\{2^{k-1},2^{k-1}.....\}\)和一个\(\{0,0,0...\}\)的数组,让他们倍增去做如上运算,最后用他们把\(p\)轮拼出来,我们就知道了\(i\)位置上二进制下第\(j\)位如果是\(0\)......
  • 国标GB28181协议下视频监控平台EasyGBS播放器起播慢或延迟高问题解决方案
    GB28181视频监控国标平台EasyGBS是基于国标GB28181协议、支持多路设备同时接入的视频监控/视频云服务平台,支持对多平台、多终端分发RTSP、RTMP、FLV、HLS、WebRTC等格式的视频流。国标GB28181平台EasyGBS可提供视频直播监控、云端录像、云存储、检索回放、智能告警、语音对讲、平......
  • P1025 [NOIP2001 提高组] 数的划分 题解
    题目传送门本题共有两种方法,分别是递归深搜和动态规划方法一:递归深搜Solution从小到大一一枚举每一个划分的数,。只要找到一种方案就记录,具体细节代码中有注释。Code#include<bits/stdc++.h>usingnamespacestd;intn,k,ans;voiddfs(intstart,intstep,intsum){......
  • 【题解】Typo
    TypoDescreption求反转一个不合法的括号序列中的一位使其成为一个合法序列的方案数(保证方案一定存在)Solution其实也就是一道较复杂的模拟题先判断哪一类括号数量更多,因为一定是将数量多的括号改成数量少的才有可能变为合法序列,这里就先用左括号举例记录每个位置时没有配对的......