Blog·Tanky WooABOUTRSS

HDU/HDOJ 1015 Safecracker

21 Jan 2011
这篇博客是从旧博客 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用大于号(>)比较。