题解：P8164 [JOI 2022 Final] 沙堡 2 (Sandcastle 2)

惊为天人的做法，来自 _YangZj。

如何判断一个矩形是否存在如题所述的哈密顿路径？我们首先站在最大值的位置上，每次走向相邻的位置中，比自己小的最大者，若相邻的位置都大于当前所在的位置则停止，检查是否遍历整个矩形即可。

这启示我们把每个位置向它相邻的位置中比自己小的最大者连边，我们会得到一个森林，我们需要检查它是否是一条链。

设

a_i

为点

i

在原矩阵中的值，

f_i

为

i

的父亲在原矩阵中的值，若

i

为根则

f_i=0

。点分成两类：

对于一个四周都小于它的位置（可能成为起点的位置），我们对它赋权 $X-f_i$ ，其中 $X$ 是一个足够大的值；
否则对它赋权 $a_i-f_i$ 。

首先所有点的点权

>0

，因为我们的连边保证

a_i>f_i

，且

X

足够大。并且显然森林中至少有一个 1 类点，该点到根的路径上的点权之和为

X

。

所以这个森林为一条链当且仅当这样赋权后所有点权之和为

X

。

所以我们枚举矩形的上下边界，对于每个右端点可以

O(1)

统计有多少左端点合法。

#include<unordered_map>
#include<iostream>

const int N = 233, M = 5e4, X = 1e9;
int n, m, a[N][M];
long long s, sm, l[N][M], c[N][M], r[N][M];
std::unordered_map<long long, int>ct;
int inline f(int x, std::initializer_list<int>il) {
	int s = X, mx = 0;
	for (int y : il) y < x ? mx = std::max(mx, y) : s = x;
	return s - mx;
}
int main() {
	if (int i, j; std::cin >> n >> m, n < m) for (i=0; i<n; i++)
		for (j=0; j<m; j++) std::cin >> a[i][j];
	else for (std::swap(n, m), i=0; i<m; i++)
		for (j=0; j<n; j++) std::cin >> a[j][i];
	for (int i=1, j; i<n-1; i++) {
		for (j=0; j<m-1; j++) l[i][j] = l[i-1][j] + f(a[i][j], {a[i-1][j], a[i][j+1], a[i+1][j]});
		for (j=1; j<m; j++) r[i][j] = r[i-1][j] + f(a[i][j], {a[i-1][j], a[i][j-1], a[i+1][j]});
		for (j=1; j<m-1; j++) c[i][j] = c[i-1][j] + f(a[i][j], {a[i-1][j], a[i][j-1], a[i+1][j], a[i][j+1]});
	}
	for (int i=0, j, k; i<n; i++) for (j=i+1; j<n; j++, ct.clear()) for (k=s=1; k<m; k++) {
		ct[l[i][k-1] - l[j-1][k-1] - f(a[i][k-1], {a[i+1][k-1], a[i][k]}) - f(a[j][k-1], {a[j-1][k-1], a[j][k]}) + s]++;
		auto it = ct.find(s + f(a[i][k], {a[i+1][k], a[i][k-1]}) + f(a[j][k], {a[j-1][k], a[j][k-1]}) + r[j-1][k] - r[i][k] - X);
		if (it != ct.end()) sm += it->second;
		s += c[j-1][k] - c[i][k] + f(a[i][k], {a[i+1][k], a[i][k-1], a[i][k+1]}) + f(a[j][k], {a[j-1][k], a[j][k-1], a[j][k+1]});
	}
	for (int i=0, j, x, y; i<n; i++) for (j=1, x=y=0; j<m; sm+=x+y, j++) if (a[i][j] < a[i][j-1]) x++, y = 0; else y++, x = 0;
	for (int j=0, i, x, y; j<m; j++) for (i=1, x=y=0; i<n; sm+=x+y, i++) if (a[i][j] < a[i-1][j]) x++, y = 0; else y++, x = 0;
	std::cout << sm + n * m;
}

点评：这我哪会啊

题解：P8164 [JOI 2022 Final] 沙堡 2 (Sandcastle 2)

文章操作

相关推荐

评论

题解：P8164 [JOI 2022 Final] 沙堡 2 (Sandcastle 2)