关于统计方案的问题
查看原帖
关于统计方案的问题
237893
donkeys楼主2022/6/1 16:58

wa:

    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(minn[a][i]>maxn[j][b])++c1;
            if(minn[a][i]==maxn[j][b]&&maxn[a][i]==minn[j][b])++c2;
            if(maxn[a][i]<minn[j][b])++c3;
        }
    }

ac:

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
	bool EOFstate = 0;
	template<typename T>inline void read(T &x)
	{
		x = 0; int f = 1; char c = getchar();
		while(('0' > c || c > '9') && !EOFstate) { if(c == '-')f = -1; c = getchar(), EOFstate = c == EOF; }
		while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + c - '0', c = getchar();
		x *= f;
	}
	template<typename T = int>inline T read()
	{
		T x;
		x = 0; int f = 1; char c = getchar();
		while(('0' > c || c > '9') && !EOFstate) { if(c == '-')f = -1; c = getchar(), EOFstate = c == EOF; }
		while('0' <= c && c <= '9')x = (x << 3) + (x << 1) + c - '0', c = getchar();
		x *= f;
		return x;
	}
	template<typename T>inline void write(T x, char end = ' ')
	{
		if(x == 0)return putchar('0'), putchar(end), void();
		if(x < 0)putchar('-'), x = -x;
		char c[21], cnt = 0;
		while(x)c[cnt++] = x % 10 + '0', x /= 10;
		while(cnt)putchar(c[--cnt]); putchar(end);
	}
}using namespace IO;

const int N=55;
char ma[N][N];
int n,a,b;
int maxn[N][N],minn[N][N];

int main()
{
    read(n),read(a),read(b);
    for(int i=1;i<=n;++i)
        scanf("%s",ma[i]+1);
    for(int i=1;i<=n;++i)
    {
        for(int j=1;j<=n;++j)
        {
            if(i==j)continue;
            if(ma[i][j]=='?')
                maxn[i][j]=2,minn[i][j]=-2;
            else if(ma[i][j]=='+')
                maxn[i][j]=2,minn[i][j]=1,maxn[j][i]=-1,minn[j][i]=-2;
            else if(ma[i][j]=='-')
                maxn[i][j]=-1,minn[i][j]=-2,maxn[j][i]=2,minn[j][i]=1;
        }
    }
    for(int k=1;k<=n;++k)
        for(int i=1;i<=n;++i)
            for(int j=1;j<=n;++j)
            {
                maxn[i][j]=min(maxn[i][j],maxn[i][k]+maxn[k][j]);
                minn[i][j]=max(minn[i][j],minn[i][k]+minn[k][j]);
            }
//    int minabuc[10]={0},maxabuc[10]={0},minbbuc[10]={0},maxbbuc[10]={0};
//    for(int i=1;i<=n;++i)
//    {
//        minabuc[minn[a][i]+3]++,maxabuc[maxn[a][i]+3]++;
//        minbbuc[minn[b][i]+3]++,maxbbuc[maxn[b][i]+3]++;
//    }
//    minabuc[minn[a][a]+3]--,maxabuc[maxn[a][a]+3]--;
//    minbbuc[minn[b][b]+3]--,maxbbuc[maxn[b][b]+3]--;
//    for(int i=1;i<=5;++i)
//        minabuc[i]+=minabuc[i-1],maxabuc[i]+=maxabuc[i-1],minbbuc[i]+=minbbuc[i-1],maxbbuc[i]+=maxbbuc[i-1];
    int c1=0,c2=0,c3=0;
    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(minn[a][i]>maxn[j][b]||minn[b][i]>maxn[j][a])++c1;
            if(minn[a][i]==maxn[j][b]&&maxn[a][i]==minn[j][b]||minn[a][j]==maxn[i][b]&&maxn[a][j]==minn[i][b])++c2;
            if(maxn[a][i]<minn[j][b]||maxn[a][j]<minn[i][b])++c3;
        }
    }
    write(c1),write(c2),write(c3);
	return 0;
}

既然 a+b>c+dac>dba+b>c+d\Leftrightarrow a-c>d-b 那么为什么还要反向判一下 ad>cba-d>c-b

2022/6/1 16:58
加载中...