自动搬运

查看原文

来自洛谷，原作者为

	bianshiyang 乌云过后仍会是漫天星辰

搬运于2025-08-24 22:51:37，当前版本为作者最后更新于2023-10-28 21:38:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目传送门

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

题目简意：

有一个 $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$ 时，数表应该形如下图：

那么不难发现无论我们怎么分割这个数表，所得到的 $\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\ge N-fy$
• 即 $fx\ge\frac{N}{2}$
• 故此时 $\max{\{fx,fy}\}=fx\ge\frac{N}{2}$

若 $fx< fy$，

• 则有 $fx< N-fy$
• 即 $fx<\frac{N}{2}$
• 故此时 $\max{\{fx,fy}\}=N-fx>\frac{N}{2}$

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

$N$ 的表达式很容易求，$N=\displaystyle\sum_{i=1}^{m 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;
}

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