P2474 题解

· · 题解

前言

题目传送门！

更好的阅读体验？

差分约束。

update：修改了 \LaTeX，这下应该正常了。

思路

预处理

维护两个数组 mn_{i, j} 与 mx_{i, j}，表示砝码 i 与砝码 j 重量差值的最小最大。

我们分类讨论：

差分约束

统计完基本信息后，就可以差分约束了。

由于数据范围很小（n \le 50），并且统计答案时需要全局统计，所以用 Floyd 就可以了。

转移：（1 \le k \le n）

mn_{i, j} = \max\{mn_{i, k} + mn_{k, j}\}\end{cases}

反向取上下界，应该很容易理解吧。

统计答案

对于所有 i \ne A 且 j \ne B 且 i \ne j 的两个砝码 i, j，统计答案。

同样是分类讨论：

  1. 如果 mn_{A, i} > mx_{j, B} 或者 mn_{A, j} > mx_{i, B}，说明左边有可能重。

  2. 如果 mn_{A, i} = mx_{A, i} = mn_{j, B} = mx_{j, B}，说明有可能相等； 同理，如果 mn_{B, i} = mx_{B, i} = mn_{j, A} = mx_{j, A}，也有可能相等；

  3. 与左边重的情况相反，如果 mn_{A, i} < mx_{j, B} 或者 mn_{A, j} < mx_{i, B}，说明右边有可能重。

统计好后输出即可。这道题就完美的做完啦！

完整代码

略微压行，凑合着看看吧，应该很容易看懂。

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 55;
int n, A, B;
int maxd[N][N], mind[N][N]; //maxd[i][j] 或 mind[i][j] 表示：砝码 i 与砝码 j 重量差值 的最值。 
void Input()
{
    scanf("%d%d%d", &n, &A, &B);
    for  (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            char x;
            cin >> x;
            if (i == j || x == '=') maxd[i][j] = mind[i][j] = 0; //别忘了：同一块砝码，最值都是 0。 
            else if (x == '+') maxd[i][j] = 2, mind[i][j] = 1; //差值最大：a[i]=3，a[j]=1。最小：a[i]=2，a[j]=1。 
            else if (x == '-') maxd[i][j] = -1, mind[i][j] = -2; //恰好与上面反过来。
            else if (x == '?') maxd[i][j] = 2, mind[i][j] = -2; //差值最大：a[i]=3，a[j]=1。最小：a[i]=1，a[j]=3。
        }
}
void Floyd() //差分约束
{
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                maxd[i][j] = min(maxd[i][j], maxd[i][k] + maxd[k][j]),
                mind[i][j] = max(mind[i][j], mind[i][k] + mind[k][j]);
}
void Output()
{
    int lcnt = 0, ecnt = 0, rcnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j < i; j++)
        {
            //要保证 i 与 j 均不是给定砝码。 
            if (i == A || i == B) break;
            if (j == A || j == B) continue;
            if (mind[A][i] > maxd[j][B] || mind[A][j] > maxd[i][B]) lcnt++;

            if (mind[A][i] == maxd[A][i] && mind[A][i] == mind[j][B] && mind[j][B] == maxd[j][B]) ecnt++;
            else if (mind[B][i] == maxd[B][i] && mind[B][i] == mind[j][A] && mind[j][A] == maxd[j][A]) ecnt++;

            if (maxd[A][i] < mind[j][B] || maxd[A][j] < mind[i][B]) rcnt++;
        }
    printf("%d %d %d", lcnt, ecnt, rcnt);
}
int main()
{
    //程序三段式，十分清晰美观。 
    Input();
    Floyd();
    Output();
    return 0;
}

希望能帮助到大家！