热门标签 | 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;
}


推荐阅读
  • 题目描述:给定n个半开区间[a, b),要求使用两个互不重叠的记录器,求最多可以记录多少个区间。解决方案采用贪心算法,通过排序和遍历实现最优解。 ... [详细]
  • UNP 第9章:主机名与地址转换
    本章探讨了用于在主机名和数值地址之间进行转换的函数,如gethostbyname和gethostbyaddr。此外,还介绍了getservbyname和getservbyport函数,用于在服务器名和端口号之间进行转换。 ... [详细]
  • 题目Link题目学习link1题目学习link2题目学习link3%%%受益匪浅!-----&# ... [详细]
  • 文件描述符、文件句柄与打开文件之间的关联解析
    本文详细探讨了文件描述符、文件句柄和打开文件之间的关系,通过具体示例解释了它们在操作系统中的作用及其相互影响。 ... [详细]
  • 本文详细介绍了C语言中链表的两种动态创建方法——头插法和尾插法,包括具体的实现代码和运行示例。通过这些内容,读者可以更好地理解和掌握链表的基本操作。 ... [详细]
  • 本文详细探讨了VxWorks操作系统中双向链表和环形缓冲区的实现原理及使用方法,通过具体示例代码加深理解。 ... [详细]
  • 本教程涵盖OpenGL基础操作及直线光栅化技术,包括点的绘制、简单图形绘制、直线绘制以及DDA和中点画线算法。通过逐步实践,帮助读者掌握OpenGL的基本使用方法。 ... [详细]
  • 本文介绍如何使用Objective-C结合dispatch库进行并发编程,以提高素数计数任务的效率。通过对比纯C代码与引入并发机制后的代码,展示dispatch库的强大功能。 ... [详细]
  • 前言--页数多了以后需要指定到某一页(只做了功能,样式没有细调)html ... [详细]
  • C++: 实现基于类的四面体体积计算
    本文介绍如何使用C++编程语言,通过定义类和方法来计算由四个三维坐标点构成的四面体体积。文中详细解释了四面体体积的数学公式,并提供了两种不同的实现方式。 ... [详细]
  • 本文探讨了如何在模运算下高效计算组合数C(n, m),并详细介绍了乘法逆元的应用。通过扩展欧几里得算法求解乘法逆元,从而实现除法取余的计算。 ... [详细]
  • 扫描线三巨头 hdu1928hdu 1255  hdu 1542 [POJ 1151]
    学习链接:http:blog.csdn.netlwt36articledetails48908031学习扫描线主要学习的是一种扫描的思想,后期可以求解很 ... [详细]
  • 本文探讨了如何在给定整数N的情况下,找到两个不同的整数a和b,使得它们的和最大,并且满足特定的数学条件。 ... [详细]
  • 从 .NET 转 Java 的自学之路:IO 流基础篇
    本文详细介绍了 Java 中的 IO 流,包括字节流和字符流的基本概念及其操作方式。探讨了如何处理不同类型的文件数据,并结合编码机制确保字符数据的正确读写。同时,文中还涵盖了装饰设计模式的应用,以及多种常见的 IO 操作实例。 ... [详细]
  • 本实验主要探讨了二叉排序树(BST)的基本操作,包括创建、查找和删除节点。通过具体实例和代码实现,详细介绍了如何使用递归和非递归方法进行关键字查找,并展示了删除特定节点后的树结构变化。 ... [详细]
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社区 版权所有