P7876 「SWTR-07」Scores（hard version）题解
by_chance
·
·
题解
P7876 「SWTR-07」Scores（hard version）
考察思维的构造题。
Testcase #1：n=1。
这时只有一个人，随便输出即可，比如全部满分。
if(t==1){
printf("YES\n");
for(int i=1;i<=m;i++)printf("100 ");
printf("\n");
}
Testcase #4：a[i][j]=1(i≠j)。
这时题目和A1一样，还要进一步分类讨论。
$m≥2$ 时，可以让所有人第一门学科的分数单调递减，第二门学科的分数单调递增，剩余的分数随意，比如全部满分。
```cpp
if(t==4){
if(n==1){
printf("YES\n");
for(int i=1;i<=m;i++)printf("100 ");
printf("\n");
}
else if(m==1&&n!=1)printf("NO\n");
else{
printf("YES\n");
for(int i=1;i<=n;i++){
printf("%d %d ",i,100-i);
for(int j=3;j<=m;j++)printf("100 ");
printf("\n");
}
}
}
```
## Testcase #2 ：$m=1$。
------------
这时，$a[i][j]=1$ 表示 $i$ 的分数比 $j$ 高，$a[i][j]=0$ 表示 $i$ 的分数比 $j$ 低。由此可知 $a[i][j]=a[j][i]$ 时无解。
于是只需考虑每个人的排名，那么怎么得到这个排名呢？
由于每个人分数互不相同，只需统计每个人比多少个人分数高即可。如果有两人比同样多的人分数高则无解。
```cpp
bool f=1;
for(int i=1;i<=n;i++)
for(int j=1;j<i;j++)
if(a[i][j]==a[j][i])f=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j&&!a[i][j])add[j]++;
for(int i=1;i<=n;i++){
if(vis[add[i]])f=0;
vis[add[i]]=1;
}
if(!f)printf("NO\n");
else{
printf("YES\n");
for(int i=1;i<=n;i++)printf("%d\n",add[i]);
}
```
## Testcase #3 ：$m=2$。
------------
到目前为止，我们还没有用到题目中的一个条件：
**如果 $i$,$j$ 被同一个人吊打，或同时吊打同一个人，则他们之间也有一方被另一方吊打。**
这么一来，我们假设某人 $X$ 被 $A$、$B$、$C$…吊打，吊打 $a$、$b$、$c$…，那么 $a$、$b$、$c$、…、$A$、$B$、$C$、…、$X$ 之间的所有吊打关系就明了了。由于吊打关系是具有传递性的，于是这些人之间就形成了明确的排名。为了叙述方便，称这样的一群人为一块。
利用并查集，我们可以处理出所有的块；再利用 Testcase #2 时所用到的方法，确定每个人在该块中的排名。
还是由于这个条件，各块之间一定是互相不比对方差。此时就可以套用 Testcase #4 的情况进行构造。在处理块的同时记录每一块内的第一名，然后各个块的第一名的第一个分数递减，第二个分数递增；每两个块之间要留出足够的分数区间给块内其他人，这就需要记录一下每一块的大小。每块内其他的人用该块第一名减去排名得到分数。
此时的无解情况有两种：各个块内排名有重复，或者存在 $a[i][j]=0$，$a[j][k]=0$，但 $a[i][j]=1$。
## Testcase #5 ：无特殊限制。
------------
在 Testcase #3 的基础上，把每组最高分的另外 $m-2$ 个分数初始化为 $100$ 即可。
具体细节参见代码:
```cpp
#include<bits/stdc++.h>
using namespace std;
int read(){
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
return x*f;
}
int t,T,n,m,tot,f=1;
int a[110][110],vis[110],rk[110],fa[110],cnt[110],root[110],ans[110][110];
vector<int> g[110];//记录各个块内的人员
int get(int x){return (x==fa[x]?x:(fa[x]=get(fa[x])));}
void Union(int x,int y){fa[get(x)]=get(y);}
int main(){
t=read();T=read();
while(T--){
memset(rk,0,sizeof(rk));//每个人在自己的块内的排名
memset(vis,0,sizeof(vis)); //计算排名时，记录该排名是否有人
memset(cnt,0,sizeof(cnt)); //每个块内的人数
tot=0; //块的个数
f=1; //是否有解
n=read();m=read();
for(int i=1;i<=n;i++)while(g[i].size())g[i].pop_back();
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
a[i][j]=read();
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||k==i)continue;
if(a[i][k]==0&&a[k][j]==0&&a[i][j]!=0)f=0;
}
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(i!=j&&!a[i][j])Union(i,j);//处理块
for(int i=1;i<=n;i++)g[get(i)].push_back(i);
for(int x=1;x<=n;x++)
if(g[x].size()){
memset(vis,0,sizeof(vis));
++tot;
cnt[x]=g[x].size();
for(int i=0;i<g[x].size();i++)
for(int j=0;j<g[x].size();j++){
int t1=g[x][i],t2=g[x][j];
if(t1!=t2&&a[t1][t2]==0)rk[t1]++;
}
for(int i=0;i<g[x].size();i++){
if(vis[rk[g[x][i]]])f=0;
vis[rk[g[x][i]]]=1;
if(rk[g[x][i]]==0)root[x]=g[x][i];
}//判定无解
}
if(f==0||(m==1&&tot!=1)){printf("NO\n");continue;}
int sum=0;
for(int i=1;i<=n;i++)if(cnt[i]){
ans[root[i]][1]=sum+cnt[i];
ans[root[i]][2]=100-sum;
for(int j=3;j<=m;j++)ans[root[i]][j]=100;
for(int j=0;j<g[i].size();j++){
int tmp=g[i][j];
for(int k=1;k<=m;k++)
ans[tmp][k]=ans[root[i]][k]-rk[tmp];
}
sum=sum+cnt[i];//记录已处理的人数，确定下一块最高分前两门学科的分数
}
printf("YES\n");
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++)
printf("%d ",ans[i][j]);
printf("\n");
}
}
return 0;
}
```