刷题记录:牛客NC13947Contest
记录 刷题 牛客
2023-09-14 09:12:53 时间
传送门:牛客
题目描述:
n支队伍一共参加了三场比赛。
一支队伍x认为自己比另一支队伍y强当且仅当x在至少一场比赛中比y的排名高。
求有多少组(x,y),使得x自己觉得比y强,y自己也觉得比x强。
(x, y), (y, x)算一组。
输入:
4
1 3 1
2 2 4
4 1 2
3 4 3
输出:
5
这道题还是有点难度的,首先是要想到能转化成求逆序对的题目,然后还要会如何求出逆序对,掌握以上知识才能够解决这道题
下面先讲述如何将这道题转化成求逆序对的题目:
首先读完题目我们知道对于一个队伍比另一个的队伍高说明该队伍只要有一场比赛的排名比另一个队伍高且有一场比赛的排名比另一个队伍的排名低.然后我们有以下的想法,假设我们根据一个比赛的排名来储存其他比赛的排名,是不是就可以巧妙的判断出两个队伍之间两场比赛的关系了,可能这一点比较难懂,没关系,可以结合下面举的一个栗子来结合理解:
比如下面这个样例
A B C
1 2 3
2 3 1
3 1 2
然后我们考虑A,B的两场排名,得到以下的数据
2
3
1
此时我们仔细观察我们的储存方式,第一个为2,第二个为3,我们思考一下这代表了什么??
首先这个2是在3的前面的,说明在第一个比赛中甲到排名是比乙高的,所以此时如果排在前面的数字
又比后面的数字要大的话,是不是就意味着甲另一场比赛的排名都是比乙低的呢??,是不是就由此求
出了这两场比赛中的关系?,并且求出以上情况的个数就是直接求出逆序对的个数即可
下面是具体的代码(当然要使用longlong):
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string.h>
#include <stack>
using namespace std;
typedef long long ll;
#define inf 0x3f3f3f3f
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
ll x=0,w=1;char ch=getchar();
for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
return x*w;
}
#define maxn 1000000
ll a[maxn],b[maxn],c[maxn];
ll aa[maxn],bb[maxn],cc[maxn];
ll fuzhu[maxn];ll ans=0;
void qsort(ll l,ll r,ll zhiqian[]) {
if(l>=r) return;
ll mid=(l+r)>>1;
qsort(l,mid,zhiqian);qsort(mid+1,r,zhiqian);
ll k=l,i=l,j=mid+1;
while(i<=mid&&j<=r) {
if(zhiqian[i]<=zhiqian[j]) fuzhu[k++]=zhiqian[i++];
else {
fuzhu[k++]=zhiqian[j++];
ans+=(mid-i+1);
}
}
while(i<=mid) fuzhu[k++]=zhiqian[i++];
while(j<=r) fuzhu[k++]=zhiqian[j++];
for(ll ii=l;ii<=r;ii++) zhiqian[ii]=fuzhu[ii];
}
int main() {
ll n;n=read();
for(ll i=1;i<=n;i++) {
a[i]=read();b[i]=read();c[i]=read();
aa[a[i]]=b[i];bb[a[i]]=c[i];cc[b[i]]=c[i];
}
qsort(1,n,aa);
// cout<<ans<<endl;
qsort(1,n,bb);
// cout<<ans<<endl;
qsort(1,n,cc);
ans/=2;
cout<<ans<<endl;
return 0;
}
相关文章
- [记]Centos下流量统计使用记录
- 刷题记录:牛客NC16464[NOIP2015]神奇的幻方
- 刷题记录:牛客NC212226回文数
- 刷题记录:牛客NC13585安卓图案解锁
- 刷题记录:牛客NC15029吐泡泡
- 刷题记录:牛客NC15128老子的全排列呢
- 刷题记录:牛客NC50999表达式计算4
- 刷题记录:牛客NC16660[NOIP2004]FBI树
- 刷题记录:牛客NC16618排座位
- 刷题记录:牛客NC19838可持久化动态图上树状数组维护01背包
- 刷题记录:NC16640[NOIP2007]纪念品分组
- 刷题记录:牛客NC23803DongDong认亲戚
- 刷题记录:牛客NC23619小A的柱状图
- 刷题记录:牛客NC24840[USACO 2009 Mar S]Look Up
- 刷题记录:牛客NC16430[NOIP2016]蚯蚓
- 刷题记录:牛客NC14662小咪买东西&&NC15446wyh的物品
- 刷题记录:牛客NC16619[NOIP2008]传球游戏
- 刷题记录:牛客NC16856[NOI1999]钉子和小球
- 刷题记录:牛客NC51216花店橱窗
- 刷题记录:牛客NC24851[USACO 2009 Oct G]Bessie‘s Weight Prob
- 刷题记录:牛客NC16576[NOIP2012]摆花
- 刷题记录:牛客NC16759[NOIP2000]方格取数
- 刷题记录:牛客NC17193简单瞎搞题
- 刷题记录:牛客NC14704美味菜肴
- 刷题记录:牛客NC16666[NOIP2006]开心的金明
- 刷题记录:牛客NC17890方格填色 [矩阵快速幂详解]
- 刷题记录:牛客NC16129小小粉刷匠
- 刷题记录:牛客NC22600Rinne Loves Dynamic Graph
- 刷题记录:牛客NC24370Milk Routing
- 刷题记录:牛客NC53074Forsaken喜欢独一无二的树
- 刷题记录:牛客NC17877整数序列
- 刷题记录:HDU - 4902 Nice boat 区间修改+区间gcd
- 刷题记录:牛客NC54586小翔和泰拉瑞亚