一道差分约束好题。

题目描述

有 $n$ 个砝码，所有砝码有 $3$ 种：$1$ 克，$2$ 克，$3$ 克。

给出 $n$ 个砝码之间的关系，并点出所有砝码中的两个砝码的编号 $A$ 与 $B$，将这两个砝码一起放置在天平左端，并将除了 $A$ 和 $B$ 之外的其他砝码中选两个放在天平的右端。求左端重的方案数，一样重的方案数，右端重的方案数。

数据很小，$n \le 50$。（随便搞

题目分析

只给出砝码之间的两两关系，不容易求得每个砝码的具体重量。

尝试从答案入手，由果及因，设其他选出的两个砝码编号为 $C$ 和 $D$。假使此时是左端重，则 $A+B>C+D$，则应满足 $A-C>D-B$ 或 $A-D>C-B$。

为了判断差的大小，容易想到维护两个数组 $fx_{i,j}$ 与 $fn_{i,j}$，分别表示 $i-j$ 的可能的最大值和最小值。判断大小的时候比较数组 $fx$ 和 $fn$ 就可以了。

这样，对于每个条件，我们做出如下操作：

• 若关系为 =，考虑极限情况，则 $fx_{i,j}=0$ 且 $fn_{i,j}=0$。

• 若关系为 -，考虑极限情况，则 $fx_{i,j}=-1$ 且 $fn_{i,j}=-2$。

• 若关系为 +，考虑极限情况，则 $fx_{i,j}=2$ 且 $fn_{i,j}=1$。

• 若关系为 ?，考虑极限情况，则 $fx_{i,j}=2$ 且 $fn_{i,j}=-2$。

• 若 $i=j$，则 $fx_{i,j}=0$ 且 $fn_{i,j}=0$。

以上其实就是建边。

建完边后跑 floyd，有点类似于传递闭包的样子将任意两点差的上下界求出来，就可以统计答案啦。

时间复杂度：$O(n^3)$

Code

代码还是很短滴。

#include<bits/stdc++.h>
using namespace std;
const int maxn=70;
int n,a,b,fx[maxn][maxn],fn[maxn][maxn],cnt1,cnt2,cnt3;
char x;
inline void floyd(){
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				fx[i][j]=min(fx[i][j],fx[i][k]+fx[k][j]);
				fn[i][j]=max(fn[i][j],fn[i][k]+fn[k][j]);
			}
		}
	}
}
int main(){
	scanf("%d%d%d",&n,&a,&b);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>x;
			if(i==j||x=='=') fx[i][j]=fn[i][j]=0;
			else if(x=='-') fx[i][j]=-1,fn[i][j]=-2;
			else if(x=='+') fx[i][j]=2,fn[i][j]=1;
			else fx[i][j]=2,fn[i][j]=-2;
		}
	}
	floyd();
	for(int i=1;i<=n;i++){
		if(i==a||i==b) continue;
		for(int j=i+1;j<=n;j++){
			if(j==a||j==b) continue;
			if(fn[a][j]>fx[i][b]||fn[a][i]>fx[j][b]) cnt1++;
			if(fx[a][j]<fn[i][b]||fx[a][i]<fn[j][b]) cnt3++;
			if((fn[a][j]==fx[a][j]&&fx[a][j]==fn[i][b]&&fn[i][b]==fx[i][b])||
			(fn[a][i]==fx[j][b]&&fx[j][b]==fx[a][i]&&fx[a][i]==fn[j][b])) cnt2++;
		}
	}
	printf("%d %d %d\n",cnt1,cnt2,cnt3); 
	return 0;
}

写的时候注意搞清楚关系。希望对你有帮助qwq

这是ljw觉得自己最nt的一次 ——不是 Lofty 的ljw

【题目详解】

本题要求多个东西之间的大小关系，但凡上过初中就知道要往不等式的思路去想。因为是给出了多个物品之间的二元关系，且具有传递性，求尽可能多的推出元素之间的关系，就是很明显的传递闭包。翻看蓝书，floyd可以解决传递闭包的关系问题。思考如何构图，对于每个关系，可以确定两个砝码的关系，即当“+”时，这两个砝码的取值线段为从1到2，同理“-”时，取值线段为-2到-1，而“?”时，为-2到2。以此为基础构图，分别跑floyd，求出两个砝码的取值线段范围，再根据取值范围列不等式计算，对于线段下限大于另一线段上限的，c1++，同理c2、c3也用相应方式列不等式，判断累加。

#include <bits/stdc++.h>
using namespace std;
const int N = 110;
char ch[N][N];
int lim[N][N], uplim[N][N];

int main() {
    int n, A, E;
    scanf("%d%d%d", &n, &A, &E);
    for (int i = 1; i <= n; i++) {
        scanf("%s", ch[i] + 1);
        for (int j = 1; j <= n; j++) {
            if (ch[i][j] == '=' || i == j) {
                lim[i][j] = uplim[i][j] = 0;
            } else if (ch[i][j] == '-') {
                lim[i][j] = -2; uplim[i][j] = -1;
            } else if (ch[i][j] == '+') {
                lim[i][j] = 1; uplim[i][j] = 2;
            } else if (ch[i][j] == '?') {
                lim[i][j] = -2; uplim[i][j] = 2;
            }
        }
    }
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j && j != k && i != j) uplim[i][j] = min(uplim[i][j], uplim[i][k] + uplim[k][j]);
                lim[i][j] = max(lim[i][j], lim[i][k] + lim[k][j]);
            }
        }
    }
    int c1 = 0, c2 = 0, c3 = 0;
    for (int C = 1; C <= n; C++) {
        for (int D = 1; D < C; D++) { // nt错误D <= C，一个砝码不能被选两次
            if (C == A || C == E || D == A || D == E) continue;
            if (lim[A][C] > uplim[D][E] || lim[A][D] > uplim[C][E]) c1++;
            else if ((uplim[A][C] == lim[A][C] && uplim[D][E] == lim[D][E] && uplim[A][C] == lim[D][E]) || (uplim[A][D] == lim[A][D] && uplim[C][E] == lim[C][E] && uplim[A][D] == lim[C][E])) c2++;
            else if (uplim[A][C] < lim[D][E] || uplim[A][D] < lim[C][E]) c3++;
        }
    }
    printf("%d %d %d", c1, c2, c3);
}