Lotuses's Blog

P7755 POREDAK 题解

  • 687 字
  1. 1. Solution
    1. 1.0.1. 题意简化：
    2. 1.0.2. 实现：

其实这道题渟水的

Solution

题意简化：

在一堆字符串中间，找到一些两两相对位置正确的字符串的个数。

其实，我们可以给这些字符串标号。

就比如说，按样例 1，

1
2
3
4
5
6
7
8
3

> 1    2     3
alpha beta gamma

> 1     3    2
alpha gamma beta

对正确序列标号为 。

就可以将给出的序列变成 。

于是就只用寻找正确的编号大小关系即可。

可以在上面序列中找到两组：

和 。于是答案就是 。

最后变成了找逆序对正序对的问题。

实现：

编号，再用 枚举就可以啦~

虽然可以用归并排序解逆序对，但时间复杂度不需要。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<bits/stdc++.h>
using namespace std;
map<string,int> mp;
int od[2501];

int main()
{
	int n,ans=0;string str;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>str,mp[str]=i;
	for(int i=1;i<=n;i++) cin>>str,od[i]=mp[str];
	for(int i=1;i<n;i++)
		for(int j=i+1;j<=n;j++)
			if(od[i]<od[j]) ans++;
	printf("%d/%d",ans,n*(n-1)/2);
	return 0;
}

qaq

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可