hdu 1015 Safecracker

原题:hdoj 1015

原题大意

题中给了一个式子 v - w^2 + x^3 - y^4 + z^5 = target 要求输入一个数(即作为target),再给出一个字符串,字符串由从A到Z,26个大写字母组成(A=1, B=2, …, Z=26),式子中的v,w,x,y,z由给出的字符串中的5个字符组成,使得式子能够成立.但是符合条件的有很多时,则按字典顺序且逆序输出一种,若无,则打印”no solution”.

算法分析

因为要按字典序输出最大的一组,所以先要将输进去的字符串重新排序,用C++中stl里sort函数就可以了.
下面可以用枚举(5重循环)或dfs.

程序代码

枚举

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define target(v,w,x,y,z) v-w*w+x*x*x-y*y*y*y+z*z*z*z*z
using namespace std;
char str[30];
int num[30];
int n;
int len;
int flag;
bool cmp(int a,int b)
{
    return a>b;
}
void work()
{
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            if(i!=j)
            for(int k=0;k<len;k++)
            if(k!=i&&k!=j)
                for(int l=0;l<len;l++)
                    if(l!=i&&l!=j&&l!=k)
                    for(int m=0;m<len;m++)
                        if(m!=i&&m!=j&&m!=k&&m!=l)
                        {
                            if(target(num[i],num[j],num[k],num[l],num[m])==n)
                                {
                                    printf("%c",'A'+num[i]-1);
                                    printf("%c",'A'+num[j]-1);
                                    printf("%c",'A'+num[k]-1);
                                    printf("%c",'A'+num[l]-1);                                                                        
                                    printf("%c\n",'A'+num[m]-1);
                                    flag=1;
                                    return ;
                                }
                        }
}
int main()
{
    while(scanf("%d%s",&n,str)&&n&&strcmp("END",str))
    {
        flag=0;
        len=strlen(str);

        for(int i=0;i<len;i++)
            num[i]=str[i]-'A'+1;
        sort(num,num+len,cmp);
        work();
        if(!flag) printf("no solution\n");
    }
    return 0;
}

dfs

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define target(v,w,x,y,z) v-w*w+x*x*x-y*y*y*y+z*z*z*z*z
using namespace std;
char str[30];
int num[30];
int tmp[5];
int n;
int len;
int flag;
bool cmp(int a,int b)
{
    return a>b;
}
void dfs(int m)
{
    if(m>5) return ;
    if(m==5&&target(tmp[0],tmp[1],tmp[2],tmp[3],tmp[4])==n)
    {
        flag=1;        
        printf("%c",'A'-1+tmp[0]);    
        printf("%c",'A'-1+tmp[1]);
        printf("%c",'A'-1+tmp[2]);
        printf("%c",'A'-1+tmp[3]);
        printf("%c\n",'A'-1+tmp[4]);
        return ;
    }
    for(int i=0;i<len&&flag==0;i++)
    {
        if(m==0) 
        {
            tmp[m]=num[i];
            dfs(m+1);
        }
        int ok=1;
        for(int j=0;j<m;j++)
        {
            if(tmp[j]==num[i])
            {
                ok=0;break;
            }
        }
        if(ok)
        {
            tmp[m]=num[i];
            dfs(m+1);
        }
    }

}
int main()
{
    while(scanf("%d%s",&n,str)&&n&&strcmp("END",str))
    {
        flag=0;
        len=strlen(str);

        for(int i=0;i<len;i++)
            num[i]=str[i]-'A'+1;
        sort(num,num+len,cmp);
        dfs(0);
        if(!flag) printf("no solution\n");
    }
    return 0;
}