热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

HDU1015Safecracker

原题目链接:HDU1015分类:HDU暴力回溯DFS题意:给temp赋一个值,然后给出一个字符串(不会出现

原题目链接:HDU1015




分类:

HDU 暴力 回溯 DFS



题意:

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



样例输入输出:

Sample Input:

1 ABCDEFGHIJKL
11700519 ZAYEXIWOVU
3072997 SOUGHT
1234567 THEQUICKFROG
0 END

Sample Output:

LKEBA
YOXUZ
GHOST
no solution



想法:


  • dfs深搜
  • 最大数据:26 * 25 * 24 * 23,可以直接暴力5层循环



代码:

DFS深搜:(31ms)

//31ms
#include
using namespace std;
const int maxn = 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=a-'A'+1;x=(b-'A'+1)*(b-'A'+1);v=(c-'A'+1)*(c-'A'+1)*(c-'A'+1);n=(d-'A'+1)*(d-'A'+1)*(d-'A'+1)*(d-'A'+1);m=(e-'A'+1)*(e-'A'+1)*(e-'A'+1)*(e-'A'+1)*(e-'A'+1);if((z-x+v-n+m)==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;
}


推荐阅读
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本文详细探讨了KMP算法中next数组的构建及其应用,重点分析了未改良和改良后的next数组在字符串匹配中的作用。通过具体实例和代码实现,帮助读者更好地理解KMP算法的核心原理。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • Splay Tree 区间操作优化
    本文详细介绍了使用Splay Tree进行区间操作的实现方法,包括插入、删除、修改、翻转和求和等操作。通过这些操作,可以高效地处理动态序列问题,并且代码实现具有一定的挑战性,有助于编程能力的提升。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 本文深入探讨 MyBatis 中动态 SQL 的使用方法,包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]
  • 在前两篇文章中,我们探讨了 ControllerDescriptor 和 ActionDescriptor 这两个描述对象,分别对应控制器和操作方法。本文将基于 MVC3 源码进一步分析 ParameterDescriptor,即用于描述 Action 方法参数的对象,并详细介绍其工作原理。 ... [详细]
author-avatar
mobiledu2502861463
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有