砝码比较问题

问题描述

有 n 个砝码，根据材质不同，质量只有 1g, 2g, 3g 三种。

现在砝码上的质量标签都遗失了，由于只有材质不同，从外表难以分辨。但所幸还有一个天平，可以用这个天平秤量砝码之间的重量关系。

某些砝码之间的重量关系已经称出来了，但其它的还不知道。

现在已经选了两个放在了天平左边，想再选另外两个放在右边，求有多少种选法使得由已知信息能确定左边更重/相等/右边更重。

输入格式

第一行一个数 n。

接下来 n 行，每行 n 个字符，包含 +/-/=/?，第 i 行第 j 个字符 s_{i,j} 为 + 表示第 i 个比第 j 个大，- 表示更小，= 表示相等，? 表示不知道。

保证 s_{i,i} 是 ?，且如果 s_{i,j} 是 +/-/=/? 有 s_{j,i} 是 -/+/=/?。

接下来两个数 a, b 表示放在左边的编号。

保证存在至少一种质量序列满足所有秤量结果。

输出格式

三行，每行一个数，按顺序分别有多少种选法使得由已知信息能确定左边更重/相等/右边更重。

样例

输入

6
?+????
-?+???
?-????
????+?
???-?+
????-?
2
5

输出

1
4
1

解释

可以发现已知信息唯一确定了重量序列为 (3,2,1,3,2,1)。

数据范围与提示

对于100%的数据，n ≤ 50。

==============================================================================================================

解题思路

这个问题是一个典型的逻辑推理和组合优化问题。给定一组砝码和它们之间的某些已知重量关系，目标是找出可以放在天平右边的砝码组合，使得我们可以确定天平左边和右边的重量关系（左边更重、相等或右边更重）。下面是对代码思路的解释：

输入与砝码关系的解析:

程序首先读取砝码的数量 $n$。
接着，程序读取一个 $n \times n$ 的矩阵，该矩阵描述了砝码之间的已知关系（'+' 表示更重，'-' 表示更轻，'=' 表示等重，'?' 表示关系未知）。
然后，程序读取两个编号 $a$ 和 $b$，这些是已经放在天平左边的砝码。

初始化:

并查集初始化：并查集用于追踪哪些砝码已知具有相同的重量（由'='关系表示）。
图的构建：基于砝码之间的重量关系（由'+'关系表示），构建一个有向图。

遍历与检查:

对于除了已经放在天平左边的砝码之外的所有砝码，程序尝试将它们作为一对放在天平的右边。
对于每一对可能的砝码，程序尝试所有可能的重量分配（1g, 2g, 3g），检查哪些分配是符合已知重量关系的。
对于每个有效的重量分配，程序检查天平的左边和右边的总重量，并更新一个名为 ok 的数组，该数组追踪三种可能的结果（左边更重、两边相等、右边更重）是否可能。

结果的确定与输出:

如果对于一个特定的砝码组合，只有一种可能的结果（即 ok 数组中只有一个元素是 1），则更新 ans 数组。
ans 数组累积了每种可能情况（左边更重、两边相等、右边更重）的总数。
程序最后输出 ans 数组。

在这个问题中，重要的是理解如何利用已知的信息（砝码之间的关系和它们可能的重量）来排除不可能的情况，并找到那些可以确定天平哪边更重的砝码组合。代码通过尝试所有可能的组合和重量分配，并检查它们是否与已知的重量关系一致，来实现这一点。最终，程序计算出每种可能结果的数量，并将这些结果输出。

==============================================================================================================

以下是C++代码：

#include<bits/stdc++.h>
using namespace std;

// 定义常量和全局变量
int n;
int fa[55]; // 用于并查集的数组
char s[55][55]; // 存储砝码之间关系的二维数组
vector<int> to[55]; // 邻接表表示的图
int ok[3], ans[3]; // 存储结果的数组
int w[55]; // 存储砝码重量的数组
int ind[55], oud[55]; // 存储图的入度和出度

// 并查集查找函数
int find(int x) {
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}

// 比较函数，确定两个砝码的重量关系
int cmp(int x, int y) {
    return x > y ? 0 : x == y ? 1 : 2;
}

// 检查当前的重量分配是否符合所有已知的重量关系
bool check() {
    // 遍历所有砝码
    for (int i = 1; i <= n; ++i) if (w[i]) {
        // 如果当前砝码所在集合的重量未知，则设置为当前砝码的重量
        if (!w[find(i)]) w[find(i)] = w[i];
        // 如果当前砝码所在集合的重量已知，但与当前砝码的重量不同，则返回false
        else if (w[find(i)] != w[i]) return 0;
    }
    // 设置独立砝码的默认重量
    for (int i = 1; i <= n; ++i) if (find(i) == i && !w[i] && !ind[i]) w[i] = 1;
    for (int i = 1; i <= n; ++i) if (find(i) == i && !w[i] && !oud[i]) w[i] = 3;
    for (int i = 1; i <= n; ++i) if (find(i) == i && !w[i]) w[i] = 2;
    // 检查所有已知的重量关系是否都满足
    for (int i = 1; i <= n; ++i) for (auto j : to[i]) if (w[j] <= w[i]) return 0;
    return 1;
}

int main() {
    // 如果定义了QAQAutoMaton，从文件读取输入和输出
#ifdef QAQAutoMaton
    freopen("B.in", "r", stdin);
    freopen("B.out", "w", stdout);
#endif
    // 读取砝码数量
    scanf("%d", &n);
    // 读取砝码之间的关系
    for (int i = 1; i <= n; ++i) scanf("%s", s[i] + 1);
    // 初始化并查集
    for (int i = 1; i <= n; ++i) fa[i] = i;
    // 根据等重关系更新并查集
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (s[i][j] == '=') fa[find(i)] = find(j);
    // 根据重量关系构建图
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if (s[i][j] == '+') {
        to[find(j)].emplace_back(find(i));
        ++ind[find(i)];
        ++oud[find(j)];
    }
    // 读取放在天平左边的两个砝码
    int x, y;
    scanf("%d%d", &x, &y);
    // 遍历所有砝码组合
    for (int i = 1; i <= n; ++i) if (i != x && i != y)
        for (int j = i + 1; j <= n; ++j) if (j != x && j != y) {
            // 重置ok数组
            ok[0] = ok[1] = ok[2] = 0;
            // 尝试所有可能的重量分配
            for (int a1 = 1; a1 <= 3; ++a1) for (int a2 = 1; a2 <= 3; ++a2)
                for (int a3 = 1; a3 <= 3; ++a3) for (int a4 = 1; a4 <= 3; ++a4) {
                    // 重置w数组
                    for (int k = 1; k <= n; ++k) w[k] = 0;
                    // 设置当前组合的重量
                    w[x] = a1; w[y] = a2; w[i] = a3; w[j] = a4;
                    // 如果当前的重量分配是可能的，更新ok数组
                    if (check()) {
                        ok[cmp(a1 + a2, a3 + a4)] = 1;
                    }
                }
            // 如果只有一种可能的结果，更新ans数组
            if (ok[0] + ok[1] + ok[2] == 1) {
                for (int j = 0; j <= 2; ++j) ans[j] += ok[j];
            }
        }
    // 输出结果
    for (int i = 0; i <= 2; ++i) printf("%d\n", ans[i]);
    return 0;
}

这段代码使用了C++标准库，并定义了一个 find 函数来查找砝码的根，一个 check 函数来检查砝码的重量，以及一个主函数来处理输入和计算可能的情况。

==============================================================================================================