如果一个字符串不包含相邻的重复字符子串,就叫做困难的串
输入n,l, 输出由前l个字符组成,字典序排第k的串。
1 #include <cstdio> 2 #include <string.h> 3 using namespace std; 4 int cnt,n,l; 5 int A[10000]; 6 int dfs(int cur) 7 { 8 if(cnt++==n) //到第n个 ,输出串 ,返回0 9 { 10 for (int i = 0; i < cur; ++i) 11 printf("%c", A[i]); 12 printf("\n"); 13 return 0; 14 } 15 for (int i = 0; i < l; ++i) //挨个字母往里面试 16 { 17 int ok=1; 18 A[cur]=‘A‘+i; 19 for(int j=1; j*2<=cur+1; j++) //试后一半的元素可不可行 20 { 21 int equal=1; 22 for (int k = 0; k < j; ++k) 23 if(A[cur-k]!=A[cur-j-k]) //有不相等的话就可行 24 { equal=0;break; } 25 if(equal){ //有相等就不可行 26 ok=0;break; 27 } 28 } 29 if(ok) if(dfs(cur+1)==0) return 0; //如果可以的话,继续往下数 30 } 31 return 1; //不可行呀 32 } 33 int main() 34 { 35 36 while(~ scanf("%d%d",&n,&l)) 37 cnt=0,dfs(0); 38 return 0; 39 }
用回溯法,.....