洛谷2474 [SCOI2008]天平

题意

有 $N$ 个重量为 $1,2,3$ 的砝码，以知部分砝码之间的重量关系。给出砝码 $A,B$ ，要求另外选出两个砝码 $C,D$，使得 $A+B > , = , < C+D$ ，求三种情况的方案数。

$4\le N\le 50$ 。

题解

可以先预处理出砝码之间差值的范围。令 $S_i$ 为 $i$ 砝码的重量，用 $mx[i][j]$ 表示 $S_i-S_j$ 的最大值，$mn[i][j]$ 为最小值。因为重量只有三种，所以容易得到。

然后跑 $\text{Floyd}$ 就可以得到所有砝码差值的上界和下界。

对于

$$A+B > C+D$$

可以化为

$$\begin{cases} A-C > D-B \\ A-D > C-B \end{cases}$$

即

$$\begin{cases} mn[A][C] > mx[D][B] \\ mn[A][D] > mx[C][B] \end{cases}$$

两个式子是等价的，也就是说满足其中一个就可以对答案产生贡献。

小于的情况同理。

等于的情况还要求两式上界和下界相等，否则就是不确定的。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

char ch[55];
int n,A,B,mx[55][55],mn[55][55],ans1,ans2,ans3;

signed main()
{
    n=read(); A=read(); B=read();
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ch+1);
        for (int j=1;j<=n;j++)
        {
            if (i==j || ch[j]=='=') mx[i][j]=mn[i][j]=0;
            else if (ch[j]=='+') mx[i][j]=2,mn[i][j]=1;
            else if (ch[j]=='-') mx[i][j]=-1,mn[i][j]=-2;
            else mx[i][j]=2,mn[i][j]=-2;
        }
    }
    for (int k=1;k<=n;k++)
    {
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=n;j++)
            {
                mx[i][j]=min(mx[i][j],mx[i][k]+mx[k][j]);
                mn[i][j]=max(mn[i][j],mn[i][k]+mn[k][j]);
            }
        }
    }
    for (int i=1;i<=n;i++)
    {
        if (i==A || i==B) continue;
        for (int j=1;j<i;j++)
        {
            if (j==A || j==B) continue;
            if (mn[A][i]>mx[j][B] || mn[A][j]>mx[i][B]) ans1++;
            if (mx[A][i]<mn[j][B] || mx[A][j]<mn[i][B]) ans3++;
            if (mx[A][i]==mn[A][i] && mx[j][B]==mn[j][B] && mx[A][i]==mx[j][B]) ans2++;
            else if (mx[A][j]==mn[A][j] && mx[i][B]==mn[i][B] && mn[A][j]==mx[i][B]) ans2++;
        }
    }
    return !printf("%d %d %d",ans1,ans2,ans3);
}