xml地图|网站地图|网站标签 [设为首页] [加入收藏]

洛谷P3531 [POI2012]LIT-Letters

来源:http://www.ccidsi.com 作者:集成经验 人气:67 发布时间:2019-09-25
摘要:标题陈诉 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 asurname of the same length, though different from Johnny's. Moreover, th

标题陈诉

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.

交付七个长度同样且由大写西班牙语字母组成的字符串A、B,保障A和B中各种字母出现的次数一样。

这段时间历次能够调换A中相邻五个字符,求最少须求调换多少次能够使得A产生B。

洛谷P3531 [POI2012]LIT-Letters,p3531poi2012

输入输出格式

输入格式:

 

In the first line of the standard input there is a single integer 图片 1 (图片 2) denoting the length of Johnny's surname.

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

The third line contains Mary's surname in the same format: a string of 图片 4 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 图片 5.

 

出口格式:

 

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.

 

标题陈述

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.

交付五个长度一样且由大写西班牙语字母组成的字符串A、B,有限援助A和B中各样字母现身的次数一样。

以后每趟能够调换A中相邻五个字符,求最少要求调换多少次能够使得A形成B。

输入输出样例

输入样例#1: 复制

3
ABC
BCA

出口样例#1: 复制

2

输入输出格式

输入格式:

 

In the first line of the standard input there is a single integer 图片 6 (图片 7) denoting the length of Johnny's surname.

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

The third line contains Mary's surname in the same format: a string of 图片 9 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 图片 10.

 

出口格式:

 

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.

 

说明

交给七个长度一样且由大写保加利亚语字母组成的字符串A、B,保障A和B中每个字母出现的次数同样。

最近历次能够调换A中相邻几个字符,求最少须要沟通多少次能够使得A形成B。

 

大家得以先思考一下小的数据范围

假设唯有A B五个字母

那正是说只有二种景况

  1. A B nA B 对于这种情景大家是毫不进行置换的

  2. A B nB A 这种景色只需沟通叁遍即可

为了便于钻探,大家把 A B依据顺序标号为1 2

那么第三种意况就是

1 2

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

那么大家轻松就能想到:逆序对

要是不放心,能够团结申明几组数据,意会一下就很分明了

后天就有七个难题:

输入输出样例

输入样例#1: 复制

3
ABC
BCA

输出样例#1: 复制

2

一.逆序对怎么求

1.暴力,绝对TLE

2.归并排序

3.树状数组

说明

付出多少个长度同样且由大写希伯来语字母组成的字符串A、B,保障A和B中每一种字母出现的次数同样。

前几日每回能够沟通A中相邻三个字符,求最少须要沟通多少次可以使得A产生B。

 

笔者们能够先牵挂一下小的数量范围

假设独有A B七个假名

那就是