P2765 魔术球问题

wjh2022 · 2024-07-16 08:48:50 · 题解

拿到题目，手玩 n 较小的情况即可发现，「最多放入的球的数量」似乎是成规律增长的，将得到的放置方法整理出来，即可得到贪心策略，本文将基于如下的贪心策略进行证明：

对于任意 n，基于 n-1 得到的放置方法，接下来，对于任意一个球：

• 若无法在已有的柱子上放，则新开一个柱子，将该球放入。

• 若可以在已有的柱子上放，则将该球放入。

• 否则，球无法放入，放置结束，得到了 n 的答案。

这样得到的答案是呈 +2+2+4+4+6+6 规律增长的。

接下来，我们尝试证明该贪心

首先，将递推式用通项公式表示出来，记 a_i 表示有 i 个柱子时的最大值，则有

1. a_{2k-1}=2k^2-1,k \in Z_+
2. a_{2k}=2k^2+2k-1,k \in Z_+

两个式子的证明是类似的，故只给出一式的证明，如下：

证明构造结果最大，即证 2k^2 无法放入。

在所有正确的贪心构造中，都有一个性质：最上面一层的球的大小是连续的。

故上面一层的球大小为 [2k^2-2k+1,2k^2-1]。

此时，因为

所以无法放入 2k^2。

下证上文性质为何成立。

若最上面一层并非 [2k^2-2k+1,2k^2-1]，则在该区间内必有一个球不在最上面一层。

又因为对于任意一个球，设其大小为 x，则其上方的球的大小一定大于 x，故对于上面的区间，必有两个大小在其中的球上下相邻。

设这两个球的大小和为 sum，则因为

故该情况不成立，得证上界。

因为我们易证 n=1 的答案，故证明以上式子的结果可以由构造达到，即证一式成立时二式成立，且二式成立时一式成立，最后使用数学归纳法即可。

以下证明二式成立时一式成立。

证明一式的构造结果可以达到，则因为

则依照构造，在新柱子上放入 2k^2-2k，由于此时球的最上面一层是连续的，故有：

故可达到一式结果，证毕。

因为这是篇题解，所以要给出 \text{code}。

//#pragma GCC optimize (2)
#include <bits/stdc++.h>
//#include <windows.h>
#define ll long long
#define mid (l+r>>1)
#define lowbit(x) (x&-x)

using namespace std;
const int N = 60;

int n;
int h[N];   // h[i] 表示第 i 个柱子的高度 
int a[N][N];    // a[i][j] 表示第 i 个柱子，从下往上数第 j 个球的大小 

bool check(int x, int y)    // 判断 x+y 是否为完全平方数
{
    int k = 1;
    while (k * k <= x + y)
    {
        if (k * k == x + y) return true;
        k ++ ;  
    }
    return false;
}

signed main()
{
    cin >> n;

    int tot = 0, now = 1;   // tot 表示已经开了的柱子数量，now 表示目前应该放的球的大小（注意，并非已经放的最大球的大小！P2765 魔术球问题） 
    for (int i = 1; i <= n; i ++ )  // 递推计算 n=i 时的答案 
    {
        while (true)
        {
            bool flag = true;
            for (int j = 1; j <= tot; j ++ )
                if (check(a[j][h[j]], now))
                {
                    h[j] ++ , a[j][h[j]] = now ++ ;
                    flag = false;
                    break;
                }

            if (flag == true)   // 无法放入，则新开一个柱子，若亦无法新开柱子，则已得到 n=i 的一个结果 
            {
                if (tot < i)    tot ++ , h[tot] = 1, a[tot][1] = now, now ++ ;
                else break;
            }
        }
    }

    int sum = 0;
    for (int i = 1; i <= n; i ++ )  sum += h[i];
    cout << sum << "\n";
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= h[i]; j ++ )   cout << a[i][j] << " ";
        cout << "\n";
    }

    return 0;
}

upd on 2024.11.25：才发现以前原来有人做过类似的证明/kel，这下尴尬了。

从以球数为自变量，最少的柱子数量为因变量（大概）的证明：here

一个看起来很厉害但我没看懂的：here