当前位置：首页 > news >正文

UVa129 Krypton Factor（回溯法）

news 来源：原创 2024/5/4 5:28:06

题目链接

You have been employed by the organisers of a Super Krypton Factor Contest in which contestants have very high mental and physical abilities. In one section of the contest the contestants are tested on their ability to recall a sequenace of characters which has been read to them by the Quiz Master. Many of the contestants are very good at recognising patterns. Therefore, in order to add some difficulty to this test, the organisers have decided that sequences containing certain types of repeated subsequences should not be used. However, they do not wish to remove all subsequences that are repeated, since in that case no single character could be repeated. This in itself would make the problem too easy for the
contestants. Instead it is decided to eliminate all sequences containing an occurrence of two adjoining identical subsequences. Sequences containing such an occurrence will be called “easy”. Other sequences will be called “hard”. For example, the sequence ABACBCBAD is easy, since it contains an adjoining repetition of the
subsequence CB. Other examples of easy sequences are:
• BB
• ABCDACABCAB
• ABCDABCD
Some examples of hard sequences are:
• D
• DC
• ABDAB
• CBABCBA
In order to provide the Quiz Master with a potentially unlimited source of questions you are asked to write a program that will read input lines from standard input and will write to standard output.

Input
Each input line contains integers n and L (in that order), where n > 0 and L is in the range 1 ≤ L ≤ 26. Input is terminated by a line containing two zeroes.

Output
For each input line prints out the n-th hard sequence (composed of letters drawn from the first L letters in the alphabet), in increasing alphabetical order (Alphabetical ordering here corresponds to the normal ordering encountered in a dictionary), followed (on the next line) by the length of that sequence. The first sequence in this ordering is ‘A’. You may assume that for given n and L there do exist at least n hard sequences. As such a sequence is potentially very long, split it into groups of four (4) characters separated by
a space. If there are more than 16 such groups, please start a new line for the 17th group. Your program may assume a maximum sequence length of 80. For example, with L = 3, the first 7 hard sequences are:

1.题目大意：如果一个字符串包含两个相邻的重复子串，那么其称为“容易的串”，否则称为“困难的串”。现在给出一对n,L，求出包含前L个大写字母的字典序为第n个困难的串。另外在输出上要求每四个字符后面一个空格，每64个字符后面一个回车，并在字符序列的下一行打印串的长度

2.首先看题，想到了一些常规的判断重复方法，却不知道如何按字典序排列，一个令人头疼的条件。看了LRJ的讲解，才知道这无非就是dfs从0-L-1的全排列，求出之后每个位置加上’A’输出即可。然后至于如何判断是否包含相同的子串呢，我们只要判断后缀即可，假如有两个字母，显然比较第一个和第二个，如果在这基础上再添加一个，那么显然前两个就不用比较了，只比较后面两个即可

3.思想懂了，具体的代码还是有点疑惑：“for(int j=1;2*j<=cur+1;j++)”。为什么这里要cur+1呢，我觉得j<=cur/2就行。举了几个例子才看了出来：以样例一为例，假如到最后一个需要判断的字母ABACAB?，那么我们只需要比较的就只有三组：B?,CAB?,BACAB？。因为cur从0开始，而此时cur为6，故cur/2和cur+1/2相等。但是假如cur=5时，这时待判断串的长度为6，那么仍然是需要判断三个子串，所以cur需要加一

4.最后一个很奇怪的地方是，题目说保证至少有n个困难串，但事实上并非如此，第二个样例只有二十八个困难的串。我觉得应该是后面无法添加字符的话就直接返回最大的那个。因此，不能用cur和n比较，要再设置一个统计数量的变量，当其等于n时输出

#include <iostream>

using namespace std;
int n,L,cnt;
int ans[105];

int dfs(int cur){
    if(cnt++ == n){
        for(int i=0;i<cur;i++){
            if(i%64==0 && i) printf("\n");
            else if(i%4==0 && i) printf(" ");
            printf("%c",ans[i]+'A');
        }
        printf("\n%d\n",cur);
        return 0;
    }
    for(int i=0;i<L;i++){
        ans[cur]=i;
        int ok=1;
        for(int j=1;2*j<=cur+1;j++){
            int equ=1;
            for(int k=0;k<j;k++)
            if(ans[cur-k]!=ans[cur-k-j]){ equ=0; break; }
            if(equ){ ok=0; break; }
        }
        if(ok){
            if(!dfs(cur+1)) return 0;
        }
    }
    return 1;
}

int main()
{
    while(scanf("%d%d",&n,&L)!=EOF){
        if(n==0&&L==0) break;
        cnt=0;
        dfs(0);
    }
    return 0;
}