https://vjudge.net/problem/UVA-129
這題看了我很久，一是因為溯回法還不熟 理解上有誤，二是將cnt看成了cur...

#define _CRT_SECURE_NO_WARNINGS    
#include<cstdio>  
#include<cstring>  
using namespace std;  
  
#define N 80+10  
int S[N];  
int n, L;  
int cnt;  
  
int dfs(int cur)  
{  
    if (cnt++ == n)  
    {  
        for (int i = 0; i < cur; i++)  
        {  
            printf("%c", 'A' + S[i]);  
            if ((i + 1) % 4 == 0)  
            {  
                if ((i + 1) % 64 == 0)printf("\n");  
                else if (i != cur - 1)printf(" ");  
            }  
        }  
        if (cur % 64)printf("\n");  
        printf("%d\n", cur);  
        return 0;//返回0表示已經(jīng)找到了解  
    }  
    for (int i = 0; i < L; i++)  
    {  
        if(cnt!=1) if(i == S[cur - 1])continue; //除了第一個之外 其他的都不等于上一個 
        S[cur] = i;  
        //printf(" %d ",  cur );
        int ok = 1;  
        for (int j = 1; j * 2 <= cur + 1; j++)//枚舉后綴的長度（注意不是整個串的長度）  
        {  
            int equal = 1;  
            for (int k = 0; k < j;k++)//檢查前綴和后綴是否相等，S[cur-k]是后綴部分，S[cur-k-j]是前綴部分  
            if (S[cur - k] != S[cur - k - j]){ equal = 0; break; }  //如果能找到一個不等則遞歸 否則繼續(xù)循環(huán)  這里break之后不會進入下一個if 而是繼續(xù)循環(huán) 直至遍歷完成
            if (equal){ ok = 0; break; }   //如果進入了 ， 就會再次進行選擇字母
        }  
        if (ok)if (!dfs(cur + 1))return 0;//如果找到解，直接退出  
    }  
    return 1;  
}  
int main()  
{  
    //freopen("t.txt", "r", stdin);  
    while (~scanf("%d%d", &n, &L)&&(n||L))  
    {  
        cnt = 0;  
        memset(S, 0, sizeof(S));  
        dfs(0);  
    }  
    return 0;  
}

我做了一個小小的優(yōu)化： if(cnt!=1) if(i == S[cur - 1])continue; //除了第一個之外 其他的都不等于上一個

圖片發(fā)自簡書App

幾個疑問：
0 后綴是什么？ 后綴在我理解起來就是所有的從新輸入起的后一半 所有的后綴 是1，2，3，...，（cur+1）[數(shù)組實際使用元素個數(shù)]/2
1 為什么該溯回不用復原？ 因為cur的控制只會用到cur+1個元素 后面的元素會先被賦值
2 三個for分別控制什么？ 第一個：嘗試字母的個數(shù) 第二個：與第三個結(jié)合 遍歷所有后綴
3 奇數(shù)怎么辦？
4 為什么有任意的不同即可？ 因為只要有一個不同 代表當前判斷的這組后綴（1-（cur+1）/2中的某一組）不同
5 溯回在哪了？ 這里的溯回 跟前面一樣 是因為前面一個選錯而使得后面的值都不滿足

 0  1  2  3  3  4  5  6  7  7  6  7  8  8  9  9  10  11  12  12  13  14  15  16  16  17  18  19  19  20  21  21  22  22  23  24  25  25  24  25  26  27

這是輸入 30 3后，輸出的cur，很明顯，第一個回溯發(fā)生在 7 7 6 7 8 8 ， 實際上L>= 3時，回溯已經(jīng)很少發(fā)生了，而且可以構(gòu)造出無限長的串

另外 這里有個常用技巧 就是將字母換成數(shù)字來表