首页 > 代码库 > 百练1248:Safecracker

百练1248:Safecracker

2024-10-28 16:02:02   207人阅读

题目链接：http://bailian.openjudge.cn/practice/1248/

题目大意：

给定一个正数target（小于12000000）和一串由大写字母组成的数组（长度为5~12），从数组中挑出5个字母，用v,w,x,y,z表示，这5个字母满足如下关系：

 　　　　v - w2+ x3- y4+ z5= target   其中A=1，B=2，...，Z= 26

当存在多个满足条件的解时，输出按字典序排序的最后一个解

分析：

　　暴力搜索，将输入的字符串转换为数字（1~26），并将其从大到小排序，以保证遍历时遇到的第一个解时字典序最大的解。

#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
string quote;
char temp[15];bool compare(int a,int b){
    return a > b;
}

int main(){
    unsigned int target;
    vector<int> v;
    int two[27];
    int three[27];
    int four[27];
    int five[27];
    for(int i = 1;i <= 26;i++){
        int p = i;
        two[i] = p*p;
        three[i] = two[i] * p;
        four[i] = three[i] * p;
        five[i] = four[i] * p;
    }
    bool find;
    while(true){
        scanf("%d%s",&target,temp);
        quote = temp;
        if(target == 0 && quote == "END")break;
        v.clear();
        int L = quote.length();
        for(int i = 0;i < L;i++)
            v.push_back(quote[i] - ‘A‘ + 1);
        sort(v.begin(),v.end(),compare);
        int size = v.size();
        find = false;
        for(int j = 0;j < size;j++){
            for(int k = 0;k < size;k++){
                if(k == j)continue;
                for(int m = 0;m < size;m++){
                    if(m == k || m == j )continue;
                    for(int n = 0;n < size;n++){
                        if(n == m || n == k || n == j )continue;
                        for(int i = 0;i < size;i++){
                            if(i == j || i == k || i == m || i == n)continue;
                            //if(five[v[i]] < target)break; //最开始剪枝剪错了。。。
                            if(v[j] - two[v[k]] + three[v[m]] - four[v[n]] + five[v[i]]== target)
                            {printf("%c%c%c%c%c\n",v[j]+‘A‘-1,v[k]+‘A‘-1,v[m]+‘A‘-1,v[n]+‘A‘-1,v[i]+‘A‘-1);find = true;break;}
                        }
                        if(find)break;
                    }
                    if(find)break;
                }
                if(find)break;
            }
            if(find)break;
        }
        if(!find)puts("no solution");
    }
}

 

百练1248:Safecracker


联系
我们