Safecracker

谁借莪１个温暖的怀抱￠ 2022-05-16 14:04 171阅读 0赞

## Safecracker ##

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 17760 Accepted Submission(s): 9254

Problem Description  
=== Op tech briefing, 2002/11/02 06:42 CST ===  
“The item is locked in a Klein safe behind a painting in the second-floor library. Klein safes are extremely rare; most of them, along with Klein and his factory, were destroyed in World War II. Fortunately old Brumbaugh from research knew Klein’s secrets and wrote them down before he died. A Klein safe has two distinguishing features: a combination lock that uses letters instead of numbers, and an engraved quotation on the door. A Klein quotation always contains between five and twelve distinct uppercase letters, usually at the beginning of sentences, and mentions one or more numbers. Five of the uppercase letters form the combination that opens the safe. By combining the digits from all the numbers in the appropriate way you get a numeric target. (The details of constructing the target number are classified.) To find the combination you must select five letters v, w, x, y, and z that satisfy the following equation, where each letter is replaced by its ordinal position in the alphabet (A=1, B=2, …, Z=26). The combination is then vwxyz. If there is more than one solution then the combination is the one that is lexicographically greatest, i.e., the one that would appear last in a dictionary.”

v - w^2 + x^3 - y^4 + z^5 = target

“For example, given target 1 and letter set ABCDEFGHIJKL, one possible solution is FIECB, since 6 - 9^2 + 5^3 - 3^4 + 2^5 = 1. There are actually several solutions in this case, and the combination turns out to be LKEBA. Klein thought it was safe to encode the combination within the engraving, because it could take months of effort to try all the possibilities even if you knew the secret. But of course computers didn’t exist then.”

=== Op tech directive, computer division, 2002/11/02 12:30 CST ===

“Develop a program to find Klein combinations in preparation for field deployment. Use standard test methodology as per departmental regulations. Input consists of one or more lines containing a positive integer target less than twelve million, a space, then at least five and at most twelve distinct uppercase letters. The last line will contain a target of zero and the letters END; this signals the end of the input. For each line output the Klein combination, break ties with lexicographic order, or ‘no solution’ if there is no correct combination. Use the exact format shown below.”

Sample Input  
1 ABCDEFGHIJKL  
11700519 ZAYEXIWOVU  
3072997 SOUGHT  
1234567 THEQUICKFROG  
0 END

Sample Output  
LKEBA  
YOXUZ  
GHOST  
no solution  
题意分析  
首先默认有个字母到数字的映射，A=1，B=2，C=3 …… Z=26,给出你一个目标数字target，然后给出一串字母，要求从这些字母中选取5个数字vwxyz，满足  
v - w^2 + x^3 - y^4 + z^5 = target。可能有多组解，只输出字典序最大的那个。

wuwu~~最近专题练习搜索~~有些模板还是固定的~  
难度系数在大神那里都不算什么吧 就是想发个博客 检验自己 学的如何 真正想把这一题学好,参考大神博客[https://blog.csdn.net/pengwill97/article/details/54882698][https_blog.csdn.net_pengwill97_article_details_54882698]  
1.1  
**初始化@1 把数组a\[i\]由字母转化为数字**

void init()
    {
        len=strlen(a);
        judge=false;
        memset(visited,0,sizeof(visited));
        sort(a,a+len,cmp);
        for(int i=0;i<len;i++)
        a[i]=a[i]-'A'+1;    
    }

1.2  
**初始化@2把数组b\[i\]由数字转化为字母**

void Init()
    {
        for(int i=0;i<5;i++)
        b[i]=b[i]+'A'-1;
    }

1.3  
**判断条件**

bool check()
    {
         if(n == b[0] - b[1]*b[1] + b[2]*b[2]*b[2] - b[3]*b[3]*b[3]*b[3] + b[4]*b[4]*b[4]*b[4]*b[4]){
            judge=true;
            return true;
    }
        else
            return false;
    }

1.4  
**搜索dfs**

void dfs(int depth)
    {
        //递归边界
        if(judge) return;
        if(depth==5){
            check();return ;
        }
        for(int i=0;i<len;i++)
        {
            if(!visited[i]&&!judge)
            {
                b[depth]=a[i];
                visited[i]=1;
                dfs(depth+1);
                visited[i]=0;
            }
        }
    }

不要忘记题目要求：找到一组字典序最大的解即可。首先是递归边界，如果找到了解（judge为真），停止递归；亦或是当depth为5（代表找到了5个数字）的时候，用check函数判断一下是否满足题目要求。若都不满足递归边界，继续搜索。  
下面的for循环非常像dfs地图的四向搜索，但是len指的是数据中给定的字母序列的长度。那么就指，下一个搜索的目标要在所有的字母序列中找，哪些可以作为搜索目标呢？首先就是这个字母没有被选定过（!visit\[i\] ）并且现在解还没有找到（!judge）。 进入if后，首先把数组b中depth的位置赋值为a\[i\]，代表我数组b选定了你a中i这个位置的数字（或者说是字母）,并且在visit中置为选择过了，dfs(depth+1)继续寻找下一个位置的搜索目标。**别忘了最后把visit\[i\]置为0（无后效性）。**  
1.5  
**主函数**

int main()
    {
        while(scanf("%d %s",&n,a)!=EOF){
            if(n==0&&strcmp(a,"END")==0)
            break;
            init();
            dfs(0);
            Init();
            if(judge) printf("%s\n",b);
            else
            printf("no solution\n");
        }
        return 0;
    }

main函数中完成了数据的读入，init函数把字符数组a中的字母转变成数字，lnit函数在最后输出的时候把数组b中的答案又转变成了字母，check函数就是检查是否是满足题目要求的解。关键在dfs函数。  
1.5  
**代码总览**

//1015
    #include <cstdio>
    #include <iostream>
    #include <cstring>
    #include <algorithm>
    char a[15],b[15];
    int visited[15];
    int len,n,m;
    using namespace std;
    bool judge=false;
    int cmp(char a,char b)
    {
        return a>b;
    }
    void init()
    {
        len=strlen(a);
        judge=false;
        memset(visited,0,sizeof(visited));
        sort(a,a+len,cmp);
        for(int i=0;i<len;i++)
        a[i]=a[i]-'A'+1;    
    }
    void Init()
    {
        for(int i=0;i<5;i++)
        b[i]=b[i]+'A'-1;
    }
    bool check()
    {
         if(n == b[0] - b[1]*b[1] + b[2]*b[2]*b[2] - b[3]*b[3]*b[3]*b[3] + b[4]*b[4]*b[4]*b[4]*b[4]){
            judge=true;
            return true;
    }
        else
            return false;
    }
    void dfs(int depth)
    {
        if(judge) return;
        if(depth==5){
            check();return ;
        }
        for(int i=0;i<len;i++)
        {
            if(!visited[i]&&!judge)
            {
                b[depth]=a[i];
                visited[i]=1;
                dfs(depth+1);
                visited[i]=0;
            }
        }
    }
    int main()
    {
        while(scanf("%d %s",&n,a)!=EOF){
            if(n==0&&strcmp(a,"END")==0)
            break;
            init();
            dfs(0);
            Init();
            if(judge) printf("%s\n",b);
            else
            printf("no solution\n");
        }
        return 0;
    }

[https_blog.csdn.net_pengwill97_article_details_54882698]: https://blog.csdn.net/pengwill97/article/details/54882698