tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> IT/计算机 >>

国家集训队2008论文集浅谈信息学竞赛中的区


浅谈信息学竞赛中的区间问题

华东师大二附中 周小博

引言
在信息学竞赛中,有很多问题最终都能转 在信息学竞赛中, 化为区间问题. 化为区间问题. 这类问题变化繁多,解法各异.论文归纳 这类问题变化繁多,解法各异. 总结出了几种常用模型, 总结出了几种常用模型,我们将对它们做 简要分析. 简要分析.

1.最大区间调度问题 1.最大区间调度问题
数轴上有n个区间,选出最多的区间, 数轴上有n个区间,选出最多的区间,使得 这些区间不互相重叠. 这些区间不互相重叠. 算法: 算法: 按右端点坐标排序 依次选择所有能选的区间

2.多个资源的调度问题 2.多个资源的调度问题
有n个区间和无限多的资源,每个资源上的 个区间和无限多的资源, 区间之间不互相重叠. 区间之间不互相重叠.将每个区间都分配 到某个资源中,使用到的资源数量最小. 到某个资源中,使用到的资源数量最小.

定义区间集合深度d 定义区间集合深度d为包含任意一点的区间 数量的最大值 至少需要d 至少需要d个资源 算法1 算法1: 计算出d 计算出d 按左端点坐标排序 依次将区间任意地分配到d 依次将区间任意地分配到d个资源中

实现
记录每个资源的最大右端点 O(nd)

用二叉堆维护这些坐标

O(nlogd)

计算d 也可以不用计算) 计算d(也可以不用计算) 按右端点坐标排序 每个区间都分配到右端点坐标最大的可用 资源中. 资源中.

算法2 算法2:

平衡二叉树 O(nlogd)

3.有最终期限的区间调度问题 3.有最终期限的区间调度问题
有n个长度固定,但位置可变的区间,将它 个长度固定,但位置可变的区间, 们全部放置在[0,+∞)上 们全部放置在[0,+∞)上.每个区间有两 个已知参数:长度t 和最终期限d 个已知参数:长度ti和最终期限di,设fi为 其右端点坐标. 其右端点坐标.定义

fi di li = 0

if f i > d i L = max{li } 1≤i ≤ n if f i ≤ d i

放置所有区间, 放置所有区间,使它们不互相重叠且最大 延迟L最小. 延迟L最小.

最终期限d 最终期限 i

算法: 算法: 按最终期限排序 顺序安排各区间

4.最小区间覆盖问题 4.最小区间覆盖问题
有n个区间,选择尽量少的区间,使得这些 个区间,选择尽量少的区间, 区间完全覆盖某线段[s,t]. 区间完全覆盖某线段[s,t]. 算法: 算法: 按左端点坐标排序 每次选择覆盖点s 每次选择覆盖点s的区间中右端点坐标最大 的一个,并更新s 的一个,并更新s 直到所选区间已包含t 直到所选区间已包含t

5.带权区间调度,覆盖问题 5.带权区间调度, 带权区间调度

例题: 例题:USACO 2005 dec silver 仓库从第M秒到第E 仓库从第M秒到第E秒的任意时刻都 需要有人打扫. 个工人, 需要有人打扫.有N个工人,每人 给出自己的工作时间段:从第T1秒 给出自己的工作时间段:从第T1秒 到第T2秒 需要支付工资S 到第T2秒,需要支付工资S元. 录用一部分人,要保证从M秒到第E 录用一部分人,要保证从M秒到第E 秒的任意时刻都得有人打扫, 秒的任意时刻都得有人打扫,问最 少要付多少工资. 少要付多少工资.

转化
问题转化为:在一些带权区间中, 问题转化为:在一些带权区间中,选出一 部分,使它们覆盖[M,E]上的所有整数点 上的所有整数点, 部分,使它们覆盖[M,E]上的所有整数点, 求权和最小值. 求权和最小值. 算法:按右端点坐标排序,做动态规划 算法:按右端点坐标排序, 状态:f[i]=覆盖 覆盖[M,T2 状态:f[i]=覆盖[M,T2i]的权和最小值 方程: 方程:
if M ∈ [T 1i , T 2i ] if M [T 1i , T 2i ]

Min{f [ j ] | T 2 j + 1 ≥ T 1i }+ Si f [i ] = 1≤ j <i Si

优化1 优化1
建立线段树[M,E] 建立线段树[M,E] 得到f[i] 插入在T2 得到f[i] 插入在T2i处 计算f[i]:选取区间[T1 计算f[i]:选取区间[T1i-1,T2i-1] 中的最小值进行状态转移

优化2 优化2
建立一个栈 保持栈中区间f 保持栈中区间f值的单调性 状态转移 二分查找:O(logN) 二分查找: 栈的维护: 栈的维护:O(N)

优化3 优化3
按左端点坐标排序 维护一个二叉堆, 维护一个二叉堆,以f值为关键字 状态转移 删除右端点坐标太小的区间) (删除右端点坐标太小的区间)

6.区间和点的有关问题 6.区间和点的有关问题
有n个区间,m个点.若某区间包含了某点, 个区间, 个点.若某区间包含了某点, 则构成一对匹配关系. 则构成一对匹配关系.选出最多的区间和 相同数量的点, 相同数量的点,使对应的区间和点构成匹 配关系. 配关系.

算法: 算法:
所有点按坐标排序 选取包含该点且右端点坐标最小的区间

优化
维护二叉堆: 维护二叉堆: 按区间左端点排序, 按区间左端点排序,得到有序表 插入左端点小于等于该点坐标的区间 删除右端点小于该点坐标的区间 取出右端点坐标最小的与该点匹配并删除 维护二叉堆, 维护二叉堆,以区间右端点为关键字 所有点按坐标从小到大依次处理

总结
有序性 算法的选择 优化——数据结构的选择 优化——数据结构的选择


推荐相关:

国家集训队2008论文集浅谈信息学竞赛中的区._图文.ppt

国家集训队2008论文集浅谈信息学竞赛中的区. - 浅谈信息学竞赛中的区间问题


国家集训队2008论文集浅谈信息学竞赛中的区_图文.ppt

国家集训队2008论文集浅谈信息学竞赛中的区 - 浅谈信息学竞赛中的区间问题 华


国家集训队2008论文集浅谈信息学中状态的合._图文.ppt

国家集训队2008论文集浅谈信息学中状态的合. - 浅谈信息学状态的合理设计与


国家集训队2008论文集浅谈信息学中状态的合.doc

国家集训队2008论文集浅谈信息学中状态的合 - 浅谈信息学状态的合理设计与应用 浅谈信息学状态的合理设计与应 浅谈信息学状态的合理设计与应用 合理设计与 ...


国家集训队2008论文集部分贪心在信息学竞赛_图文.ppt

国家集训队2008论文集部分贪心在信息学竞赛 - 部分贪心在信息学竞赛中的应用


国家集训队2008论文集部分贪心在信息学竞赛.doc

国家集训队2008论文集部分贪心在信息学竞赛 - 清华附中 高逸涵 部分贪心思想在信息学竞赛中的应用 部分贪心思想在信息学竞赛中的应用 贪心 清华附中 高逸涵 (gaoyi...


国家集训队2008论文集浅谈最短路径问题中的.doc

国家集训队2008论文集浅谈最短路径问题中的 - NOI Winter Camp 2008 浅谈最短径路问题中的分层思想 福建省泉州市第七中学 吕子 摘要 分层思想与最短路径算法...


国家集训队2009论文集浅谈信息学竞赛中的“.pdf

国家集训队2009论文集浅谈信息学竞赛中的“ - 浅谈信息学竞赛中的0 和 1


国家集训队论文:浅谈信息学竞赛中的“0”和“1”_图文.ppt

国家集训队论文:浅谈信息学竞赛中的“0”和“1” - “1与0, 一切数字的神奇


国家集训队论文分类.xls

国家集训队论文分类_计算机软件及应用_IT/计算机_...2008 2009 2009 2004 2007 2002 2007 2009 2009 ...《浅析倍增思想在信息学竞赛中的应用》 李睿:《...


NOI国家集训队论文分类(至2008)(摘抄自C博客).doc

NOI国家集训队论文分类(至2008)(摘抄自C博客)_学科竞赛_高中教育_教育专区。...《浅谈信息学竞赛中的线性规划简洁高效的单纯形法实现 与应用》 置换群 ...


国家集训队2007论文集6.李宇骞《浅谈信息学_图文.ppt

国家集训队2007论文集6.李宇骞《浅谈信息学 - 浅谈信息学竞赛中的线性规划


国家集训队2009论文集浅谈估价函数在信息学.pdf

国家集训队2009论文集浅谈估价函数在信息学 - 浅谈估价函数在信息学竞赛中的应用 浙江省绍兴一中 周而进 1 目录 摘要 关键字 前言 1估价函数在搜索中的应用 1.1...


国家集训队2009论文集信息学竞赛中概率问题_图文.ppt

国家集训队2009论文集信息学竞赛中概率问题 - 走进概率的世界 信息学竞赛中概率问题求解初探 信息学竞赛中概率问题求解初探 安徽省合肥一中 1 22 梅诗珂 引言...


国家集训队2008论文集 计算几何中的二分思_图文.ppt

国家集训队2008论文集 计算几何中的二分思 - 计算几何中的二分思想 贵阳市第


国家集训队2008论文集 论文.pdf

国家集训队2008论文集 论文 - 运用化归思想解决信息学中的数列问题 余林韵


国家集训队2008论文集非完美算法初探任.doc

国家集训队2008论文集非完美算法初探任 - 非完美算法的应用 河北唐山


国家集训队2008论文集浅谈随机化思想在几何_图文.ppt

国家集训队2008论文集浅谈随机化思想在几何 - 感受随机的美 浅谈随机化思想在几何问题中的应用 广东中山一中 顾研 引入 随着信息学的发展,近几年,各种各样...


国家集训队论文分类整理.pdf

国家集训队论文分类整理来源: 洪雁书的日志距离 NOI 时间越来越少了,选择性地...《染色法和构造法在棋盘上的应用》 2008 - 周小博《浅谈信息学竞赛中的区间...


中国国家集训队论文集目录(1999-2009).txt

《论C++语言在信息学竞赛中的应用》黄源河:《浅谈图论模型的建立与应用》金恺:...国家集训队2008论文集 Day1 1.曹钦翔《数据结构的提炼与压缩》 2.郑暾《平衡...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com