UVA129 暴力dfs，有许多值得学习的代码

紫书195

题目大意：给一个困难的串，困难的串的定义就是里面没有重复的串。

思路：不需要重新对之前的串进行判重，只需要对当前的加入的字符进行改变即可。

因为是判断字典序第k个的字符串，所以要多一个全局变量cnt来记录目前是第几次循环到了。

 1 #include<bits/stdc++.h>
 2 
 3 using namespace std;
 4 const int maxn = 1000000 + 5;
 5 int n, L;
 6 int s[maxn];
 7 int cnt;
 8 
 9 bool dfs(int cur){
10     //printf("cur = %d
", cur);
11     if (cnt++ == n){
12         for (int i = 0; i < cur; i++){
13             if (i % 64 == 0 && i > 0) printf("
");
14             else if (i % 4 == 0 && i > 0) printf(" ");
15             printf("%c", s[i] + 'A');
16 
17         }
18         printf("
");
19         printf("%d
", cur);
20         return 0;
21     }
22     else {
23         for (int i = 0; i < L; i++){
24             s[cur] = i;
25             bool flag = true;
26             /*下面的这个暴力枚举半长的一定要学会*/
27             for (int j = 1; j * 2 <= cur + 1; j++){/*必须cur+1，因为cur是从第0位开始的*/    
28                 int equa = 1;
29                 for (int k = 0; k < j; k++){
30                     if (s[cur - k] != s[cur - j - k]){
31                         equa = 0;
32                         break;
33                     }
34                 }
35                 if (equa == 1) {flag = false; break;}
36             }
37             if (flag){
38                 if (!dfs(cur + 1)) return false;
39             }
40         }
41     }
42     return 1;
43 }
44 
45 int main(){
46     while (scanf("%d%d", &n, &L) && n + L != 0){
47         cnt = 0;
48         dfs(0);
49     }
50     return 0;
51 }

View Code

关键：暴力dfs法不需要对之前已经确定的状态再次进行条件确定。二分寻找合法串。全局记录字典序的序列。

并且懂得暴力枚举一般的技巧

定义！！！！很重要。

目前如果我们放入的这个串合法的，那么二分j，那么对于cur-j和cur-j-k也必须要是合法的才行，所以这个是判断的条件，也是新手入门的难点