题解与代码 - Scores

## 题解

本题部分分较多。

1. 直接输出样例，开场就能得到 $1$ 分的好成绩。

2. $n=1$ 时，即只有一个人。任意输出即可。

3. $m=1$ 时，即只有一门课。很容易就得到选手的排名。（但是由于眼瞎，没看到这个点，所以考场并没有写这个。）

4. $m=2$ 比较难，所以先跳。

5. 我们发现 $a_{i,j}=1$（$i\neq j$）非常简单，因为只需要让 $i$ 号选手语文得 $i$ 分，数学得 $n-i$ 分即可。

6. 然后回到 $m=2$ 的情况。假设 wmh 吊打 wmy，wmy 吊打 zjh，wmy 又吊打 ljm，此时形成一个『吊打链』，在此『吊打链』中的人两两之间必存在吊打关系。而根据题意，我们发现可以构成若干条这样的『吊打链』。

容易发现下面的性质：**任意两个属于不同『吊打链』的人，肯定不存在吊打关系。**

这是因为，若存在吊打关系，这两条链就可以合并为一条链。根据上面的描述，容易发现可以使用并查集维护『吊打链』。

而什么时候会输出 `NO` 呢？容易发现存在 $i,j,k$ 是互不相同的三个人，且 $i$ 吊打 $j$，$j$ 吊打 $k$，此时 $i$ 理应吊打 $k$，而输入要求的并不是这样，就不符合题意，输出 `NO`。

码码码…… Runtime Error！我的实现方式如下：将同一个并查集中的人放到 `vector` 里，对它们进行 **排序**。哪里错了呢？我经过无数次的尝试，终于发现把 `sort` 那行注释掉是 Wrong Answer，而注释回去就变成 Runtime Error。经过一番乱搞，我把选手的排名按照它吊打的人数来计算，就 A 了。（我也不知道为什么，问 STL。）

7. 然后经过冥思苦想，发现整个问题对于 $m=2$ 来说没有什么区别，因为多出来的科目只需要复制任意一个科目的信息即可。

```cpp
// 2023.06.14

#include<bits/stdc++.h>
using namespace std;

int n,m,a[101][101];
bool cmp(int x,int y){
    return a[y][x]==0;
}
int ansx[101],ansy[101],totx,toty;

int fa[101];
int find(int id){
    if(fa[id]==id)return id;
    else return fa[id]=find(fa[id]);
}

int main(){
    int T,TestId; scanf("%d%d",&TestId,&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",a[i]+j);
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]==0&&i!=j&&find(i)!=find(j))
                    fa[find(i)]=find(j);
        bool flag=true;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    if(i!=j&&j!=k&&k!=i&&a[i][j]==0&&a[j][k]==0&&a[i][k]==1)
                        flag=false;
        totx=toty=0;
        int total=0;
        for(int i=1;i<=n&&flag;i++)
            if(find(i)==i){
                total++;
                vector<int> ids; ids.clear();
                for(int j=1;j<=n;j++)
                    if(find(j)==i)ids.push_back(j);
                int rank[101]={};
                for(int j=0;j<ids.size();j++)
                    rank[j]=ids.size();
                for(int j=0;j<ids.size();j++)
                    for(int k=0;k<ids.size();k++)
                        if(j!=k&&a[ids[k]][ids[j]])rank[j]--;
                for(int j=0;j<ids.size();j++)
                    for(int k=0;k<ids.size();k++)
                        if(j!=k&&rank[j]==rank[k])flag=false;
                if(!flag)continue;
                sort(ids.begin(),ids.end(),cmp);
                for(int j :ids)
                    totx++,ansx[j]=n-totx+1;
                reverse(ids.begin(),ids.end());
                for(int j :ids)
                    toty++,ansy[j]=toty;
            }
        if(m==1&&total==1&&flag){
            puts("YES");
            for(int i=1;i<=n;i++)
                printf("%d\n",ansy[i]);
        }
        else if(m==1)puts("NO");
        else if(flag){
            puts("YES");
            for(int i=1;i<=n;i++){
                for(int j=2;j<=m;j++)
                    printf("%d ",ansx[i]);
                printf("%d\n",ansy[i]);
            }
        }
        else puts("NO");
    }
    return 0;
}
```

Scores

题解

本题部分分较多。

直接输出样例，开场就能得到 $1$ 分的好成绩。
$n=1$ 时，即只有一个人。任意输出即可。
$m=1$ 时，即只有一门课。很容易就得到选手的排名。（但是由于眼瞎，没看到这个点，所以考场并没有写这个。）
$m=2$ 比较难，所以先跳。
我们发现 $a_{i,j}=1$ （ $i\neq j$ ）非常简单，因为只需要让 $i$ 号选手语文得 $i$ 分，数学得 $n-i$ 分即可。
然后回到 $m=2$ 的情况。假设 wmh 吊打 wmy，wmy 吊打 zjh，wmy 又吊打 ljm，此时形成一个『吊打链』，在此『吊打链』中的人两两之间必存在吊打关系。而根据题意，我们发现可以构成若干条这样的『吊打链』。

容易发现下面的性质：任意两个属于不同『吊打链』的人，肯定不存在吊打关系。

这是因为，若存在吊打关系，这两条链就可以合并为一条链。根据上面的描述，容易发现可以使用并查集维护『吊打链』。

而什么时候会输出 NO 呢？容易发现存在 $i,j,k$ 是互不相同的三个人，且 $i$ 吊打 $j$ ， $j$ 吊打 $k$ ，此时 $i$ 理应吊打 $k$ ，而输入要求的并不是这样，就不符合题意，输出 NO。

码码码…… Runtime Error！我的实现方式如下：将同一个并查集中的人放到 vector 里，对它们进行排序。哪里错了呢？我经过无数次的尝试，终于发现把 sort 那行注释掉是 Wrong Answer，而注释回去就变成 Runtime Error。经过一番乱搞，我把选手的排名按照它吊打的人数来计算，就 A 了。（我也不知道为什么，问 STL。）
然后经过冥思苦想，发现整个问题对于 $m=2$ 来说没有什么区别，因为多出来的科目只需要复制任意一个科目的信息即可。

代码

// 2023.06.14

#include<bits/stdc++.h>
using namespace std;

int n,m,a[101][101];
bool cmp(int x,int y){
    return a[y][x]==0;
}
int ansx[101],ansy[101],totx,toty;

int fa[101];
int find(int id){
    if(fa[id]==id)return id;
    else return fa[id]=find(fa[id]);
}

int main(){
    int T,TestId; scanf("%d%d",&TestId,&T);
    while(T--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                scanf("%d",a[i]+j);
        for(int i=1;i<=n;i++)fa[i]=i;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(a[i][j]==0&&i!=j&&find(i)!=find(j))
                    fa[find(i)]=find(j);
        bool flag=true;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                for(int k=1;k<=n;k++)
                    if(i!=j&&j!=k&&k!=i&&a[i][j]==0&&a[j][k]==0&&a[i][k]==1)
                        flag=false;
        totx=toty=0;
        int total=0;
        for(int i=1;i<=n&&flag;i++)
            if(find(i)==i){
                total++;
                vector<int> ids; ids.clear();
                for(int j=1;j<=n;j++)
                    if(find(j)==i)ids.push_back(j);
                int rank[101]={};
                for(int j=0;j<ids.size();j++)
                    rank[j]=ids.size();
                for(int j=0;j<ids.size();j++)
                    for(int k=0;k<ids.size();k++)
                        if(j!=k&&a[ids[k]][ids[j]])rank[j]--;
                for(int j=0;j<ids.size();j++)
                    for(int k=0;k<ids.size();k++)
                        if(j!=k&&rank[j]==rank[k])flag=false;
                if(!flag)continue;
                sort(ids.begin(),ids.end(),cmp);
                for(int j :ids)
                    totx++,ansx[j]=n-totx+1;
                reverse(ids.begin(),ids.end());
                for(int j :ids)
                    toty++,ansy[j]=toty;
            }
        if(m==1&&total==1&&flag){
            puts("YES");
            for(int i=1;i<=n;i++)
                printf("%d\n",ansy[i]);
        }
        else if(m==1)puts("NO");
        else if(flag){
            puts("YES");
            for(int i=1;i<=n;i++){
                for(int j=2;j<=m;j++)
                    printf("%d ",ansx[i]);
                printf("%d\n",ansy[i]);
            }
        }
        else puts("NO");
    }
    return 0;
}