UVA129-Krypton Factor(搜索剪枝)

2022-07-17 08:33:03

Problem UVA129-Krypton Factor

Accept：1959 Submit：10261

Time Limit: 3000 mSec

Problem Description

通过了光明狮子的考验，小渡来到了创界山的第二层。没想到第二层的守护神——火焰凤凰正沉迷于字母游戏，不能自拔！为了尽快得到她的帮助，小渡决定出手帮她解决字母游戏的谜题。字母游戏规则是这样的：
一个字母串里包含有两个相邻的重复子串则称为“水串”，否则为“火串”
例如AA、ABCABC都是"水串"，而D、DC、ABDAD、CBABCBA都是“火串"。
输入正整数L和n，输出由前L个字母组成的、字典序第n个的"火串"。

Input

多组输入n和L，1<=L<=26，n>0。输入0 0结束。

Output

对于每个输入，输出第n个"火串"。在下一行输出“火串”的长度。你可以假设对于给定的L和n，至少存在n个“火串”。
由于这样的序列可能非常长，每4个字母分割成一组，如果有超过16个这样的小组，请为第17组开始新的一行。
假设最大“火串”长度为80。
例如，当L = 3时，前7个“火串”是：
A
AB
ABA
ABAC
ABACA
ABACAB
ABACABA

Sample Input

7 3
30 3
0 0

Sample Ouput

ABAC ABA
7
ABAC ABCA CBAB CABA CABC ACBA CABA
28

题解：回溯法。当判断下一个字母能否添加进来时，只需判断目前字符串的后缀即可。

P.S.这个题的输出确实比较坑

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 const int maxl = ;

 int n,L,cnt;

 char ans[maxl];

 bool ok;

 bool Can_Prune(char *str){

     int cur = strlen(str);

     for(int i = (cur+)>>;i < cur;i++){

         int len = cur-i;

         int st = i-len;

         char tmp[maxl];

         strncpy(tmp,str+st,len*sizeof(char));

         tmp[len] = ;

         if(!strcmp(tmp,str+i)) return true;

     }

     return false;

 }

 void dfs(char *ss,int cur){

     if(ok) return;

     for(int i = ;i < L;i++){

         char ch = i+'A';

         ss[cur] = ch;

         ss[cur+] = '\0';

         if(cur> && Can_Prune(ss)) continue;

         cnt++;

         if(cnt == n){

             ok = true;

             int con = ,len = strlen(ss);

             for(int i = ;i < len;i++){

                 printf("%c",ss[i]);

                 if(i%== && i!=len-){

                     con++;

                     if(con == ){

                         con = ;

                         printf("\n");

                     }

                     else printf(" ");

                 }

             }

             printf("\n");

             printf("%d\n",len);

             return;

         }

         dfs(ss,cur+);

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     while(~scanf("%d%d",&n,&L) && (n||L)){

         cnt = ;

         ok = false;

         memset(ans,,sizeof(ans));

         dfs(ans,);

     }

     return ;

 }

码农公寓