网络流24题,就不都水一篇题解了QWQ 但是这题的贪心做法比较有意思,所以就写一写,网上好像找不到比较完整的证明。
众所周知,网络流24题不需要网络流(doge)。
Statement
有 $n$ 根柱子,依次放入编号为 $1,2,3,\cdots $ 的球。每次只能在顶端放,且同一根中任何两个相邻球的编号之和为完全平方数。
求最多能放多少个球。
Solution
$\color{black}{小}\color{red}{卷猫}$ 曰:可以枚举答案转化为判定性问题。
那么就二分最多能放的个数,然后对于所有 $i+j=k^2(i<j)$ 的东西连边,跑最小路径覆盖即可。
但是!这道题还有更为优美的性质:贪心。也就是在已有的柱子上,能放就放,放不了新开,这样就是最优解。
这篇博客 给出了对于贪心正确性的证明,首先得到贪心的答案是
$$
f(n)=
\begin{cases}
(n^2-1)/2+n & n\equiv 1(\bmod 2)\\\\
(n^2-2)/2+n & n\equiv 0(\bmod 2)
\end{cases}
$$
如果最终答案比 $f(n)$ 大,那么至少放了 $f(n)+1$ 个球。
当 $n\equiv 1(\bmod 2)$ 时,即 $(n^2-1)/2+n+1$ 个。(另一种同理)
在 $1\sim (n^2-1)/2+n+1$ 个数中,最后 $n+1$ 个数最大和为 $n^2+2n<(n+1)^2$ ,最小和为 $n^2+2>n^2$ ,所以这 $n+1$ 个数必定属于 $n+1$ 个柱子,而不可能在 $n$ 个柱子中放下。于是贪心的答案就一定正确。
但是博客并没有给出 $f(n)$ 的通项式证明。
1 3 6 10 15 21 28 36 45 55
2 7 9 16 20 29 35 46 54
4 5 11 14 22 27 37 44 56
8 17 19 30 34 47 53
12 13 23 26 38 43 57
18 31 33 48 52
24 25 39 42 58
32 49 51
40 41 59
50
观察上面 $n=10$ 的情况,不妨设第 $i$ 个柱子最底下的数为 $g[i]$ ,根据贪心实现和上面的式子,等价于证明 $g[i]=\lfloor i^2/2\rfloor$ (当 $i>2$ 时)(事实上,这是数列 A007590 )。那么我们需要证明的就是 $\lfloor (n-1)^2/2\rfloor+1\sim \lfloor n^2/2\rfloor-1$ 之间的数可以被 $n-1$ 个柱子放下,而 $\lfloor n^2/2\rfloor$ 不行。不妨增设一个额外条件:在放上这 $n$ 个数之前,$n-1$ 个柱子顶端的数都是当前放好的最大的 $n-1$ 个数。
假设这个结论对 $n-1$ 成立。考虑 $n$ 。
如果 $n$ 为偶数,注意到有 $\lfloor (n-1)^2/2\rfloor +1+\lfloor (n-1)^2/2\rfloor=(n-1)^2$ ,那么 $\lfloor (n-1)^2/2\rfloor +1\sim \lfloor n^2/r\rfloor -1$ 的任何一个数都能和顶端的 $n-1$ 个数配对,但 $\lfloor n^2/2\rfloor$ 不能和其中任何一个配对。这样的情形对于偶数 $n$ 显然成立。
如果 $n$ 为奇数,有 $\lfloor (n-1)^2/2\rfloor +1+\lfloor (n-1)^2/2\rfloor-1=(n-1)^2$ ,那么 $\lfloor (n-1)^2/2\rfloor +1\sim \lfloor n^2-1\rfloor$ 都能和 $\lfloor (n-2)^2/2\rfloor+1\sim \lfloor (n-1)^2/2\rfloor-1$ 配对,此时上一组剩下的 $\lfloor (n-1)/2\rfloor$ 和当前剩下的 $\lfloor n^2/2\rfloor$ (也就是新的柱子的顶端)分别是顶端的数中的最小、最大值,并且依然满足顶端的数是最大的 $n$ 个数。
根据归纳假设,结论对任意 $n$ 都成立。
请问这题网络流和贪心哪个效率高啊
Orz
膜拜!像我数学就根本不行。
注意了注意了,这是小卷猫 Orz
欧欧欧阿rei