Tony102's Blog - 前缀和
type: channel
link: https://tony102.com/index.php/tag/%E5%89%8D%E7%BC%80%E5%92%8C/
items: 《廊桥分配》问题研究

《廊桥分配》问题研究
type: item
date: 2021-11-02T11:43:00+08:00
description: 前情提要菜鸡托在考场上狂写了二分，萎了；三分，萎了；二分+范围暴力（40 + 10)。对这个题的答案函数到底长成什么样子非常好奇，因为二分三分全部萎了。花了两个小时发现了一些奇妙的事情，很有价值拓展。这篇 blog 就来分析一下。答案函数假如我们设国内分配 $x$ 个廊桥的时候，最多停靠 $f(x)$ 次航班，国外的同理有 $g(y)$。我们知道 $x+y=n$。暴力做法是，我们枚举 $x$，然后 $O(n \log (m_1+m_2)) = O(n \log n)$ 地算答案。这样总共是 $O(n^2 \log )$ 的。当 $x$ 单增时，$y$ 单减；同时 $f(x)$ 单调不降，$g(y)$ 单调不增。这样答案就是 $h(x) = f(x) + g(n-x)$这样的函数到底有单不单峰，答案很显然不单峰。但是假如你跟我一样傻逼，就会先认为它单调再认为它单峰。随便举一个例子都能 hack 掉这个，例如初等函数中 $\sin, \cos$ 函数都可以 hack 掉这个。我们枚举每一个 $x$ ，然后把它的 $(x,c_1), (y,c_2)$ 打印出来，然后在 Geogebra 上描点绘图。注意不要使用 polynomial ，这个东西好像不支持点太多来插值出一个多项式函数。只能用 Fitpoly, 后面有一个 Degree of Polynomial 的参数可以控制多项式度数。还有一个事情就是，这样我们只能得到整数上的点，所以拟合出来的函数不太准确。所以我在每一个 $[x,x+1]$ 中间都插了三个点，函数值就是四等分。这样让函数比较平滑。性质上也更加准确。花了很长时间根据样例 3 画了一个图，长这样：暴力算答案的代码：int judge(int x) { std::priority_queue < int, vector < int >, greater < int > > q; int y = n - x; int c1 = 0, c2 = 0; for (int i = 1; i <= m1; ++ i) { while (!q.empty() && q.top() <= a1[i].l) q.pop(); if (q.size() + 1 <= x) q.push(a1[i].r), ++ c1; } while (!q.empty()) q.pop(); for (int i = 1; i <= m2; ++ i) { while (!q.empty() && q.top() <= a2[i].l) q.pop(); if (q.size() + 1 <= y) q.push(a2[i].r), ++ c2; } if (ans < c1 + c2) return ans = c1 + c2, 1; else return 1; }明显 $h(x)$ 多峰。如果还是非要利用 $f(x)$ 和 $g(x)$ 单调的性质，可以试试一个 $O(n \log ^3 n)$ 的算法：二分 $x, y$ ，然后 $O(n \log n)$ 检验。可惜并没有这一档分。无聊：多项式定义 $n$ 为一常量，则：$h(x) = f(x) + g(n-x)$看到这个式子，你很想卷一下。但是奈何中间是个 $+$ 号，但是没有关系，你知道指数运算可以帮助你：$e^{h(x)} = e^{f(x)} \cdot e^{g(n-x)} = e^{f(x)+g(n-x)}$然后呢？没有然后了。因为三个函数并不是一个多项式，上面那张图的函数是我们拟合出来的。所以想求出 $e^{h(x)}$ 之后再背包做不了。纯粹就是我一次失败的尝试（无聊暴力和正解回头看看上面贴的我的考场暴力代码，不禁感觉这玩意儿怎么跟正解这么像....假如在 while (!q.empty() && q.top() <= a1[i].l) q.pop(); 这一句后面把弹出的东西用一个堆把它存下来，后面 ++ c1 的时候从这个堆里面取，就变成了正解....看到这里，你不禁再次感叹写这篇 blog 的人是个大傻逼。看看正解中有一段叫做：求前缀和 的步骤。for (int i = 0; i <= n; ++ i) ans = std::max(ans, s1[i] + s2[n - i]);想把这个 $s_1, s_2$ 打印出来一探究竟。突然你发现，把第二列反转一下，这些就是描点的时候 $f(x), g(x)$ 的值。日！！！！！！！！！！！！可能这个时候你已经感受到了一些东西。让我们来理一理这到底是怎么回事。再次回到 $f(x)$ 和 $g(x)$ 上，$f(x)$ 是怎么算出来的：$f(x-1) + \Delta \to f(x)$。其中 $\Delta$ 在这道题中就是廊…