网站公司怎么做的好,如何进行网络推广,淮安做网站服务单位,高淳网站建设1、题目 2、题意
如果一个字符串包含两个相邻的重复子串#xff0c;则称它是“容易的串”#xff0c;其他串称为“困难的串”。例如#xff0c;BB、ABCDACABCAB、ABCDABCD都是容易的的串#xff0c;而D、DC、ABDAB、CBABCBA 都是困难的串。
输入正整数 k k k 和 L L L则称它是“容易的串”其他串称为“困难的串”。例如BB、ABCDACABCAB、ABCDABCD都是容易的的串而D、DC、ABDAB、CBABCBA 都是困难的串。
输入正整数 k k k 和 L L L输出由前 L L L 个字符组成的、字典序第 k k k 小的困难的串。例如当 L 3 L 3 L3 时前 7个困难的串分别为 A、AB、ABA、ABAC、ABACA、ABACAB、ABACABA。输入保证答案不超过80个字符。
3、分析
基本框架不难确定从左到右依次考虑每个位置上的字符。因此问题的关键在于如何判断当前字符串是否已经存在连续的重复子串。例如如何判断ABACABA是否包含连续重复子串呢一种方法是检查所有长度为偶数的子串分别判断每个字串的前一半是否等于后一半。尽管是正确的但这个方法做了很多无用功。还记得八皇后问题中是怎么判断合法性的吗判断当前皇后是否和前面的皇后冲突但并不判断以前的皇后是否相互冲突——那些皇后在以前已经判断过了。同样的道理我们只需要判断当前串的后缀而非所有子串。
提示在回溯法中应注意避免不必要的判断就像在八皇后问题中那样只需判断新皇后和之前的皇后是否冲突而不必判断以前的皇后是否相互冲突。
程序如下
int dfs(int cur) { //返回0表示已经得到解无须继续搜索if(cnt n) {for(int i 0; i cur; i) printf(%c, A S[i]); //输出方案printf(\n);return 0;}for(int i 0; i L; i) {S[cur] i;int ok 1;for(int j 1; j * 2 cur 1; j) { //尝试长度为j*2的后缀int equal 1;for(int k 0; k j; k) //检查后一半是否等于前一半if(S[cur - k] ! S[cur - k - j]) { equal 0; break; }if(equal) { ok 0; break; } //后一半等于前一半方案不合法}if(ok) if(!dfs(cur 1)) return 0; //递归搜索。如果已经找到解则直接退出}return 1;
}有意思的是 L 2 L 2 L2 时一共只有 6 个串当 L ≥ 3 L≥3 L≥3 时就很少回溯了。事实上当 L 3 L3 L3 时可以构造出无限长的串不存在相邻重复子串。
4、代码实现
#includestdio.h
int n, L, cnt;
int S[100];int dfs(int cur) { // 返回0表示已经得到解无须继续搜索if(cnt n) {for(int i 0; i cur; i) {if(i % 64 0 i 0) printf(\n);else if(i % 4 0 i 0) printf( );printf(%c, A S[i]); // 输出方案}printf(\n%d\n, cur);return 0;}for(int i 0; i L; i) {S[cur] i;int ok 1;for(int j 1; j * 2 cur 1; j) {// 尝试长度为j*2的后缀int equal 1;for(int k 0; k j; k) // 检查后一半是否等于前一半if(S[cur - k] ! S[cur - k - j]) { equal 0; break; } if(equal) { ok 0; break; } // 后一半等于前一半方案不合法}if(ok) if(!dfs(cur1)) return 0; // 递归搜索。如果已经找到解则直接退出}return 1;
}int main() {while(scanf(%d%d, n, L) 2 n 0) {cnt 0;dfs(0);}return 0;
}
