2026 杭电暑期多校 6 ——1002-Dice Tower-骰子塔(小心,舞台最下面的那个面也会贡献) · znzryb
## 题目大意
# 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$。
**注意:** **最底层的骰子的下表面(即与舞台平面接触的面)也计入露出的表面并产生点数贡献**。
## 思路讲解
::: 一种比较复杂的实现方式
```cpp
// 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 的原理。
```cpp
ll acc1 = accumulate(all(axis1), 0ll);
ll res = ... + origin_cost[acc1];
```
完整的函数如下:
```cpp
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;
}
```
```cpp
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](https://acm.hdu.edu.cn/contest/view-code?cid=1234&rid=11474)
::: 源代码
```cpp
// 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……)