洛谷 P2180 题解

题目链接：https://www.luogu.com.cn/problem/P2180

作为我A掉的第777题，我自然要写一篇题解庆祝一下的。~~（我是不会告诉你我是因为再不写题解社区贡献分就要掉了才来写题解的）~~

有一篇题解是有说明的但是Markdown炸了且没有代码，另一篇有代码但是没有详细说明，我就来发这篇题解，来详（cu）细（lüe）地解释一下吧。

首先，要明确只有一行不为满的时候答案才可能为最大值，像这样：

.......
...ooo.
.ooooo.
.ooooo.
.ooooo.
.......

显然要比

.......
..oooo.
..oooo.
.ooooo.
.ooooo.
.......

更优。
所以，只需要枚举一下放的行数就可以了。
那么，如何计算一个 $a\times b$ 的网格中，可以组成多少个矩形呢？显然，一行有 $a\times(a-1)/2$ 种选法，一列中有 $b\times(b-1)/2$ 种，所以有 $a\times b\times(a-1)\times(b-1)/4$ 种方案。假设剩余的一行有 $c$ 列，那么还要加上 $a\times c\times(c-1)/2$ ，这样，正解就出来了，答案 $ans=\max\limits _{i=1}^{\min(n,k)}(i\times \lfloor k/i\rfloor \times(i-1)\times(\lfloor k/i\rfloor-1)/4+i\times (k\bmod i)\times (k\bmod i-1)/2)$ 。
最后，有一个非常坑的地方，就是当 $n>m$ 的时， $n$ 和 $m$ 要交换，否则只有 $90$ 分。

#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
FILE *fin, *fout;
inline int read(ll &x) {
	char c = 0; int f = x = 0;
	while (c < 48 || c > 57) {
		if (c == -1) return 0;
		if (c == '-') f = 1; c = fgetc(fin);
	}
	while (c > 47 && c < 58) x = (x << 3) + (x << 1) + (c & 15), c = fgetc(fin);
	if (f) x = -x; return 1;
}
template<class T, class... Args> inline int read(T &x, Args&... args) {
	return read(x) + read(args...);
}
inline int write(ll x) {
	if (x < 0) return fputc(45, fout), write(-x);
	if (x > 9) write(x / 10);
	return fputc((x % 10) | 48, fout), 1;
}
ll n, m, k, ans;
int main() {
	#ifdef ONLINE_JUDGE
	fin = stdin;
	fout = stdout;
	#else
	fin = fopen("P2180.in", "rb");
	fout = fopen("P2180.out", "wb");
	#endif
	read(n, m, k); if (n > m) swap(n, m);//就是这个地方，非常坑！
	for (ll i = 1; i <= min(n, k); ++i) {
		ll x = k / i, y = k % i;
		if (!y && x > m) continue;
		if (y && x >= m) continue;
		ans = max(ans, i * x * (i - 1) * (x - 1) / 4 + x * y * (y - 1) / 2);
	}
	write(ans);
	return 0;
}

Gridea

洛谷 P2180 题解

洛谷 P6248 题解