fogflea
fogflea
发布于 2025-12-19 / 30 阅读
0
0

乱学数学-FME

起因是某道九省联考题:

0<a<b<c<1,满足a+b \leq 1 或者 b\geq 2a,求(\max\{b-a,c-b,1-c\})_{\min}

其实第一眼看到这题脑子立马蹦出来二分答案。。。(已中 OI xxxer_bound 型病毒,晚期,无救

我不会什么聪明的做法,只好枚举了六种情况把它做出来了,对每种情况用各种不等式乱搞一通,总算是搞出来了。

然后发现这貌似还算简洁的方法。

然后就是上个周末,在刷 B 站的时候,看到了这么个视频标题:

用傅里叶消元法解决九联填空最后一题

我心中一惊,傅里叶消元法?貌似在哪看过啊?然后打开 OI-wiki,检索了一下,果然出现了 FME 的身影,啊,原来我每种情况的干想是可以规范化的!

浅浅算一下 FME(傅里叶-莫茨金消元法)的时间复杂度,O(n^{2^n}) ,嗯,以算法竞赛的角度看并不优,但放到这题 n 如此之小的版本可谓是绰绰有余。

以这题为例,设 x 为所求,题目的两个条件为两类,每类 x 可分别为 b-a,c-b,1-c 三种情况,所以总共六种情况,随便挑一种情况:

\left\{ \begin{aligned} &a+b\leq 1\\ &x=b-a\\ &x\geq c-b\\ &x\geq 1-c \end{aligned} \right.

规范化一下:

\left\{ \begin{align} &a+b-1\leq 0\;\;\;\;\\ &a-b+x=0\\ &b-c+x\geq 0\\ &c+x-1\geq 0 \end{align} \right.

首先可以利用 (2) 将 b 消掉。

\left\{ \begin{aligned} &2a+x-1\leq 0\\ &a-c+2x\geq 0\\ &a+c+2x-1\geq 0 \end{aligned} \right.

接下来才是 FME 真正开搞的时候(其实 (2) 也能拆分为两个不等式 a-b+x\leq 0a-b+x\geq 0),首先要选定本次要消的元,比如说 a 。( x 肯定不行,因为要求的是 x ),那么就把 a 搞得特别一点,比如说移到一边(我这样是不是有点形式主义了,算了我喜欢这样

\left\{ \begin{aligned} &a\leq \frac{-x+1}{2}\\ &a\geq c-2x\\ &a\geq 1-c-2x \end{aligned} \right.

那么这其实和下面这个方程组是等价的:

\left\{ \begin{aligned} &\frac{-x+1}{2}\geq c-2x\\ &\frac{-x+1}{2}\geq 1-c-2x \end{aligned} \right.

然后重复此过程就行啦。


评论