2026 杭电暑期多校 6 ——1002-Dice Tower-骰子塔（小心，舞台最下面的那个面也会贡献）

题目大意

Dice Tower

时间限制: 2000 MS | 内存限制: 524288 KB

题目描述

联合演出结束后，Ave Mujica 的舞台机关还没有拆。睦留下了一批骰子道具，祥子想把它们堆成一座能从观众席各个方向看到的骰子塔；一旁的爱音则认真研究起怎样摆才能让露出的点数更多。

祥子在舞台平面上画出了一个 $n$ 行 $m$ 列的网格。第 $i$ 行第 $j$ 列的位置上堆着若干个完全相同的单位骰子。从正上方看，第 $i$ 行第 $j$ 列的骰子塔高度为 $h_{i,j}$，也就是说这个位置上堆了 $h_{i,j}$ 个骰子。

所有骰子都与网格对齐，且同一个格子里的骰子上下紧贴摆放；若试图把它们摆歪，会被祥子立刻制止。

每个骰子的 $6$ 个面分别有 $1, 2, 3, 4, 5, 6$ 个点，且相对两面的点数和为 $7$。睦提醒大家，骰子各个面的相对位置固定：初始时，上、下、前、后、左、右六个面的点数依次为 $1, 6, 2, 5, 3, 4$；之后只能通过旋转改变朝向，不能将骰子翻成镜像。

爱音可以任意旋转每个骰子，并且不同骰子的朝向可以不同。相邻两个骰子贴在一起的面不会露出。一个骰子对答案的贡献等于它所有露出面的点数之和。

请你帮爱音求出所有骰子的贡献之和最大可以是多少。

输入格式

第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含两个整数 $n,m$（$1 \le n,m \le 10^3$），表示网格的行数和列数。

• 接下来 $n$ 行，每行包含 $m$ 个整数，其中第 $i$ 行第 $j$ 个整数为 $h_{i,j}$（$0 \le h_{i,j} \le 10^9$），表示该位置上骰子塔的高度。

保证对于所有的测试数据，满足 $\sum n \times m \le 10^6$。

输出格式

对于每组测试数据，输出一行一个整数，表示该组测试数据中露出面的最大点数之和。

样例输入

Plaintext

2
2 2
1 2
3 4
3 4
0 2 0 1
3 1 4 0
0 2 2 5

样例输出

Plaintext

156
314

样例解释

样例中的两组测试数据分别对应原来的两座骰子塔。

在第一组数据中，骰子塔的普通外表面积为 $34$，但本题计算的是露出面上的点数之和。通过合理旋转每个骰子，可以使露出面的点数之和达到 $156$。

注意： 最底层的骰子的下表面（即与舞台平面接触的面）也计入露出的表面并产生点数贡献。

思路讲解

一种比较复杂的实现方式

// teamname: Gospel_rock
/**
 * Problem: Dice Tower
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1234&pid=1002
 * Created: 2026-08-06 14:03:22
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define SZ(a) ((long long)a.size())
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"
using namespace std;
using namespace __gnu_pbds;
using ordered_set = tree<int, null_type, less<>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128_t;
constexpr const ll INF = 1e18, MOD = 1e9 + 7;
constexpr const ld EPS = 1e-7;
// #define int long long
#define all(x) x.begin(), x.end()
#define debug1d(a)                            \
    cerr << #a << " = [";                     \
    for (int i = 0; i < (int)(a).size(); i++) \
        cerr << (i ? ", " : "") << (a)[i];    \
    cerr << "]\n";
#define debug2d(a)                                   \
    cerr << #a << " = [\n";                          \
    for (int i = 0; i < (int)(a).size(); i++)        \
    {                                                \
        cerr << "  [";                               \
        for (int j = 0; j < (int)(a[i]).size(); j++) \
            cerr << (j ? ", " : "") << a[i][j];      \
        cerr << "]\n";                               \
    }                                                \
    cerr << "]\n";
#define debug(x) cerr << "[" << #x << "] = " << (x) << "\n"
static int last_res;

ostream &operator<<(ostream &os, __int128 x) {
	if (x < 0) os << '-', x = -x;
	if (x > 9) os << x / 10;
	return os << (char)('0' + x % 10);
}

istream &operator>>(istream &is, __int128 &x) {
	string s;
	if (!(is >> s)) return is;
	x = 0;
	size_t i = 0;
	bool neg = false;
	if (s[0] == '-') {
		neg = true;
		i = 1;
	} else if (s[0] == '+') { i = 1; }
	for (; i < s.size(); ++i) x = x * 10 + (s[i] - '0');
	if (neg) x = -x;
	return is;
}

/* -> (Right, Down, Left, Up)
  |  |
   <-
*/
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

struct Block {
	ll height;
	ll id;

	bool operator<(const Block &o) const {
		return height < o.height;
	}
};

i128 cnt2[2];
i128 cnt3[2];

void solve() {
	int n, m;
	cin >> n >> m;
	vector<vector<int> > grid(n + 2, vector<int>(m + 2));
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> grid[i][j];
		}
	}
	ll cnt1[7] = {0};
	ll cnt4 = 0;
	cnt2[0] = 0;
	cnt2[1] = 0;
	cnt3[0] = 0;
	cnt3[1] = 0;
#ifdef LOCAL
	cerr << "grid:\n";
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cerr << grid[i][j] << " ";
		}
		cerr << "\n";
	}
	cerr << "\n";
#endif
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			ll h = grid[i][j];
			vector<Block> p;
			p.push_back({0, 0});
			set<ll> st;
			for (int k = 1; k <= 4; k++) {
				int nx = i + dx[k - 1];
				int ny = j + dy[k - 1];
				if (nx <= 0 || ny <= 0 || nx > n || ny > m) {
					st.insert(k);
					continue;
				}
				p.push_back({grid[nx][ny], k});
			}
			sort(all(p));

			ll cover = 0;
			while (!p.empty() && p.back().height >= h) {
				// st.erase(p.back().id);
				p.pop_back();
				cover++;
			}
			int tot = p.size();
			p.push_back({h - 1, 0});
#ifdef LOCAL
			debug(cover);
			for (auto x: p) {
				cerr << "高度：" << x.height << " id：" << x.id << "\n";
			}
#endif
			for (int k = 1; k < p.size(); k++) {
				// 被遮蔽
				int delta = tot - k + cover;
				if (4 - delta != 2) {
					st.insert(p[k].id);
					cnt1[4 - delta] += p[k].height - p[k - 1].height;
#ifdef LOCAL
					ll d = p[k].height - p[k - 1].height;
					cerr << "i:" << i << " j:" << j << " type:" << 4 - delta << " d:" << d << "\n";
#endif
				} else {
#ifdef LOCAL
					assert(SZ(st)==2);
#endif
					if (SZ(st) >= 2) {
						// #ifdef LOCAL
						// 							debug(cnt2[0]);
						// 							debug(cnt2[1]);
						// #endif
						if ((*st.begin() == 1 && *st.rbegin() == 3) || (*st.begin() == 2 && *st.rbegin() == 4)) {
							cnt2[0] += p[k].height - p[k - 1].height;
#ifdef LOCAL
							ll d = p[k].height - p[k - 1].height;
							cerr << "i:" << i << " j:" << j << " type:" << 4 - delta << " 相对  d:" << d << "\n";
#endif
						} else {
							cnt2[1] += p[k].height - p[k - 1].height;
#ifdef LOCAL
							ll d = p[k].height - p[k - 1].height;
							cerr << "i:" << i << " j:" << j << " type:" << 4 - delta << " 相邻  d:" << d << "\n";
#endif
						}
					}
					st.insert(p[k].id);
				}
			}
			if (5 - cover == 2) {
				cnt2[1]++;
#ifdef LOCAL
				cerr << "i:" << i << " j:" << j << " type:" << 5 - cover << " 相邻顶部  d:" << 1 << "\n";
#endif
			} else if (5 - cover == 4) {
				cnt4++;
#ifdef LOCAL
				cerr << "i:" << i << " j:" << j << " type:" << 5 - cover << " 特殊顶部 d:" << 1 << "\n";
#endif
			} else if (5 - cover == 3) {
				st.erase(0);
				assert(SZ(st)==2);
				if ((*st.begin() == 1 && *st.rbegin() == 3) || (*st.begin() == 2 && *st.rbegin() == 4)) {
					cnt3[0]++;
#ifdef LOCAL
					cerr << "i:" << i << " j:" << j << " type:" << 5 - cover << " 相对 3 顶部 d:" << 1 << "\n";
#endif
				} else {
					cnt3[1]++;
#ifdef LOCAL
					cerr << "i:" << i << " j:" << j << " type:" << 5 - cover << " 相邻 3 顶部 d:" << 1 << "\n";
#endif
				}
			} else {
				cnt1[5 - cover]++;
#ifdef LOCAL
				cerr << "i:" << i << " j:" << j << " type:" << 5 - cover << " 顶部 d:" << 1 << "\n";
#endif
			}
#ifdef LOCAL
			cerr << "\n";
#endif
		}
	}
	i128 ans = 0;
	i128 cost[6] = {0, 6, 7, 13, 14, 20};
	for (int i = 1; i <= 5; i++) {
		if (i != 2) {
#ifdef LOCAL
			debug(i);
			debug(cnt1[i]);
#endif
			ans += cnt1[i] * cost[i];
		}
	}
#ifdef LOCAL
	cend;
	debug(cnt2[0]);
	debug(cnt2[1]);
	debug(cnt4);
	cEnd;
#endif
	ans += cnt2[0] * 7;
	ans += cnt2[1] * 11;
	ans += cnt4 * (7 + 11);
	ans += cnt3[0] * 13;
	ans += cnt3[1] * (6 + 5 + 4);
	cout << ans << "\n";
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}

那么这种实现方式比较复杂，是因为它没有实现轴的单独判别。

它是用面数进行判别的，那么实际上我们可以把单个块的逻辑给抽离出来。我们没有必要在遍历的时候，在同一个地方书写计算的逻辑。

这个函数的计数的计数原理就是我们知道一个相对面组，它的和一定是7，所以说如果凑齐了一个相对面，那么它的答案一定是贡献7，我们称一个相对面组为一个轴，轴中如果只有一个面，那么就是贡献6，5，4，我们优先给他分配比较高的面。

这个就是 axis1，acc1，和 origin_cost 的原理。

ll acc1 = accumulate(all(axis1), 0ll);
	ll res = ... + origin_cost[acc1];

完整的函数如下：

i128 origin_cost[] = {0, 6, 11, 15};
// X, Y是坐标，H是该点高度，ver是该点暴露在外的垂直面数量（夹在中间就是0，头尾就是1，2 只有块高度为一的时候）
i128 cal_single(ll x, ll y, ll h, ll ver) {
	if (h == 0) return 0;
	vector<ll> axis1(3), axis2(3);
	if (ver == 1) {
		axis1[2]++;
	} else if (ver == 2) {
		axis2[2]++;
	}
	for (int k = 0; k < 4; ++k) {
		auto [tox,toy] = make_tuple(x + dx[k], y + dy[k]);
		ll toh;
		// 小心这里，不要漏掉，也不要直接跳过
		if (tox < 1 || toy < 1 || tox > N || toy > M) {
			toh = 0;
		} else {
			toh = grid[tox][toy];
		}
		if (toh < h) {
			axis1[k & 1]++;
			if (axis1[k & 1] == 2) {
				axis1[k & 1] = 0;
				axis2[k & 1]++;
			}
		}
	}
	ll acc2 = accumulate(all(axis2), 0ll);
	ll acc1 = accumulate(all(axis1), 0ll);
	ll res = acc2 * 7 + origin_cost[acc1];
	return res;
}

i128 ans = 0;
for (int x = 1; x <= N; ++x) {
	for (int y = 1; y <= M; ++y) {
		ll h = grid[x][y];
		if (h == 0) {
			continue;
		}
		if (h == 1) {
			ans += cal_single(x, y, h, 2);
			continue;
		}
		ans += cal_single(x, y, 1, 1);
		ans += cal_single(x, y, h, 1);
		vector<ll> hls;
		// 注意一下哨兵值的设置
		// 如果设定为1的话，那么将无法计入1
		hls.push_back(0);
		for (int k = 0; k < 4; ++k) {
			auto [tox,toy] = make_tuple(x + dx[k], y + dy[k]);
			if (tox < 1 || toy < 1 || tox > N || toy > M) continue;
			if (grid[tox][toy] == 0) {
				continue;
			}
			if (grid[tox][toy] <= h) {
				hls.push_back(grid[tox][toy]);
			}
		}
		hls.push_back(h);
		// 不要忘记对HLS进行排序
		sort(all(hls));

		for (int k = 1; k < SZ(hls); ++k) {
			// 采用直接减法方法，所以说要把1给记进去的话，那么哨兵值必须得设为0。
			ll num = hls[k] - hls[k - 1];
			ans += num * cal_single(x, y, hls[k], 0);
		}
		ans -= cal_single(x, y, 1, 0);
		ans -= cal_single(x, y, h, 0);
	}
}
cout << ans << "\n";

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1234&rid=11474

源代码

// teamname: Gospel_rock
/**
 * Problem: Dice Tower
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1234&pid=1002
 * Created: 2026-08-06 16:21:42
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
#define debug(x) cerr << "[" << #x << "]" << ": " << x << "\n"
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)3e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
// 不用 M_PI: 后者是 POSIX 扩展, glibc <cmath> 严格模式会 undef
const long double PI = acosl(-1.0);

ll lT, testcase;

/*
 *
 */

ll N, M;

ostream &operator<<(ostream &os, __int128 x) {
	if (x < 0) os << '-', x = -x;
	if (x > 9) os << x / 10;
	return os << (char)('0' + x % 10);
}

istream &operator>>(istream &is, __int128 &x) {
	string s;
	if (!(is >> s)) return is;
	x = 0;
	size_t i = 0;
	bool neg = false;
	if (s[0] == '-') {
		neg = true;
		i = 1;
	} else if (s[0] == '+') { i = 1; }
	for (; i < s.size(); ++i) x = x * 10 + (s[i] - '0');
	if (neg) x = -x;
	return is;
}

struct GRID {
	ll a[MAXN] = {};

	ll *operator[](int i) {
		return a + i * (M + 2);
	}
} grid;

/* -> (Right, Down, Left, Up)
  |  |
   <-
*/
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
i128 origin_cost[] = {0, 6, 11, 15};

i128 cal_single(ll x, ll y, ll h, ll ver) {
	if (h == 0) return 0;
	vector<ll> axis1(3), axis2(3);
	if (ver == 1) {
		axis1[2]++;
	} else if (ver == 2) {
		axis2[2]++;
	}
	for (int k = 0; k < 4; ++k) {
		auto [tox,toy] = make_tuple(x + dx[k], y + dy[k]);
		ll toh;
		if (tox < 1 || toy < 1 || tox > N || toy > M) {
			toh = 0;
		} else {
			toh = grid[tox][toy];
		}
		if (toh < h) {
			axis1[k & 1]++;
			if (axis1[k & 1] == 2) {
				axis1[k & 1] = 0;
				axis2[k & 1]++;
			}
		}
	}
	ll acc2 = accumulate(all(axis2), 0ll);
	ll acc1 = accumulate(all(axis1), 0ll);
	ll res = acc2 * 7 + origin_cost[acc1];
	return res;
}

void Solve() {
	cin >> N >> M;
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= M; ++j) {
			cin >> grid[i][j];
		}
	}
	// #ifdef LOCAL
	// 	for (int i = 1; i <= N; ++i) {
	// 		for (int j = 1; j <= M; ++j) {
	// 			cerr << grid[i][j] << " ";
	// 		}
	// 		cerr << "\n";
	// 	}
	// #endif
	i128 ans = 0;
	for (int x = 1; x <= N; ++x) {
		for (int y = 1; y <= M; ++y) {
			ll h = grid[x][y];
			if (h == 0) {
				continue;
			}
#ifdef LOCAL
			cerr << "x:" << x << " y:" << y << "\n";
#endif
			if (h == 1) {
				ans += cal_single(x, y, h, 2);
#ifdef LOCAL
				debug(cal_single(x, y, h, 2));
				cEnd;
#endif

				continue;
			}
			ans += cal_single(x, y, 1, 1);
			ans += cal_single(x, y, h, 1);
			vector<ll> hls;
			hls.push_back(0);
			for (int k = 0; k < 4; ++k) {
				auto [tox,toy] = make_tuple(x + dx[k], y + dy[k]);
				if (tox < 1 || toy < 1 || tox > N || toy > M) continue;
				if (grid[tox][toy] == 0) {
					continue;
				}
				if (grid[tox][toy] <= h) {
					hls.push_back(grid[tox][toy]);
				}
			}
			hls.push_back(h);
			sort(all(hls));
#ifdef LOCAL
			for (auto p: hls) {
				cerr << p << " ";
			}
			cerr << "\n";
#endif

			for (int k = 1; k < SZ(hls); ++k) {
				ll num = hls[k] - hls[k - 1];
				ans += num * cal_single(x, y, hls[k], 0);
#ifdef LOCAL
				cerr << "num:" << num << " cal:" << cal_single(x, y, hls[k], 0) << " h:" << hls[k] << "\n";
#endif
			}
			ans -= cal_single(x, y, 1, 0);
			ans -= cal_single(x, y, h, 0);
#ifdef LOCAL
			cEnd;
#endif
		}
	}
	cout << ans << "\n";
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	cin >> lT;
	for (testcase = 1; testcase <= lT; ++testcase)
		Solve();
	return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1234&rid=11474

*/

心路历程（WA，TLE，MLE……）