OI 第4页

努力向前, 永不言弃.

[POJ3714]Raid[分治,平面最近点对]

cgazn阅读(140)评论(0)赞(0)

题面 根据题目要求, 求的是两组点之间的最短距离, 在求距离的时候把同一组里面点之间的距离看做inf就变成一个普通的平面最近点对问题. 平面最近点对问题用分治做, 先把点按照横坐标排序, 以中间的点为分界不断分成两个区间, 直到区间内只剩2...

[POJ1328]Radar Installation[贪心]

cgazn阅读(84)评论(0)赞(0)

题面 首先这道题容易想到降维, 一个点P(x, y)能够被圆心O在X轴上的一个圆覆盖, 等价于O在线段[$latex x-\sqrt{r^2-y^2}$, $latex x+\sqrt{r^2-y^2}$]上. 这样就转化为要用最少的点标记...

OI知识总结大纲

cgazn阅读(2711)评论(0)赞(0)

考试总结 模板题 基础数论知识总结 2019暑假数学课笔记 注意事项与奇技淫巧总结 初赛笔记

[POJ3190]Stall Reservations[贪心]

cgazn阅读(83)评论(0)赞(0)

题面 首先要把牛按照开始时间升序排序, 不然安排一头牛时这头牛开始时间之前我们都管不了了, 可能造成浪费一段正好可以安排后面一头开始时间更早的牛的空档. 而按开始时间排序后就能线性的安排每头牛, 保证安排到每一头牛时这头牛的开始时间之前已经...

[POJ3614]Sunscreen[贪心]

cgazn阅读(99)评论(0)赞(0)

题面 贪心策略: 奶牛按照minSPF降序排序, 对于每只奶牛尽量选符合要求且SPF大的防晒霜, 若没有符合要求的防晒霜就去除这只牛. 证明: 由于每头参加晒太阳的牛都要涂防晒霜, 所以我们要多用防晒霜. 按minSPF降序排序后, 对于某...

[CH0601]Genius ACM[倍增]

cgazn阅读(120)评论(0)赞(0)

题面(CH暂时无法访问) 为了划分出最少的段数, 我们必须使每一段在校验值不超过T的前提下尽可能长. 以一段的开头为L, 结尾为R, 于是问题就转化成了已知L的情况下怎样找到一个尽量大的R使校验值不超过T. 为了求出校验值, 要对序列进行排...

[CF670C]Cinema[离散化]

cgazn阅读(140)评论(0)赞(0)

题面 n个人m个电影, 最多涉及$latex n+m\times 2$种语言, 把语言离散化之后可以直接开个大数组统计每门语言会的人数, 然后选出符合要求的电影. 本题的意义在于规范了我离散化的写法.(俗称板子题). 离散化可以理解为一种把...

[POJ3784]Running Median[堆]

cgazn阅读(99)评论(0)赞(1)

题面 题目要求动态维护中位数, 每当序列长为奇数时输出(也就是输出第i/2+1小的数). 设当前序列长为i, 我们把整个序列按升序分为第1~i/2小, 第i/2+1小两部分. 资瓷动态插入并维持有序的数据结构容易想到堆. 对左半边和右半边分...