題意：如果一個字符串包含兩個相鄰的重復子串，則稱它是“容易的串”，其他串稱為“困難的串”

輸入正整數(shù)n和L，輸出由前L個字符組成的并且它的字典序是第n小的串，和輸出這個串的長度

樣例輸入：

7 3

30 3

樣例輸出：

ABAC ABA

7

ABAC ABCA CBAB CABA CABC ACBA CABA?

28

為了避免判斷做無用功，每次都從尾部開始，枚舉所有可能長度，在和前面的串匹配。因為前面的串已經(jīng)匹配過，所以可以直接從尾部開始。

#include<iostream> #include <string> #include <string.h> using namespace std; const int maxn = 10000; int cnt = 0,n,l; int c[maxn]; int dfs(int cur) {if (cnt++ == n) {//到達第n小的字典序int nextline = 0;for (int i = 0; i < cur; i++) {printf("%c", c[i] + 'A');if ((i + 1) % 4 == 0 && i != cur - 1) { nextline++;if (nextline % 16 == 0){printf("\n");continue;}printf(" ");}}printf("\n%d\n",cur);return 0;}for (int i = 0; i < l; i++) {//搜索前l(fā)個字母int ok = 1;c[cur] = i;for (int j = 1; 2 * j <= cur + 1; j++) {//枚舉長度，cur是從0開始所以要加一int equal = 1;for (int k = 0; k < j; k++) {//搜索長度為j的串是否和前面相鄰的長度為j的串相等//不以cur結(jié)尾的串都在前面已經(jīng)判斷過，所以不用判斷if (c[cur - k] != c[cur - k - j]) {//存在不等equal = 0; break;}}if (equal) {//若相等則不dfs下一個ok = 0; break;}}if (ok)if (!dfs(cur + 1))return 0;//如果搜索到了就退出}return 1; } int main() { #ifdef LOCALfreopen("data.in", "r", stdin);//scanffreopen("data.out", "w", stdout);//printf #endifwhile (cin >> n >> l && n&&l) {cnt = 0;dfs(0);}//system("pause");return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的回溯法之避免无用判断 UVA129 Krypton Factor困难的串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。