max、逻辑与绝对值_随笔
JueFan 一只绝帆

max、逻辑与绝对值

在诸多时候(例如组合计数),我们很方便处理加与乘,此时 max⁡\max 这种东西对我们是一个头疼的东西。

同样令我们头疼的还有逻辑与、逻辑或、绝对值,这些东西在一定前提下是可以互相转化的,显然将所有形式转化到一起,有利于我们观察性质。

叙述完了目的,我们开始正文。

max 的性质

max⁡(a,a)=a\max(a,a)=a 配合上交换律结合律使得 max⁡\max 是一个很有性质的运算,++ 对 max⁡\max 还有分配律,甚至 min⁡\min 对 max⁡\max 也有分配律。

同向的 max⁡\max 可以让我们拆掉很多东西,很典型的,倘若我们的“贡献”指的是对答案取 max⁡\max,那么 max⁡(a,b)\max(a,b) 贡献到答案,就不如 a,ba,b 贡献到答案。

max⁡\max 运算不可逆是它唯一的缺点,也是通常它令我们头疼的点。

逻辑

很经典的,max⁡(a,b)≤c  ⟺  a≤c∧b≤c,max⁡(a,b)≥c  ⟺  a≥c∨b≥c\max(a,b)\le c\iff a\le c\wedge b\le c,\max(a,b)\ge c\iff a\ge c\vee b\ge c。

通常更有用的是第一个,因为复杂问题下,给出的诸多“限制”自带逻辑与的含义,a≤c∧b≤ca\le c\wedge b\le c 虽然增加了条件的个数,但是却化简了条件。

当然,后者也很有用,因为当 a,b,ca,b,c 都是一坨式子的时候,将其变为可以移项的不等式实在是很有用的一件事。

下面给出一个例子,这在 Exchange Arguments 问题及其变种中十分有用:

max⁡(fx,fy−gx)<max⁡(fy,fx−gy)  ⟺  (fx<max⁡(fy,fx−gy))∧(fy−gx<max⁡(fy,fx−gy))  ⟺  ((fx<fy)∨(fx<fx−gy))∧((fy−gx<fy)∨(fy−gx<fx−gy))  ⟺  ((fx<fy)∨(gy<0))∧((gx>0)∨(fx+gx>fy+gy))\begin{aligned}& \max(f_x,f_{y}-g_x)< \max(f_y,f_x-g_y)\\&\iff\left( f_x< \max(f_y,f_x-g_y)\right)\wedge\left( f_y-g_x< \max(f_y,f_x-g_y)\right)\\&\iff \left((f_x<f_y)\vee (f_x< f_x-g_y)\right)\wedge \left((f_y-g_x<f_y)\vee (f_y-g_x< f_x-g_y)\right)\\&\iff\left((f_x<f_y)\vee (g_y<0)\right)\wedge \left((g_x>0)\vee (f_x+g_x>f_y+g_y)\right)\end{aligned}

不去深究具体含义,这确实为我们带来了很直观的等价版本。

同样的方式也可以用来处理集合的交并,不过直接对交并统计的题目较为冷门,此处不展开。

绝对值

绝对值与 max⁡\max 的互转同样很常用。

很经典的,∣a−b∣=max⁡(a−b,b−a)|a-b|=\max(a-b,b-a),这在 曼哈顿距离 中十分常用(简单例题:[AGC034D] Manhattan Max Matching),例如如果我们要求距离每个点的最大曼哈顿距离,由于求最大值,所以 max⁡\max 的结合律可以让我们拆掉内层的 max⁡\max,于是我们可以用 2kn2^k n(kk 是维数)的复杂度求解。

例题:[ARC107F] Sum of Abs。

本题就把 max⁡∣∑b∣\max |\sum b| 拆成了"所有 bb 的符号必须相同即可贡献到答案",然后再用一些网络流技巧来限制符号相同。

还有一个容易忽视的转化:max⁡(a,b)=a+b+∣a−b∣2\max(a,b)=\frac{a+b+|a-b|}{2},如果我们把加和乘看作“没有代价”的话,那么这个式子实现了 max⁡(a,b)\max(a,b) 和 ∣a−b∣|a-b| 的直接转化,若 a−ba-b 能化简那再好不过。

例题:CF2062F。

给定序列 a,ba,b,一个完全图,w(i,j)=max⁡(ai+bj,aj+bi)w(i,j)=\max(a_i+b_j,a_j+b_i),对每个 kk 求 kk 条边的最短哈密顿路。

n≤3000n\le 3000。

max⁡(ai+bj,aj+bi)=ai+bi+aj+bj+∣ai+bj−aj−bi∣2\max(a_i+b_j,a_j+b_i)=\frac{a_i+b_i+a_j+b_j+|a_i+b_j-a_j-b_i|}{2}

忽略掉除以 22,对一条路径,前面的贡献就是 2(∑a+∑b)−(a+b)first,last2(\sum a+\sum b)- (a+b)_{first,last},后面的贡献就是将位置视作 xi=(ai−bi)x_i=(a_i-b_i),不断移动的路程。

显然,固定 first,lastfirst,last,后面的贡献最小是 2(max⁡x−min⁡x)−∣xfirst−xlast∣2(\max x-\min x)-|x_{first}-x_{last}|。

到这里已经可以 dp\rm dp 了,按照 xx 排序后,设 fi,j,0/1/2f_{i,j,0/1/2} 表示前 ii 个,选了 jj 个,无 first,lastfirst,last/有其一/都有,min⁡x\min x 的贡献在 jj 由 00 变为 11 时算,max⁡\max 的贡献可以统计答案时算。

 评论
评论插件加载失败
正在加载评论插件
由 Hexo 驱动 & 主题 Keep
总字数 237.9k 访客数 访问量