ACM题目————困难的串

题目描述

如果一个字符串包含两个相邻的重复子串，则称他是“容易的串”,其他串称为"困难的串"。例如，BB，ABCDACABCAB,ABCDABCD都是容易的串，而D,DC,ABDAB,CBABCBAD都是困难的串。

输入

输入正整数n和L。

输出

输出由前L个字符串组成的，字典序第k小的困难的串。例如，当L=3时，前7个困难的串分别为A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA。输入保证答案不超过80个字符。

样例输入

7 3
30 3

样例输出

ABACABA
ABACABCACBABCABACABCACBACABA

成功对着小白敲了一次，然并卵，不懂题。

//困难的串
#include <iostream>
#include <string.h>
#include <stdio.h>

using namespace std;
int n, s[1001], L, cnt;

int DFS(int cur)
{
    if(cnt ++ == n )
    {
        for(int i=0; i<cur; i++) printf("%c",'A'+s[i]);
        printf("
");
        return 0;
    }
    for(int i=0; i<L; i++)
    {
        s[cur] = i ;
        int OK = 1 ;
        for(int j=1; j*2<=cur+1; j++)
        {
            int e = 1 ;
            for(int k=0; k<j; k++)
                if(s[cur-k] != s[cur-k-j])
                {
                    e = 0 ;
                    break ;
                }
            if(e)
            {
                OK = 0 ;
                break ;
            }
        }
        if(OK) if(!DFS(cur+1)) return 0;
    }
    return 1;
}

int main()
{
    while(~scanf("%d %d",&n, &L))
    {
        cnt = 0;
        memset(s,0,sizeof(s));
        DFS(0);
    }

    return 0;
}