HDU1627 Krypton Factor（DFS）

题目链接

题意：输入 n 和 l，要求输出前 l 个字母组成的第 n 个不含有连续的重复序列的字符串。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n, l, cnt, f; //第cnt个序列
char ans[85];
void dfs(int cur){ //当前搜索到第cur位
    if(cnt == n){
        f = 1;
        int a = 0, b = 0;
        for(int i = 0; i < cur; i++){
            if(a == 4 && b != 16){
                cout << " ";
                a = 0;
            }if(b == 16){
                cout << endl;
                a = b = 0;
            }
            printf("%c", ans[i]+'A');
            a++;
            if(a == 4) b++;
        }
        cout << endl << cur << endl;
        return;
    }
    for(int i = 0; i < l; i++){
        ans[cur] = i;
        int flag = 0;
        for(int j = 1; j <= (cur+1)/2; j++){  //重复序列的元素个数
            flag = 1;
            for(int k = 0; k < j; k++){  
                if(ans[cur-k] != ans[cur-k-j]){
                    flag = 0;
                    break;
                }
            }
            if(flag) break;
        }
        if(flag) continue;
        cnt++;
        if(f) return;
        dfs(cur+1);
    }

}

int main(){
    //freopen("a.txt", "r", stdin);

    while(scanf("%d %d", &n, &l) != EOF && n && l){
        //memset(ans, 0, sizeof(ans));
        cnt = 0;
        f = 0;
        dfs(0);
    }
}