如果一个字符串包含两个相邻的重复子串，则称它为容易的串，其他串称为困难的串,如:BB，ABCDACABCAB,ABCDABCD都是容易的，D,DC,ABDAB,CBABCBA都是困难的。
输入正整数n,L，输出由前L个字符（大写英文字母）组成的，字典序第n小的困难的串。
例如，当L=3时，前7个困难的串分别为:
A,AB,ABA,ABAC,ABACA,ABACAB,ABACABA
n指定为4的话，输出ABAC
思路：
在写的时候遇到一个问题：就是当‘A’‘B’‘C’都行不通的时候就要返回上一层，如果上一层的‘A’‘B’‘C’也试了还不行，就要删除最后一个字符重新选择，但又不好写回溯条件。那么这道题到底需不需要回溯呢？我从网上看到了一句话是解释什么时候回溯什么时候不回溯，我觉得说的特别有道理，一下子让我豁然开朗。
要不增值就在递归的参数里面加，要不就回溯
#include<iostream> #include<cstring> using namespace std; int n,L; bool isHard(string s,char c){ int j = 1; for(int i = s.length() - 1; i >= 0; i-=2){ string s1 = s.substr(i, j); string s2 = s.substr(i + j) + c; if(!s1.compare(s2)){ return false; } j++; } return true; } void dfs(int cnt, string s){ if(cnt == n){ cout << s; exit(0); } for(char i = 'A'; i < 'A' + L; i++){ if(isHard(s,i)){//如果组合起来是困难的串就继续纵向递归 dfs(cnt+1, s+i); } } } int main(){ cin >> n >> L; dfs(0, ""); return 0; } 讯享网
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/30135.html