华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1260|回复: 2
打印 上一主题 下一主题

区间统计类题目

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-7-3 16:44:30 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
区间统计问题是信息学奥赛常出的题目,给定一个区间,其中满足条件的子区间。

一起来总结下这些题目:

1、总区间求和,最大值,最小值 这个很简单,其中同时求最大最小还可以递归;
2、区间最大最小值,一般可以使用ST表,线段树, 忠诚(P1816),
3、区间求和可以考虑前缀和,树状数组
3、长度K区间的最大最小值  一般用单调队列
4、区间线段覆盖问题:
     给定若干线段,求总的覆盖长度  线段的重叠
     给定若干线段,选择最多的线段互不重叠(工作安排问题)
     给定若干区间,用N条线段覆盖他们所有
5、区间上的二分 复制书稿,数列分段II
6、区间上的DP  复制书稿,乘积最大。
7、二维区间问题  最大的正方形, 二维和最大。8、单调栈 ,积水面积,删数游戏

后面这两个涉及到修改,暂时不整理、
8、区间合并问题9、区间填补  道路5019,浇花


how many wrong answer

双指针法,(统计天数,有点像队列)
单指针法, 1042乒乓球 ISBN
有些单指针法有点像堆栈

n*m的矩阵里面每个数字a(i)(j)就是i*j(行号和列号的乘积),求第k大。

1、P1317 低洼地 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36162
2、P1178 到天宫做客 http://www.hsyit.cn/forum.php?mod=viewthread&tid=35903   
3、P1496 火烧赤壁 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36164
4、P1567 统计天数 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36165

NOIP普及组这几年的第一二题都是区间类的 图书管理员,龙虎斗,公交换乘,求和等




回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
沙发
 楼主| 发表于 2020-3-8 19:34:31 | 只看该作者
连续区间最大和  两段最大和 环状最大和  二维平面的矩阵最大和
回复 支持 反对

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
板凳
 楼主| 发表于 2020-3-15 18:26:28 | 只看该作者
有很多区间的问题是变成线段树,splay,treap等树状结构来做,还有些是变成网状结构图来做。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 01:45 , Processed in 0.197341 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表