题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1015
题目大意:读取一个数字和一串字符串.每个大写字母代表一个值.判断是否存在五个大写字母使表达式成立:v - w^2 + x^3 - y^4 + z^5 = target .如果存在.则输出字典序最大的五个大写字母.否则打印no solution.
最简单的dfs即可.
AC代码:
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <vector>
#include <math.h>
#include <functional>
#include <algorithm>
using namespace std;
#define Size 12
typedef long long ll;string str;
ll n;
int visit[Size];
char world[Size];
string res;
int UpCharConvertInt(char a)
{return int(a) - 64;
}
void UpCharConvertString()
{for (int i = 0; i < 5; ++i){res += world[i];}
}
ll get()
{ll a = UpCharConvertInt(world[0]);ll b = UpCharConvertInt(world[1]);ll c = UpCharConvertInt(world[2]);ll d = UpCharConvertInt(world[3]);ll e = UpCharConvertInt(world[4]);return a - pow(b,2) + pow(c,3) - pow(d,4) + pow(e,5);
}
bool flag = false;
//cnt表示已经确定的个数.
void dfs(int cnt)
{//如果已经确定了5个数.则进行判断.if (cnt == 5){if (get() == n){UpCharConvertString();flag = true;}return;}//枚举各种情况.for (int i = 0; i < str.size(); ++i){if (visit[i] == 0){visit[i] = 1;world[cnt] = str[i];dfs(cnt + 1);//由于只需要打印最大的.所以一旦标识符被修改.则立马退出搜索.就好像一层层的退出搜索.if (flag)return;visit[i] = 0;}}
}int main()
{ios::sync_with_stdio(false);cin.tie(0);while (1){cin >> n >> str;if (n == 0 && str == "END")break;memset(visit,0,sizeof(visit));res.clear();flag = false;//先降序排列.sort(str.begin(), str.end(),greater<char>());dfs(0);if (res.empty())cout << "no solution" << endl;elsecout << res << endl;}return 0;
}