题解 | Cow Contest-牛客假日团队赛8K题
K-Cow Contest_牛客假日团队赛8
https://ac.nowcoder.com/acm/contest/1069/K
题目描述
The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (
Farmer John is trying to rank the cows by skill level. Given a list the results of
输入描述:
* Line 1: Two space-separated integers: N and M
* Lines 2..M+1: Each line contains two space-separated integers that describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B
输出描述:
* Line 1: A single integer representing the number of cows whose ranks can be determined
示例1
输入
5 5
4 3
4 2
3 2
1 2
2 5
输出
2
说明
Cow 2 loses to cows 1, 3, and 4. Thus, cow 2 is no better than any of the cows 1, 3, and 4. Cow 5 loses to cow 2, so cow 2 is better than cow 5. Thus, cow 2 must be fourth, and cow 5 must be fifth. The ranks of the other cows cannot be determined.
解答
这道题很明显有传递性（即a赢b，b赢c，则a赢c，相反，a输b，b输c，则a输c）
我们设两个
型二维数组
和
，其中
表示
赢
，即的实力比强，
表示输，即的实力比弱，一边输入，可以一边初始化和
输入代码： n=read();m=read();
for(i=1;i<=m;i++){
a=read();b=read();
w[a][b]=true;l[b][a]=true;
} 其中read()为读入优化（听说每500万个数据可省100毫秒）
读入优化代码（需要调用cctype库）：
#define g(c) isdigit(c)
#define gc getchar()
int read(){
char c=0;int x=0,f=0;
while (!g(c)) f|=c=='-',c=gc;
while (g(c)) x=x*10+c-48,c=gc;
return f?-x:x;
} 然后，我们对w和l数组分别进行一次floyd算法（n不大，能过）
floyd算法代码：
void floyd(bool f[N][N]){
//注意不能写成floyd(bool f[][])，会CE(编译错误)
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if (i!=k)
for(int j=1;j<=n;j++)
if (j!=i&&j!=k)
f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);
}
//因为floyd算法要进行两遍且两遍代码几乎一样
//所以我们可以把floyd算法定义为一个函数，而非直接打两遍几乎一样的代码
int main(){
读入+预处理
floyd(w);floyd(l);
} 最后，我们对于每个
，枚举
，若或，我们把计算器s++,若
则答案
，输出ans程序结束
因为时，
肯定等于
（即不可能赢，倒回来又赢），同理时，
肯定等于，所以不会出现少算或多算
实际测试中
和
肯定等于，所以和不必判断是否相等
for(i=1;i<=n;i++){
for(j=1,s=0;j<=n;j++)
if (w[i][j]) s++;
for(j=1;j<=n;j++)
if (l[i][j]) s++;
if (s==n-1) ans++;
}
printf("%d",ans); 完整代码： #include <bits/stdc++.h>
using namespace std;
const int N=105;
bool w[N][N],l[N][N];
int n,m,a,b,i,j,s,ans;
#define g(c) isdigit(c)
#define gc getchar()
int read(){
char c=0;int x=0,f=0;
while (!g(c)) f|=c=='-',c=gc;
while (g(c)) x=x*10+c-48,c=gc;
return f?-x:x;
}
void floyd(bool f[N][N]){
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
if (i!=k)
for(int j=1;j<=n;j++)
if (j!=i&&j!=k)
f[i][j]=f[i][j]||(f[i][k]&&f[k][j]);
}
int main(){
// freopen("t2.in","r",stdin);
n=read();m=read();
for(i=1;i<=m;i++){
a=read();b=read();
w[a][b]=true;l[b][a]=true;
}
//读入+预处理
floyd(w);floyd(l);
//floyd算法
for(i=1;i<=n;i++){
for(j=1,s=0;j<=n;j++)
if (w[i][j]) s++;
for(j=1;j<=n;j++)
if (l[i][j]) s++;
if (s==n-1) ans++;
}
//计算结果
printf("%d",ans);
return 0;
} 最后，说一下万能头bits/stdc++.h
noi比赛文件中说：理论上可以用万能头，但实际中可能不支持使用万能头，若因为使用万能头而导致CE（编译错误），比赛概不负责，即选手负全责！！！
所以，比赛时建议不要使用万能头，平时可以稍微使用一下
来源：少年更应学习，将来为祖国奋斗！
