Krypton Factor 困难的串-Uva 129(回溯)

原题:https://uva.onlinejudge.org/external/1/129.pdf

按照字典顺序生成第n个“困难的串”

“困难的串”指的是形如ABAB, ABCABC, CDFGZEFGZE的串,它们都有相邻的重复子字符串

字母的范围是L,既 'A'到'A' + L


分析: 大体上这是一道生成排列组合的题。难点在于我们如何判断当前生成的串是"困难的串"

我们首先采用递归按照字典顺序从小到大生成串, 那么每一次我们处理的都是前一个"困难的串",

既满足没有相邻重复子串。那么我们如何高效的判断给它新追加的字母会不会使它不满足"困难的串"的条件?


判断方法:

如果最后一个字母等于倒数第二个字母,那么不是困难的串,返回false

再从右往左找第一个和末尾字母相同的字母,因为它有可能是相邻重复串的末尾

然后以找到的字母为中心点,判断左右两边串是不是相等,相等就返回false

重复以上步骤

所以算法时间复杂度是O(n^2)

由于n <= 80

所以完全够用

 #include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = + ;
int sol[MAXN], L, n, cnt, depth;
bool stop; bool check(int index, int chr) {
if (index > ) {
if (chr == sol[index - ]) return false;
int i = index - ;
while (i >= ) {
while(i >= && sol[i] != chr) i--;
if (i >= && sol[i] == chr && i * + >= index) {
bool same = ;
for (int j = index - ; j > i; j--)
if (sol[j] != sol[j - index + i]) same = ;
if (same) return false;
}
i--;
}
}
return true;
} void next_str(int dep) {
if (cnt == n) {
stop = ;
for (int i = ; i < dep; i++) {
if (i && i % == ) putchar('\n');
else if (i && i % == ) putchar(' ');
printf("%c", char(sol[i] + 'A'));
}
depth = dep;
putchar('\n');
return;
}
for (int i = ; i < L; i++) {
if (stop) return;
if (check(dep, i)) {
sol[dep] = i;
cnt++;
next_str(dep + );
}
}
} int main() {
while (scanf("%d%d", &n, &L) == && n) {
stop = ; cnt = depth = ;
next_str();
printf("%d\n", depth);
}
return ;
}
上一篇:精选!15个必备的VSCode插件


下一篇:android动画学习