UVA 129 困难的串

题目如下:

通过了光明狮子的考验,小渡来到了创界山的第二层。没想到第二层的守护神——火焰凤凰正沉迷于字母游戏,不能自拔!为了尽快得到她的帮助,小渡决定出手帮她解决字母游戏的谜题。 字母游戏规则是这样的:

一个字母串里包含有两个相邻的重复子串则称为“水串”,否则为“火串”

例如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;

	}
}
上一篇:用电子表格非线性规划出充值优惠最优解


下一篇:129. Sum Root to Leaf Numbers