题目如下:
通过了光明狮子的考验,小渡来到了创界山的第二层。没想到第二层的守护神——火焰凤凰正沉迷于字母游戏,不能自拔!为了尽快得到她的帮助,小渡决定出手帮她解决字母游戏的谜题。 字母游戏规则是这样的:
一个字母串里包含有两个相邻的重复子串则称为“水串”,否则为“火串”
例如AA、ABCABC都是"水串",而D、DC、ABDAD、CBABCBA都是“火串"。
输入正整数L和n,输出由前L个字母组成的、字典序第n个的"火串"。
输入
多组输入n和L,1<=L<=26,n>0。输入0 0结束。
输出
对于每个输入,输出第n个"火串"。在下一行输出“火串”的长度。你可以假设对于给定的L和n,至少存在n个“火串”。
由于这样的序列可能非常长,每4个字母分割成一组, 如果有超过16个这样的小组,请为第17组开始新的一行。
假设最大“火串”长度为80。 例如,当L = 3时,前7个“火串”是:
A
AB
ABA
ABAC
ABACA
ABACAB
ABACABA
样例输入
7 3
30 3
0 0
样例输出
ABAC ABA
7
ABAC ABCA CBAB CABA CABC ACBA CABA
28
解题思路:
这道题的大致框架很好了解,我们首先需要从左到右进行构造困难的串。只不过这道题的难点就是如何判断这个串是困难的串。在这里的方法就是每次尝试将字符填到串中时,都要从后往前进行判断。并且判断时我们只需要将当前串中后缀为2倍的子串进行判断即可。如果当前串中所有后缀为2倍的串,只要其中有一个是简单的串,那么当前串就是简单的串。只有当所有后缀为2倍的子串都是困难的串时,当前串才是困难的串。举例如下:
例如:当L为3时(代表困难的串中只有A B C 三个字母),前7个困难的串的构造过程如下:
- 首先,我们将A填入串中。那么此时串中的元素只有A,当前串中后缀为2倍的子串为空,所以直接进行下一个字母的填入操作。
- 其次,在下一个字母的位置中,我们尝试填入A,那么此时串中的元素为AA,当前串中后缀为2倍的子串为AA,发现这个子串的前子串为A,后子串也为A,它们相等。所以这个串为简单的串。因此不再进行递归,进行回溯操作。
- 由于进行了回溯,所以在下一个字母的位置中(还是第2个位置),我们尝试填入B,那么此时串中的元素为AB,当前串中后缀为2倍的子串为AB,我们发现这个子串的前子串为A,后子串为B,它们不相等。且当前串中后缀为2倍的子串只有一个AB,因此这个串为困难的串,可以向下进行遍历操作。
- 我们在第三个位置中尝试填入A,那么此时串中的元素为ABA,当前串中后缀为2倍的子串为BA(可能你会好奇为什么没有AB? 因为AB在之前已经判断过了,这里就没有必要再次进行判断了。)我们发现这个子串的前子串为B,后子串为A,它们不相等。且当前串ABA中后缀为2倍的子串只有一个BA,因此这个串为困难的串,可以向下进行遍历操作。
- 我们在第四个位置中尝试填入A,那么此时串中的元素为ABAA,当前串中后缀为2倍的子串为 AA 和 ABAA ,我们首先判断 AA 这个子串,我们发现这个子串的前子串为A,后子串也为A,它们相等。因此,只要有一个后缀为2倍的子串为容易的串,则整个串就是容易的串,因此不再进行递归,进行回溯操作。
- 我们在第四个位置中尝试填入B,那么此时串中的元素为ABAB,当前串中后缀为2倍的子串为 AB 和 ABAB,我们首先判断AB这个子串,我们发现这个子串是困难的串,紧接着我们判断ABAB这个子串,我们发现这个子串的前子串为AB 后子串也为AB(具体的比较过程可以看代码),那么这个串就是容易的串。因此不再进行递归,进行回溯操作
- 我们在第四个位置中尝试填入C,那么此时串中的元素为ABAC,这里就不再过多解释了,这个串为困难的串。可以向下进行递归操作。
- 在之后的内容也是按照以上的内容进行判断,这里就不再进行详细述说。
建议还是从头到尾阅读以下代码,阅读代码之后就可以了解本题的全部细节了。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int cnt = 0; //代表字典序号
int l, n; //定义构造困难的串所需要的前l个字符以及字典序的编号
char String[81]; //定义保存字符串的字符数组
int dfs(int cur); //代表构造困难的串所需要的函数
int dfs(int cur) {
int i, j,k;
int ok,easy; //ok代表放入该字母后,该串还是困难的串,可以接着遍历。easy代表串中后缀为2倍的子串是否为容易的串
if (cnt++ == n) { //如果字典序号到达了目标字典序号的话(请注意,字典序号和串的长度并不是一回事,有可能会出现字典序号长而字符串的长度短的情况)
for (i = 0; String[i] != '\0'; i++) {
if(i % 64 == 0 && i != 0){
printf("\n");
}
else if (i % 4 == 0 && i != 0) {
printf(" ");
}
printf("%c", String[i]);
}
cout << "\n"<< strlen(String) << endl;
return 0;
}
for (i = 0; i < l; i++) { //代表所要遍历的字母
String[cur] = i + 'A'; //尝试将字母放入字符串中
ok = 1;
for (j = 1; 2 * j <= cur+1; j++) { //尝试判断当前串中后缀为2倍的子串(如果当前串的长度为2,那么就只判断一次,如果当前串的长度为4,那么就判断两次(2为一个子串,4为一个子串),以此类推)
easy = 1;
for (k = 0; k < j; k++) { //代表判断后缀为2倍的子串中的前后子串(例如:有一个串为AB,那么这个循环就代表判断后缀为2倍的子串AB中前A后B子串的相等情况)
if (String[cur - k] != String[cur - k - j]) { //代表将两个子串进行比较,如果判断的两个子串中有一处不相等的话,就代表是困难的串,如果都相等的话,那么这个串中后缀的子串一定是容易的串。
easy = 0; //代表这个子串是困难串
break; //如果有一处不相等,代表这个串就是困难的串,在这之后的内容就不需要判断了。
}
}
if(easy != 0){ //若当前遍历的这个串为容易的串
ok = 0; //代表就不用向下进行递归操作
break;
}
}
if (ok) {
if (!dfs(cur + 1)) { //若当前串是困难的串则进行下一个字符的选择,且当函数返回0时,代表已经找到了第n个字典序的困难串,那么这时我们需要将函数进行返回,不向下进行搜索了。(如果搜索的话,由于l为3,那么在理论上函数可以构造无限长的困难串,继续搜索下去的话就会导致TLE(无限向下递归))
return 0;
}
}
}
String[cur] = '\0'; //如果在递归当中,没有字符可填入字符串当中的话,那么就要进行递归操作(将之前字符尝试填入的位置清0,不然会影响之后的结果)
return 1;
}
int main() {
while (scanf("%d %d", &n, &l) != EOF) {
memset(String, '\0', sizeof(String)); //每一次示例都要进行清空一下字符数组
if (n == 0 && l == 0) {
return 0;
}
else {
dfs(0);
}
cnt = 0;
}
}