这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1015
分析:DFS。
/*
Description:HDOJ 1015
Author: Tanky Woo
Blog: www.WuTianQi.com
Date: 19-01-11 22:08
Note: 转载请保留作者信息
*/
#include
#include
using namespace std;
int tar;
char str[15];
char ans[6];
char wtq[6];
int len;
bool s[15];
bool flag ;
int cal(char num, int k)
{
int t = 1;
for(int i=1; i<=k; ++i)
t *= (num-'A'+1);
return t;
}
int cmp(char a, char b)
{
return a>b;
}
/*
int cmp(const void *a,const void *b)
{
return *(char *)b-*(char *)a;
}
*/
void TK(int n)
{
if(n == 5)
{
int num = cal(ans[0], 1) - cal(ans[1],2) + cal(ans[2],3) - cal(ans[3],4) + cal(ans[4],5);
if(num == tar)
{
strcpy(wtq, ans);
flag = 1;
}
return;
}
for(int j=0; j<len; ++j)
if(s[j] == 0)
{
ans[n] = str[j];
s[j] = 1;
TK(n+1);
if(flag == 1)
return;
s[j] = 0;
}
}
int main()
{
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
while(scanf("%d %s", &tar, str) && !((tar==0)&&(strcmp(str, "END")==0)))
{
memset(s, 0, sizeof(s));
memset(ans, 0, sizeof(ans));
memset(wtq, 0, sizeof(wtq));
flag = 0;
len = strlen(str);
sort(str, str+len, cmp);
//qsort(str, len, sizeof(str[0]),cmp);
TK(0);
if(flag)
cout << wtq << endl;
else
cout << "no solution\n";
}
return 0;
}
先前一直WA,经过miyu提醒才知道。原来我把sort返回值和qsort搞混了。
qsort返回-1,0,1
而
sort返回0, 1
所以qsort要用减号(-)来比较,而sort用大于号(>)比较。