P9762 [ROIR 2021 Day 1] 分割数表 题解

· · 题解

题目传送门

本蒟蒻使用数学公式求解本题，所涉及的数学公式有些繁杂，但解释十分详尽，请各位大佬耐心读完谢谢。

题目简意：

有一个 n\times m 的数表，其中 a_{i,j}=(i-1)\times m+j。现在给出 t 次询问，每次询问给出 n 和 m，需要你求出如何分割数表成两部分 x 和 y，使得 \max{\{\sum x,\sum y}\} 最小，并输出切割方案。

分析：

暴力是肯定无法 AC，因为 1\le t\le 10^5，1\le n,m\le 10^9，2\le n\times m\le 10^9。这不仅使得 O(n) 遍历都会超时，且二维树状数组求前缀和也会 MLE，所以容易想到用数学求解公式，O(1) 算出答案。

首先我们要处理 a_{i,j}=(i-1)\times m+j 是什么意思，如果你尝试模拟过的话，就知道它相当于是从 a_{1,1}=1 开始然后顺序填充整个数表直到 a_{n,m}=n\times m，例如当 n=3，m=4 时，数表应该形如下图：

1 2 3 4
5 6 7 8
9 10 11 12

那么不难发现无论我们怎么分割这个数表，所得到的 \sum x+\sum y= \displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m a_{i,j}，而 \displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^m a_{ij} 为一定值，不妨将这个定值设为 N，且为了方便表示，将 \sum x 设为 fx，\sum y 设为 fy。

再来看 \max{\{fx,fy}\}，变形一下，\max{\{fx,N-fx}\}，如果我们将它写成以下形式：

\begin{dcases}fx &\text{}fx\ge fy \\N-fx &\text{} fx<fy\end{dcases}

此时进行分类讨论： 若 fx\ge fy，

若 fx< fy，

而等号在哪一边取等都是可以的，所以 \max{\{fx,fy}\}\ge\frac{N}{2}。那么我们只要找到一种分割方案使得 \max{\{fx,fy}\}=\frac{N}{2}，那么此方案一定是最优的。而只有当 fx=\frac{N}{2} 时，才可能取等，所以接下来只需要找到 fx 和 N 的表达式即可。

n}i=\frac{mn\cdot (mn+1)}{2}$，那么 $\frac{N}{2}=\frac{mn\cdot (mn+1)}{4}$。 先考虑横着分割数表假设确定的 $i$ 为 $k$，那么相当于在第 $k-1$ 行和第 $k$ 行将数表分开，因为 $fx$ 和 $fy$ 地位等价，不妨假设 $fx$ 为第一行到第 $k-1$ 行求和，也就是从 $1$ 加到 $[(k-1)-1]\cdot m+m=(k-1)\cdot m$，自然 $fx=\displaystyle\sum_{i=1}^{m\cdot(k-1)}i=\frac{m\cdot (k-1)\cdot [m(k-1)+1]}{2}$。 此时令 $\frac{m\cdot (k-1)\cdot [m(k-1)+1]}{2}=\frac{N}{2}=\frac{mn\cdot (mn+1)}{4}$， 可化简得 $2mk^2+2(1-m)k+2m-2mn^2-n=0$， 这便是关于 $k$ 的一个一元二次方程，如果我们能够得到 $k$ 的整数解并且 $1<k\le n$，那么最小值就是 $\frac{N}{2}$，否则我们找到 $\lceil k\rceil$ 和 $\lfloor k \rfloor$，并将它们分别带入 $fx$ 看 $\max{\{fx,N-fx}\}$ 谁更小，那么谁就是结果。容易证明 $k$、$\lceil k\rceil$、$\lfloor k \rfloor$一定有一个属于 $(1,n]$ 的。 然后考虑竖着分割数表，此时求解 $fx$ 是有一些难度的，根据题目所定义 $a_{i,j}=(i-1)\times m+j$，此时若仍假设确定的 $i$ 为 $k$，那么相当于在第 $k-1$ 列和第 $k$ 列将数表分开，所以 $fx=\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^{k-1}a_{i,j}=\displaystyle\sum_{i=1}^n\displaystyle\sum_{j=1}^{k-1}m(i-1)+j =\displaystyle\sum_{i=1}^n[m(k-1)(i-1)+\displaystyle\sum_{j=1}^{k-1}j] =m(k-1)\displaystyle\sum_{i=1}^n(i-1)+\displaystyle\sum_{i=1}^n\frac{(k-1)(k-1+1)}{2} =m(k-1)\displaystyle\sum_{i=1}^ni-m(k-1)\displaystyle\sum_{i=1}^n1+\frac{nk(k-1)}{2} =\frac{mn(n+1)(k-1)}{2}-nm(k-1)+\frac{nk(k-1)}{2}

此时令 \frac{mn(n+1)(k-1)}{2}-nm(k-1)+\frac{nk(k-1)}{2}=\frac{N}{2}=\frac{mn\cdot(mn+1)}{4}，

可化简得 2k^2+2(mn-m-1)k-2mn+m-m^2n=0。

这仍是关于 k 的一个一元二次方程，如果我们能够得到 k 的整数解并且 1<k\le m，那么最小值就是 \frac{N}{2}，否则我们找到 \lceil k\rceil 和 \lfloor k \rfloor，并将它们分别带入 fx 看 \max{\{fx,N-fx}\} 谁更小，那么谁就是结果。

至此我们的分析已经结束了，直接上代码！

代码实现

#include <bits/stdc++.h>
#define int long long//不开long long见祖宗
#define inf 9e18
using namespace std;
int t, n, m;
int ans1, ans2;//ans1表示是横着切还是竖着切，ans2表示切在什么位置
double bans, aa, bb, k;//bans表示当前最小的max

double work() {//竖着切
    double fa = (double)2;
    double fb = (double)2 * (m * n - m - 1);
    double fc = (double) -2 * m * n + m - m * m * n;
    double der = sqrt(fb * fb - 4 * fa * fc);
    double aa1 = (-fb + der) / (2 * fa);//容易证明小的根是负数，所以返回大的根

    return aa1;
}

double deal(int x) {//求当x=k时竖着切的fx
    double f1 = (m * n * (n + 1) * (x - 1)) / 2;
    double f2 = m * n * (x - 1);
    double f3 = (n * x * (x - 1)) / 2;
    double res = f1 - f2 + f3;
    double tot = (m * n * (m * n + 1)) / 2;
    return max(res, tot - res);
}

double work2() {//横着切
    double fa = (double)2 * m;
    double fb = (double)(2 - 4 * m);
    double fc = (double)(2 * m - 2 - m * n * n - n);
    double der = sqrt(fb * fb - 4 * fa * fc);
    double aa1 = (-fb + der) / (2 * fa);
    return aa1;
}

double deal2(int x) {//求当x=k时横着切的fx
    double res = (m * (x - 1) * (m * (x - 1) + 1)) / 2;
    double tot = (m * n * (m * n + 1)) / 2;
    return max(res, tot - res);
}

signed main() {
    scanf("%lld", &t);

    while (t--) {
        scanf("%lld%lld", &n, &m);
        ans1 = ans2 = 0;
        aa = bb = bans = inf;//初始化以防万一
        k = work();//先求根，这里要先求竖着切的，因为“如果有多解，请输出竖切的一种”

        if (k == floor(k)) {//k为整数
            ans1 = 0;
            ans2 = k;
            bans = deal(k);
        } else {
            int k1 = floor(k);//下取整
            int k2 = k1 + 1;//上取整
            ans1 = 0;

            if (k1 > 1 && k1 <= m)
                aa = deal(k1);

            if (k2 > 1 && k2 <= m)
                bb = deal(k2);
            ans2 = aa <= bb ? k1 : k2;
            bans = aa <= bb ? aa : bb;
        }

        k = work2();//求横着切的

        if (k == floor(k)) {
            int lin = deal2(k);

            if (lin < bans) {//只有小于竖着切的情况才更新
                ans1 = 1;
                ans2 = k;
                bans = lin;
            }
        } else {
            int k1 = floor(k);
            int k2 = k1 + 1;

            if (k1 > 1 && k1 <= n)
                aa = deal2(k1);

            if (k2 > 1 && k2 <= n)
                bb = deal2(k2);

            if (aa < bans) {
                ans1 = 1;
                ans2 = k1;
                bans = aa;
            }

            if (bb < bans) {
                ans1 = 1;
                ans2 = k2;
                bans = bb;
            }
        }

        if (ans1 == 0)//ans1为0就是竖着切
            printf("V ");
        else//否则横着切
            printf("H ");
        printf("%lld\n", ans2);
    }

    return 0;
}

感谢各位大佬耐着性子看到这里，如果觉得还不错的话点个赞再走吧。