紫书搜索例题7-5 UVA

题目链接:

题意:

题解:

代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 #define MS(a) memset(a,0,sizeof(a))
 5 #define MP make_pair
 6 #define PB push_back
 7 const int INF = 0x3f3f3f3f;
 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL;
 9 inline ll read(){
10     ll x=0,f=1;char ch=getchar();
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13     return x*f;
14 }
15 //////////////////////////////////////////////////////////////////////////
16 const int maxn = 1e5+10;
17 
18 int n,m,cnt;
19 int S[maxn];
20 
21 bool dfs(int cur){
22     if(cnt++ == n){
23         for(int i=0; i<cur; i++) {
24             if(i%64==0 && i) printf("
");
25             else if(i%4==0 && i) printf(" ");
26             printf("%c",S[i]+'A');
27         }
28         printf("
");
29         printf("%d
",cur);
30         return 0;
31     }
32 
33     for(int i=0; i<m; i++){
34         S[cur] = i;
35         int ok = 1;
36         for(int j=1; j*2<=cur+1; j++){ // 为啥是+1？？ 如果不加1  第一个样例： AABAC AB  也就是当cur=1时，就没循环。
37             int equal = 1;
38             for(int k=0; k<j; k++)
39                 if(S[cur-k] != S[cur-k-j]) { equal = 0; break;}
40             if(equal) { ok = 0; break;}
41         }
42         if(ok) if(!dfs(cur+1)) return 0;
43     }
44     return 1;
45 }
46 
47 int main(){
48     while(scanf("%d%d",&n,&m)){
49         if(n+m==0) break;
50         cnt = 0;
51         dfs(0);
52     }
53 
54     return 0;
55 }
紫书搜索 例题7-5 UVA

题目链接:

题意:

题解:

代码:

紫书搜索例题7-5 UVA
