HDU/HDOJ 1015 Safecracker

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=1015

分析:DFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
/*
  Description:HDOJ 1015
  Author: Tanky Woo
  Blog:   www.WuTianQi.com
  Date: 19-01-11 22:08
  Note:  转载请保留作者信息
*/
 
#include <iostream>
#include <algorithm>
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用大于号(>)比较。

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1015 Safecracker》有2个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注