HDU1015Safecracker

HDU 暴力 回溯 DFS

题意&＃xff1a;

给temp赋一个值&＃xff0c;然后给出一个字符串&＃xff08;不会出现相同字母&＃xff0c;即字符串最长26&＃xff09;&＃xff0c;从中选出5个字母最为v,w,x,y,z(A&＃61;1, B&＃61;2, …, Z&＃61;26)使之满足等式v - w^2 &＃43; x^3 - y^4 &＃43; z^5 &＃61; target &＃xff0c;并输出由这5个字母组成字典序最大的字符串&＃xff0c;不存在输出no solution

样例输入输出&＃xff1a;

Sample Input&＃xff1a;

1 ABCDEFGHIJKL
11700519 ZAYEXIWOVU
3072997 SOUGHT
1234567 THEQUICKFROG
0 END


Sample Output&＃xff1a;

LKEBA
YOXUZ
GHOST
no solution


想法&＃xff1a;

• dfs深搜
• 最大数据&＃xff1a;26 * 25 * 24 * 23&＃xff0c;可以直接暴力5层循环

代码&＃xff1a;

DFS深搜&＃xff1a;(31ms)

//31ms
#include
using namespace std;
const int maxn &＃61; 1111;
char str[maxn],ch[maxn],max_ch[maxn];
int vis[11111];
int flag,temp,len;int cal(char a,char b,char c,char d,char e){int z,x,v,n,m;z&＃61;a-&＃39;A&＃39;&＃43;1;x&＃61;(b-&＃39;A&＃39;&＃43;1)*(b-&＃39;A&＃39;&＃43;1);v&＃61;(c-&＃39;A&＃39;&＃43;1)*(c-&＃39;A&＃39;&＃43;1)*(c-&＃39;A&＃39;&＃43;1);n&＃61;(d-&＃39;A&＃39;&＃43;1)*(d-&＃39;A&＃39;&＃43;1)*(d-&＃39;A&＃39;&＃43;1)*(d-&＃39;A&＃39;&＃43;1);m&＃61;(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1);if((z-x&＃43;v-n&＃43;m)&＃61;&＃61;temp) return 1;return 0;
}void dfs(int n){if(n&＃61;&＃61;5){if(cal(ch[0],ch[1],ch[2],ch[3],ch[4])&&strcmp(ch,max_ch)>0){strcpy(max_ch,ch);}}else{for(int i&＃61;0;i<len;i&＃43;&＃43;){//int m &＃61; str[i] - &＃39;A&＃39; &＃43; 1;if(vis[str[i]]&＃61;&＃61;0){ch[n] &＃61; str[i];vis[str[i]] &＃61; 1;//标记用过 dfs(n&＃43;1);vis[str[i]] &＃61; 0;}}}
}int main() {freopen("in.txt","r",stdin);while(scanf("%d%s",&temp,str)!&＃61;EOF&&(temp||strcmp(str,"END"))){memset(ch,&＃39;\0&＃39;,sizeof(ch));memset(max_ch,&＃39;\0&＃39;,sizeof(max_ch));memset(vis,0,sizeof(vis));len &＃61; strlen(str);sort(str,str&＃43;len);dfs(0);if(strlen(max_ch)!&＃61;0) printf("%s\n",max_ch);else printf("no solution\n");}return 0;
}


暴力5循环&＃xff1a;(46ms)

//46ms
#include
using namespace std;
const int maxn &＃61; 1111;
char str[maxn],ch[maxn],max_ch[maxn];
int flag,temp;int cal(char a,char b,char c,char d,char e){int z,x,v,n,m;z&＃61;a-&＃39;A&＃39;&＃43;1;x&＃61;(b-&＃39;A&＃39;&＃43;1)*(b-&＃39;A&＃39;&＃43;1);v&＃61;(c-&＃39;A&＃39;&＃43;1)*(c-&＃39;A&＃39;&＃43;1)*(c-&＃39;A&＃39;&＃43;1);n&＃61;(d-&＃39;A&＃39;&＃43;1)*(d-&＃39;A&＃39;&＃43;1)*(d-&＃39;A&＃39;&＃43;1)*(d-&＃39;A&＃39;&＃43;1);m&＃61;(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1)*(e-&＃39;A&＃39;&＃43;1);if((z-x&＃43;v-n&＃43;m)&＃61;&＃61;temp) return 1;return 0;
}int main() {freopen("in.txt","r",stdin);while(scanf("%d%s",&temp,str)!&＃61;EOF&&(temp||strcmp(str,"END"))){memset(max_ch,&＃39;\0&＃39;,sizeof(max_ch));memset(ch,&＃39;\0&＃39;,sizeof(ch));flag &＃61; 0;int len &＃61; strlen(str);for(int a&＃61;len-1;a>&＃61;0;a--){for(int b&＃61;len-1;b>&＃61;0;b--){if(a&＃61;&＃61;b) continue;for(int c&＃61;len-1;c>&＃61;0;c--){if(c&＃61;&＃61;b||c&＃61;&＃61;a)continue;for(int d&＃61;len-1;d>&＃61;0;d--){if(d&＃61;&＃61;a||d&＃61;&＃61;b||d&＃61;&＃61;c)continue;for(int e&＃61;len-1;e>&＃61;0;e--){if(e&＃61;&＃61;a||e&＃61;&＃61;b||e&＃61;&＃61;c||e&＃61;&＃61;d) continue;if(cal(str[a],str[b],str[c],str[d],str[e])){flag &＃61;1;ch[0]&＃61;str[a],ch[1]&＃61;str[b];ch[2]&＃61;str[c],ch[3]&＃61;str[d];ch[4]&＃61;str[e],ch[5]&＃61;&＃39;\0&＃39;;if(strcmp(ch,max_ch)>0)strcpy(max_ch,ch); } }}}}}if(flag) printf("%s\n",max_ch);else printf("no solution\n");}return 0;
}