UVA - 129 Krypton Factor （困难的串）（回溯法）

题意：求由字母表前L个字母组成的字典序第n小的困难串。（如果一个字符串包含两个相邻的重复子串，则称它是“容易的串”，其他串称为“困难的串”。）

分析：回溯时，检查枚举的当前串是否为困难串的方法：将最后一个字母（下标为cur）与第cur-j个字母不断依次向前比较j个字母。

采用此种方法的原因是，前面的串都已经是回文串。

例如：ABAC，不需检查每个长度为偶数的串是否符合要求，因为枚举的每一步都保证是困难串，所以长度为2的串只需检查AC，无需检查AB，BA。

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

typedef long long ll;

typedef unsigned long long llu;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const ll LL_INF = 0x3f3f3f3f3f3f3f3f;

const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {, , -, , -, -, , };

const int dc[] = {-, , , , -, , -, };

const int MOD = 1e9 + ;

const double pi = acos(-1.0);

const double eps = 1e-;

const int MAXN =  + ;

const int MAXT =  + ;

using namespace std;

int n, L;

int ans[MAXN];

int cnt;

int dfs(int cur){

    if(cnt++ == n){//cnt为当前为第几串

        for(int i = ; i < cur; ++i){

            if(i && (i %  == )) printf("\n");

            else if(i && (i %  == )) printf(" ");

            printf("%c", 'A' + ans[i]);

        }

        printf("\n");

        printf("%d\n", cur);

        return ;

    }

    else{

        for(int i = ; i < L; ++i){

            ans[cur] = i;

            bool ok = true;

            for(int j = ; j *  <= cur + ; ++j){//cur+1为当前串的长度,检查后缀最多只用检查到（cur+1）/2,因为再往前检查，检查的前串短于后串，没必要检查

                bool flag = true;

                for(int k = ; k < j; ++k){

                    if(ans[cur - k] != ans[cur - k - j]){

                        flag = false;

                        break;

                    }

                }

                if(flag){//方案不合法

                    ok = false;

                    break;

                }

            }

            if(ok){//方案合法继续递归

                if(!dfs(cur + )) return ;//已经找到解，退出所有递归

            }

        }

        return ;

    }

}

int main(){

    while(scanf("%d%d", &n, &L) == ){

        if(!n && !L) return ;

        cnt = ;

        memset(ans, , sizeof ans);

        dfs();

    }

    return ;

}

秒客网

UVA - 129 Krypton Factor （困难的串）（回溯法）

相关文章