题解 | #Ranking the Cows 奶牛排名#
Ranking the Cows
https://ac.nowcoder.com/acm/problem/25064
题目意思就是要我们确定奶牛产奶率的一个顺序，题目给出了m条信息，但还需要多少条消息。
对于需要多少条信息可以这样理解1.2.3.4.5......我们需要得到第一个位置上的数大于后面的，第二个位置也大于后面的，那么总数就是n*(n-1)/2条消息
对于这些信息可能会有重复的比如u>v,v>k,然后又给一条u>k那么这是重复的，就不能单纯用n*(n-1)/2 - m了
对于两个信息u>v,v>k我们也可以得到u>k;
第一种写法:暴力
三重循环判断i和k的关系能不能通过一个中间值k来传递,如果可以确定i和k的关系那就p[i][j] = 1;
最后统计f[i][j]&&f[j][i]=0的数量会算上两次还有多余的f[i][i]所以最终答案是(sum-n)/2;
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int p[N][N];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i ++)
{
int a,b;
scanf("%d%d",&a,&b);
p[a][b] = 1;
}
for(int k = 1; k <= n; k ++)
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(p[i][k]&&p[k][j])
p[i][j] = 1;
int sum = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= n; j ++)
if(!p[i][j]&&!p[j][i])
sum++;
cout<<(sum-n)/2<<endl;
}
第二种写法:通过位运算来简化循环用bitset<1001>f[1001]来记录两个数之间的关系
f[i][j]代表i>j对于关系传递如果i>j，那么j大于的数可以全部传递到i当然第一种写法我们相当于1000个数全部枚举了一遍(哦!这也可太糟糕了,差点就T了)
这里通过位运算或也就是 | 便可以实现快速传递关系
最后答案就是n*(n-1)/2减去1出现的次数，可以f[i].count()返回1的个数
//小于的情况是0，不确定的情况也是0，还有本身都是0，都是不用考虑的
#include <bits/stdc++.h>
using namespace std;
bitset<1001> f[1001];
void solve1() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
f[u][v] = 1;
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
if (f[i][k])
f[i] |= f[k];
}
}
int ans = (n-1)*n/2;
for (int i = 1; i <= n; i++) {
ans-=f[i].count();
}
printf("%d", ans);
}
void solve2() {}
int main() {
solve1();
}
投递腾讯等公司9个岗位 >
