M_sea

洛谷2474 [SCOI2008]天平
LuoguBZOJ分析设$mn[i][j]$表示$a[i]-a[j]$的最小值,$mx[i][j]$表示$a[i]...
扫描右侧二维码阅读全文
14
2019/02

洛谷2474 [SCOI2008]天平

$$\color{RoyalBlue}{\texttt{Luogu紫题200祭}}$$

Luogu

BZOJ

分析


设$mn[i][j]$表示$a[i]-a[j]$的最小值,$mx[i][j]$表示$a[i]-a[j]$的最大值。

然后跑一遍$\texttt{Floyd}$,更新$mn$和$mx$。

然后暴力枚举$C$和$D$,利用$mn$和$mx$统计答案即可。

具体实现和细节见代码。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
#define re register
using namespace std;

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

const int N=50+10;

int n,A,B;
char s[N];
int mn[N][N],mx[N][N];

int main() {
    n=read(),A=read(),B=read();
    for (re int i=1;i<=n;++i) {
        scanf("%s",s+1);
        for (re int j=1;j<=n;++j) {
            if (s[j]=='+') mn[i][j]=1,mx[i][j]=2;
            else if (s[j]=='-') mn[i][j]=-2,mx[i][j]=-1;
            else if (s[j]=='=') mn[i][j]=mx[i][j]=0;
            else mn[i][j]=-2,mx[i][j]=2;
        }
        mn[i][i]=mx[i][i]=0;
    }
    for (re int k=1;k<=n;++k)
        for (re int i=1;i<=n;++i)
            for (re int j=1;j<=n;++j) {
                if (i==j||i==k||j==k) continue;
                mn[i][j]=max(mn[i][j],mn[i][k]+mn[k][j]);
                mx[i][j]=min(mx[i][j],mx[i][k]+mx[k][j]);
            }
    int c1=0,c2=0,c3=0;
    for (re int i=1;i<=n;++i) 
        for (re int j=i+1;j<=n;++j) {
            if (i==A||i==B||j==A||j==B) continue;
            if (mn[A][i]>mx[j][B]||mn[A][j]>mx[i][B]) ++c1;
            if ((mn[A][i]==mx[A][i]&&mn[B][j]==mx[B][j]&&mn[A][i]==-mx[B][j])||
                (mn[A][j]==mx[A][j]&&mn[B][i]==mx[B][i]&&mn[A][j]==-mx[B][i])) ++c2;
            if (mx[A][i]<mn[j][B]||mx[A][j]<mn[i][B]) ++c3;
        }
    printf("%d %d %d\n",c1,c2,c3);
    return 0;
}
最后修改:2019 年 02 月 14 日 03 : 55 PM

1 条评论

  1. xgzc

    Orz

发表评论