1 条题解
-
0
本题部分分较多。
-
直接输出样例,开场就能得到 分的好成绩。
-
时,即只有一个人。任意输出即可。
-
时,即只有一门课。很容易就得到选手的排名。(但是由于眼瞎,没看到这个点,所以考场并没有写这个。)
-
比较难,所以先跳。
-
我们发现 ()非常简单,因为只需要让 号选手语文得 分,数学得 分即可。
-
然后回到 的情况。假设 wmh 吊打 wmy,wmy 吊打 zjh,wmy 又吊打 ljm,此时形成一个『吊打链』,在此『吊打链』中的人两两之间必存在吊打关系。而根据题意,我们发现可以构成若干条这样的『吊打链』。
容易发现下面的性质:任意两个属于不同『吊打链』的人,肯定不存在吊打关系。
这是因为,若存在吊打关系,这两条链就可以合并为一条链。根据上面的描述,容易发现可以使用并查集维护『吊打链』。
而什么时候会输出
NO
呢?容易发现存在 是互不相同的三个人,且 吊打 , 吊打 ,此时 理应吊打 ,而输入要求的并不是这样,就不符合题意,输出NO
。码码码…… Runtime Error!我的实现方式如下:将同一个并查集中的人放到
vector
里,对它们进行 排序。哪里错了呢?我经过无数次的尝试,终于发现把sort
那行注释掉是 Wrong Answer,而注释回去就变成 Runtime Error。经过一番乱搞,我把选手的排名按照它吊打的人数来计算,就 A 了。(我也不知道为什么,问 STL。) -
然后经过冥思苦想,发现整个问题对于 来说没有什么区别,因为多出来的科目只需要复制任意一个科目的信息即可。
// 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; }
-
- 1
信息
- ID
- 6773
- 时间
- 500ms
- 内存
- 16MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者