刷题记录:牛客NC13947Contest

传送门:牛客

题目描述:

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
1
2
3
4
5
6
7
8
9
10
11
12

这道题还是有点难度的,首先是要想到能转化成求逆序对的题目,然后还要会如何求出逆序对,掌握以上知识才能够解决这道题

下面先讲述如何将这道题转化成求逆序对的题目:

首先读完题目我们知道对于一个队伍比另一个的队伍高说明该队伍只要有一场比赛的排名比另一个队伍高且有一场比赛的排名比另一个队伍的排名低.然后我们有以下的想法,假设我们根据一个比赛的排名来储存其他比赛的排名,是不是就可以巧妙的判断出两个队伍之间两场比赛的关系了,可能这一点比较难懂,没关系,可以结合下面举的一个栗子来结合理解:

比如下面这个样例
A B C
1 2 3
2 3 1
3 1 2
然后我们考虑A,B的两场排名,得到以下的数据
2
3
1
此时我们仔细观察我们的储存方式,第一个为2,第二个为3,我们思考一下这代表了什么??
首先这个2是在3的前面的,说明在第一个比赛中甲到排名是比乙高的,所以此时如果排在前面的数字
又比后面的数字要大的话,是不是就意味着甲另一场比赛的排名都是比乙低的呢??,是不是就由此求
出了这两场比赛中的关系?,并且求出以上情况的个数就是直接求出逆序对的个数即可
1
2
3
4
5
6
7
8
9
10
11
12
13

下面是具体的代码(当然要使用longlong):

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
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<
	qsort(1,n,bb);
//	cout<
	qsort(1,n,cc);
	ans/=2;
	cout<<ans<<endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57