x \leq |x|

利用此式可以通过放缩不等式来把一些较难的问题简单化。

全局平面最远点对

举个简单的例子,我们给定 n 个点,查询平面最远点对。假设最远的两个点为 ab ,那么我们即要最大化 |x_a - x_b| + |y_a - y_b|

利用放缩,我们把每个 x_a - x_bx_b - x_a 都计算对答案的贡献( y 同理)那么最后的答案仍然相同。

洛谷4131 [WC2005]友好的生物 ▷ 2019-01-07

首先 c 没什么卵用,我们直接把他乘到属性里。可以发现这里的 d 是两个属性值减一减的绝对值,所以我们要考虑放缩

我们先考虑 K = 1 的情况,先把这些生物按照 d 的大小排个序,那么后一个减前一个的值一定就是非负的,也就等于绝对值,直接扫一遍就好了。

接下来考虑 K \not = 1 的时候的前 K - 1 位,枚举每个属性的正负把他们一起取最大值。 第 K 位采用之前 K = 1 的时候的方法,减一减扫过去。

CF1093G Multidimensional Queries ▷ 2019-01-07

照样放缩。考虑到 2 ^ 5 并不是很大,我们可以暴力枚举每个数的符号(用状态压缩的方式)。然后维护一棵线段树进行修改和查询即可。

这是一篇旧文,经重新整理后放出

约束与放缩

多项式多点求值与快速插值学习笔记
上一篇 «
洛谷5219 无聊的水题 I
» 下一篇