题解：B3760 [信息与未来 2021] 掷骰子

· · 题解

前言

2025.04.07 晚。被 cz 拷打让我看一眼这个题讨论区。经过我的手算和代码验证，我們的數據並非確有問題。考虑到这个题可能目前网上没有任何一份正确题解，遂写此文。

强烈谴责套数据特判过题来写错误题解的行为。

做法

这个数据范围很小啊，我们可以枚举这个骰子的所有面，然后判断要求的 n 个限制对应的 3 个面是否出现。

考虑怎么判断三个面是否出现。

我们小学就学过立方体的展开。让我们把他展开出来看一看。

如图是 1-4-1 类型的展开。注意题目给出的 (x,y,z) 是有顺序的。x 在最上方，y,z 从左向右。

我们把每个点作为最上方的点，然后把这个立方体想象出来（实在不行咱拿张纸折一下），把某一面朝上时，中间四面的顺序写出来。那么我们判断是否存在一个 (x,y,z) 的图，就是判断 x 作为顶端的时候，是否 y 的下一个面是 z。例如按本图标号，则 1 面朝上时，依次是 2,3,4,5。说明 (1,2,3),(1,3,4),(1,4,5),(1,5,2) 都是正确的视角。

所以我们在搜出这个立方体每一面的数之后，对于每一条限制我们都看一下是否存在这样的一张 (x,y,z) 的图。如果没有那么这个方案就是不合法的。

另外附一份数据以及对应的唯一解，这一份数据好像卡死了很多人，但事实上数据并没有错误：

5
1 6 3
2 3 6
3 6 1
6 3 2
1 3 1

代码

https://www.luogu.com.cn/record/212499277

#include <bits/stdc++.h>
using namespace std;
template <typename T>
void chkmx(T &x, T y) { x = max(x, y); }
template <typename T>
void chkmn(T &x, T y) { x = min(x, y); }
const int inf = 1e9;
int mn = inf, mx = -inf;
int mp[7];
int n;
struct node
{
    int x, y, z;
} a[50];
int e[7][4] = {
    {0, 0, 0, 0},
    {2, 3, 4, 5},
    {1, 5, 6, 3},
    {1, 2, 6, 4},
    {1, 3, 6, 5},
    {1, 4, 6, 2},
    {5, 4, 3, 2}};
void dfs(int dep)
{
    if (dep == 7)
    {
        int ans = accumulate(mp + 1, mp + 7, 0);
        for (int i = 1; i <= n; i++)
        {
            auto [x, y, z] = a[i];
            bool ok = 0;
            for (int tx = 1; tx <= 6; tx++)
            {
                for (int j = 0; j < 4; j++)
                {
                    int ty = e[tx][j];
                    int tz = e[tx][(j + 1) % 4];
                    if (mp[tx] == x && mp[ty] == y && mp[tz] == z)
                    {
                        ok = 1;
                        break;
                    }
                }
                if (ok)
                    break;
            }
            if (!ok)
                return;
        }
        chkmn(mn, ans);
        chkmx(mx, ans);
        return;
    }
    for (int i = 1; i <= 6; i++)
    {
        mp[dep] = i;
        dfs(dep + 1);
    }
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].x >> a[i].y >> a[i].z;
    dfs(1);
    cout << mn << ' ' << mx << '\n';
    return 0;
}