自动搬运

查看原文

来自洛谷，原作者为

	by_chance 还好我拥有不同的宇宙，能治愈所有我偏执的梦。

搬运于2025-08-24 22:33:53，当前版本为作者最后更新于2021-09-23 17:18:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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一样，还要进一步分类讨论。

$n=1$ 时，必然有解；$m=1$ 且 $n≠1$ 时，必然无解；

$m≥2$ 时，可以让所有人第一门学科的分数单调递减，第二门学科的分数单调递增，剩余的分数随意，比如全部满分。

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]$ 时无解。

于是只需考虑每个人的排名，那么怎么得到这个排名呢？

由于每个人分数互不相同，只需统计每个人比多少个人分数高即可。如果有两人比同样多的人分数高则无解。

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$ 即可。

具体细节参见代码:

#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;
}