洛谷P3531 [POI2012]LIT-Letters

题目描述

Little Johnny has a very long surname.

Yet he is not the only such person in his milieu.

As it turns out, one of his friends from kindergarten, Mary, has a surname of the same length, though different from Johnny's.

Moreover, their surnames contain precisely the same number of letters of each kind - the same number of letters A, same of letters B, and so on.

Johnny and Mary took to one another and now often play together.

One of their favourite games is to gather a large number of small pieces of paper, write successive letters of Johnny's surname on them, and then shift them so that they obtain Mary's surname in the end.

Since Johnny loves puzzles, he has begun to wonder how many swaps of adjacent letters are necessary to turn his surname into Mary's. For a child his age, answering such question is a formidable task.

Therefore, soon he has asked you, the most skilled programmer in the kindergarten, to write a program that will help him.

输入输出格式

In the first line of the standard input there is a single integer n(2<=n<=1000000) denoting the length of Johnny's surname.

The second line contains Johnny's surname itself, i.e., contains its n successive letters (without spaces).

The third line contains Mary's surname in the same format: a string of n letters (with no spaces either).

Both strings consist only of capital (upper-case) letters of the English alphabet.

In tests worth 30% of points it additionally holds that n<=1000

Your program should print a single integer to the standard output: the minimum number of swaps of adjacent letters that transforms Johnny's surname into Mary's.

```3
ABC
BCA```

`2`

说明

1. A B \nA B 对于这种情况我们是不用进行交换的
2. A B \nB A 这种情况只需交换一次即可

1 2

2 1 此时2在1前，且2比1大(这不是废话么。。)

1.暴力，绝对TLE

2.归并排序

3.树状数组

多年oi一场空！！！！！！

``` 1 #include<iostream>
2 #include<cstdio>
3 #include<cstring>
4 #include<cmath>
5 #include<algorithm>
6 #include<deque>
7 #include<queue>
8 #define LL long long
9 #define lb(x)    ((x)&(-x))
10 using namespace std;
11 const int MAXN=40000001;
13 {
14     char c=getchar();int x=0,f=1;
15     while(c<'0'||c>'9')    {if(c=='-')    f=-1;c=getchar();}
16     while(c>='0'&&c<='9')    x=x*10+c-48,c=getchar();return x*f;
17 }
18 int n;
19 queue<int>q[28];
20 int a[MAXN];
21 int tree[MAXN];
22 inline void Point_Add(int pos,int val)
23 {
24     while(pos<=n)
25     {
26         tree[pos]+=val;
27         pos+=lb(pos);
28     }
29 }
30 inline int Interval_Sum(int pos)
31 {
32     int ans=0;
33     while(pos)
34     {
35         ans+=tree[pos];
36         pos-=lb(pos);
37     }
38     return ans;
39 }
40 int main()
41 {
43     for(int i=1;i<=n;i++)
44     {
45         char c=getchar();
46         q[c-'A'].push(i);
47     }
48     char c=getchar();// 可恶的换行符
49     for(int i=1;i<=n;i++)
50     {
51         char c=getchar();
52         a[i]=q[c-'A'].front();
53         q[c-'A'].pop();
54     }
55     LL ans=0;
56     for(int i=1;i<=n;i++)
57     {
59         ans+=i-Interval_Sum(a[i]);// 树状数组求逆序对，不懂的自行百度
60     }
61     printf("%lld",ans);
62     return 0;
63 }```

1811 篇文章121 人订阅

0 条评论

相关文章

深入剖析Go语言编程中switch语句的使用

switch语句可以让一个变量对反对值的列表平等进行测试。每个值被称为一个的情况(case)，变量被接通检查每个开关盒(switch case)。 在Go编程，...

37070

Go语言struct类型详解

struct Go语言中，也和C或者其他语言一样，我们可以声明新的类型，作为其它类型的属性或字段的容器。例如，我们可以创建一个自定义类型person代表一个人的...

30470

29030

11120

6110

Golang之接口（interface）

//Golang中的接口，不需要显示的实现。只要一个变量，含有接口类型中的所有方法，那么这个变量就实现了这个接口。

41130

24340

Go语言struct类型详解

struct Go语言中，也和C或者其他语言一样，我们可以声明新的类型，作为其它类型的属性或字段的容器。例如，我们可以创建一个自定义类型person代表一个人的...

28840

26720