Krypton Factor-紫书第七章暴力求解

目录

题目描述

题目背景

输入描述

输出描述

样例输入

样例输出

题目大意

思路

AC代码

注意 

---

题目描述

题目背景

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.

输入描述

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

输出描述

For each input line prints out the nn-th hard sequence (composed of letters drawn from the first LL 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 nn and LL there do exist at least nn 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=3L=3, the first 7 hard sequences are:

A

AB

ABA

ABAC

ABACA

ABACAB

ABACABA

样例输入

7 3
30 3
0 0

样例输出

ABAC ABA
7
ABAC ABCA CBAB CABA CABC ACBA CABA
28

题目大意

 输入一个n和L，由前L个字母组成的困难的串(相邻的没有相同的字串)，按照字典序排序，输出第n个困难的串。

思路

递归深搜，加上判断，判断时间只判断后缀就行，前面部分已经判断满足条件，只需要判断后面即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5+10;
int n,l,cnt;
int a[N];

int dfs(int t)
{
    if(cnt++ == n){//已经找到第n个
        for(int i = 0;i < t;i++)//输出时间注意题目要求的格式
        {
            if(i%4 == 0 && i != 0 && i%64 != 0)
                cout << " ";
            else if(i != 0 && i%64 == 0)
                cout << endl;
            printf("%c", 'A'+a[i]);
        }
        if(t%64 != 0)
            cout << endl;
        cout << t << endl;
        return 0;
    }
    for(int i = 0;i < l;i++){//深搜遍历
        a[t] = i;
        int flag = 1;
        for(int j = 1;j*2 <= t+1;j++){//判断是否满足困难串的条件
            int flag1 = 1;
            for(int k = 0;k <j;k++){
                if(a[t-k] != a[t-j-k]){
                    flag1 = 0;
                    break;
                }
            }
            if(flag1)
            {
                flag = 0;
                break;
            }
        }
/*
判断方法：从最后开始，最后一个与前面相邻的一个不相等就满足第一个，
其次进行间隔两个判断，依次进行，判断有无不满足的。
因为前面已经判断过了，所以每个只需要判一次。
*/
        if(flag){
            if(!dfs(t+1))//！dfs代表找到了返回了0
                return 0;
        }
    }
    return 1;
}

int main()
{
    while(cin >> n >> l){
        cnt = 0;
        if(n == 0 && l == 0){
            return 0;
        }
        dfs(0);
    }
}

注意 

特别注意：格式问题，题目中明确说明了，每4个为一组，一行最多16组，输出长度时间，如果正好最后有一个16组的换行就不需要换行，如果不是，需要输出一个换行。