重庆网站建设论坛,合肥专门做网站,网络工程师证书有哪些,天津全包圆装修公司电话题目:分析与解答#xff1a; 题目:
如果一个字符串包含两个相邻的重复子串#xff0c;则称它是“容易的串”#xff0c;其他串成为“困难的串”。例如:BB,ABCDACABCAB,ABCDABCD都是容易的#xff0c;而D、DC、ABDAB、CBABCBA 都是困难的。 输入正整数n和L#xff0c;…题目:分析与解答 题目:
如果一个字符串包含两个相邻的重复子串则称它是“容易的串”其他串成为“困难的串”。例如:BB,ABCDACABCAB,ABCDABCD都是容易的而D、DC、ABDAB、CBABCBA 都是困难的。 输入正整数n和L输出由前L个字符组成的、字典序第n个小的困难的串。例如当L3时前7个困难的串分别为:A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。 输入保证答案不超过80个字符 输入: 7 3 30 3 输出: ABACA BA ABACA BCACB ABCAB ACABC ACBAC ABA
分析与解答
在回溯算法中应注意避免不必要的判断八皇后问题中只需判断新皇后和之前的皇后是否冲突而不必判断以前的皇后是否相互冲突。 这一题只需判断当前串的偶数项后缀是否对称
BB,长度为1*2的后缀对称 ABCDACABCAB,长度为3*2的后缀对称 ABCDABCD长度为4*2的后缀对称
像这些对称的串必定不为困难的串
#includestdio.h
#includestring.h
#define MAX 90
int S[MAX]; //保存第i个位置应该放哪个字符
int n,L;
int dfs(int cur) //返回0表示已经得到解
{ int i,j,k;if(cur n){for(i0;icur;i){printf(%c,AS[i]);}printf(\n);return 0;}for(i0;iL;i){int ok1; //判断方案是否合法S[cur]i; //将当前位置设定为i“0A1B2C”for(j1;2*jcur1;j) //循环判断长度长度为j*2的后缀{int equal1; //判断后缀中是否有前一半是否等于后一半for(k0;kj;k){if(S[cur-k]!S[cur-k-j]) //只要确定了后缀j*2中有一个不相等则可以确定前一半与后一半不相等{equal0;break;}}if(equal)//前一半等于后一半方案不合法 {ok0;break;}}if(ok){if(!dfs(cur1)) //到这里说明0到cur位置的困难串已经确立好了确立下一个位置就好//如果已经找出字典序第n小的串那么dfscur1返回0此时直接退出 return 0;}}return 1;
}
int main()
{while(scanf(%d%d,n,L)!EOF){memset(S,0,sizeof(S));dfs(0);}return 0;
}
