网上找的一些试题

1、Hyper Almost Permutative String解题报告题意简述如果一个长度为n的字符串包含前n个大写字母，我们就称之为permutative string。一个长度为n+1的字符串去掉一个字符后是permutative string我们就称为almost permutative string。而一个长度为t的字符串如果他所有长度为n+1的连续子串都是almost permutative string,我们就称之为hyper almost permutative string。现在给两个不同的长度为n的permutative string:s1,s2，你需要找一个最短的hyper

2、 almost permutative string并且同时包含这两个串。算法分析首先，这两个串必定出现在最终答案串的首部和尾部，如果不是，将头尾多余的串去掉，一定不影响结果。任何一个permutative string，例如ABDEC，如果我们在后面添加一个字符，比如说D（添加的字符一定为permutative string中出现的字符，否则肯定不会让解变的更优），得到ABDECD，最后5个字符BDECD不是permutative string，肯定不能作为结尾，因此我们必须再添加新的字符，而在串s2-s6中字母A没出现过，为了保证从下一段(s2-s7)仍然是almost permuatat

3、ive string，我们必须在字符串后添加字母A，这样一直添加下去，直到串变成ABDECDAB为止，具体过程如下：ABDEC-ABDECD-ABDECDA-ABDECDAB最后5的字符为ECDAB，从添加第一个字符D开始，到这一步都是必然发生的结果。而产生了新的permuatative string后。前面的黑色字符ABD，已经对以后的操作没有任何影响，我们可以忽略它的存在。并且在ECDAB后，我们任选字符添加，因此我们可以认为这是有一个开始。对与上面的添加，我们不妨称为一步操作，比较一下操作前后的结果：ABDEC-ECDAB我们发现，由D为中心，前后字符刚好调换，而这个操作需要添加3个字符

4、，不妨认为它的代价就是3。更进一步说，对任意一个permutative string，我们只能对它做一种操作，即以第k字符个为中心，将字符串s1 - sk-1以及sk+1 - sn的字符旋转，代价为k（就是要添加k个字符）。那么这到题目实际就是求从一个permutative string开始，不断选择一种操作，使得串最终变为另一个指定permuatative string，且代价最小。但是新的问题看上去仍然不容易解决，因此需要继续分析下去。定义字符?为可任意添加字符的位置，比如开始时字符串就写成ABDEC?，而添加字符DAB之后变为ECDAB?。但实际上?不一定要出现在串的结果，我们那以把它变

5、成环的形式，例如ABDEC同样可以写成?ABDEC或者DEC?AB严格定义一下：?所在的位置为可插入字符的位置，?之后的字符为串的开始，这样，我们回顾一下之前的操作，ABDEC?-ECDAB?，而ECDAB?又可以写成AB?ECD，比较一下ABDEC?和AB?ECD，你发现了什么？没错，就是D和?的位置颠倒了，而付出的代价则是原串中D和?的距离3。这看上去很神奇，也正因为如此，我们就有思路。我们将原来复杂的操作简化成一个新的操作，即每次可以交换?与s1中任意一个字符的位置，代价为它们间的距离。因为?的存在，对任何一个长度为n的串s,我们都可以根据?的位置把它写成n+1种形式，当然每种形式实际是

6、等价的。很明显对于终状态s2，也是一样。我们不知道最终应该交换成哪种形式，但不管如何，我们可以通过付出时间上的代价依次枚举每个形式，来求出s1到该形式所花费的最小代价，最后多所有可能取一个最优解即可。这样我们就需要解决一个新的问题！我们有两个字符串s1,s2，而且字符串中均有一个字符?，每次可以把s1中的?和另一字符交换，代价是它们之间的距离，求最少要付出多少代价才能使得s1和s2 最终相等。这个问题是可以用贪心法解决，方法如下：从s1的任意一个没有处理过的位置p开始，如果s1p=s2p，则不做任何处理，否则我们找到一个数q，使得s1q=s2p，也就是说我们需要将s1串中q位置的字符交换至p中

7、。接着再处理q，找出需要交换到q的字符的位置，这样一直下去最终必定形成一个环，即s1p1-s1p2-s1p3spk-s1p1而这个环需要分两种情况讨论：若环中包含字符?，则从?开始，按顺序交换字符，k-1次操作后，环中的字符均被交换到目标位置。若环中不包含字符?，则任意枚举一个字符与?交换，相当于用?代替该字符，再按顺序与环中每个元素交换，最后将?交换回原来位置，计算出代价。最后选出代价最小的点交换，完成操作。这样可以在O(N)的时间内计算出将s1通过操作变为s2的最小代价，并且而已轻松得出方案。复杂度时间复杂度: O(N2)空间复杂度: O(N)小结对原题难以下手的情况下，我们对问题进行多次

8、转换，最后变成了一道经典的贪心问题。附录原题268. Hyper Almost Permutative String time limit per test: 1 sec.memory limit per test: 65536 KBinput: standardoutput: standardThe string is called permutative if it consists of N first capital letters in arbitrary order (i.e. A, BA, CABED, DCBA for N=1, 2, 5, 4 correspondingly)

9、. The string is called almost permutative, if it is possible to obtain permutative string from it by removing exactly one symbol (i.e. BA, ABCCD, BCAB, ATB - almost permutative strings for N=1, 4, 3, 2 correspondingly). The string is called hyper almost permutative for some given N, if all its subst

10、rings of length N+1 are almost permutative (i.e. ABCBACB, ABCTABC, CBACAB - hyper almost permutative strings for N=3). Your task is to find the shortest hyper almost permutative string, containing permutative strings S1 and S2 as substrings for some given N. Strings S1 and S2 have the length N. The resulting string should be hyper almost permutative for the same given N. InputThe first line of the input file contains the integer number N (2 = N = 26). The second line contains the permurtative string S1. The third line contains the permurtative st