九宫-深度搜索.ppt
《九宫-深度搜索.ppt》由会员分享,可在线阅读,更多相关《九宫-深度搜索.ppt(54页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、今天,今天,你 了吗?AC2023/3/71第一讲第一讲一招制敌之搜索题2023/3/72根据“信息学初学者之家”网站的统计,Ural(俄罗斯的Ural州立大学的简称,那里设立了一个UralOnlineProblemSet,并且支持OnlineJudge。)的题目类型大概呈如下的分布:搜索动态规划贪心构造图论约10%约15%约5%约5%约10%计算几何纯数学问题数据结构其它约5%约20%约5%约25%统计信息:统计信息:2023/3/73搜索题特点分析搜索题特点分析:l题意容易理解题意容易理解l算法相对固定算法相对固定l编程有路可循编程有路可循l竞赛必备知识竞赛必备知识2023/3/74摘自摘
2、自ACMACM竞赛之新人向导竞赛之新人向导“算法中最基本和常用最基本和常用的是搜索,主要是回溯和分支限界法的使用。这里要说的是,有些初学者在学习这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。”引言引言2023/3/75什么是搜索算法呢?搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件
3、和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。2023/3/76举例分析举例分析从简单的字符串搜索讲起2023/3/77HDOJ_1238 SubstringslYou are given a number of case-sensitive strings of alphabetic characters,find the largest string X,such that either X,or its inverse can be found as a substring of any of the given strings.InputlThe first line of
4、the input file contains a single integer t(1=t=10),the number of test cases,followed by the input data for each test case.The first line of each test case contains a single integer n(1=n 4and0a/b1.Youshouldfindthepairofprimenumbersp,qsuchthatpq=manda/b=p/q=1,andfurthermore,theproductpqtakesthemaximu
5、mvalueamongsuchpairsoftwoprimenumbers.Youshouldreportpandqasthemostsuitablewidthandheightofthetranslatedpicture.2023/3/713lInputlTheinputisasequenceofatmost2000tripletsofpositiveintegers,delimitedbyaspacecharacterinbetween.Eachlinecontainsasingletriplet.Thesequenceisfollowedbyatripletofzeros,000,whi
6、chindicatedtheendoftheinputandshouldnotbetreatedasdatatobeprocessed.Theintegersofeachinputtripletaretheintegerm,thenumeratora,andthedenominatorbdescribedabove,inthisorder.Youmayassume4m=100000and1=a=b=1000.llOutputlTheoutputisasequenceofpairsofpositiveintegers.Thei-thoutputpaircorrespondstothei-thin
7、puttriplet.Theintegersofeachoutputpairarethewidthpandtheheightqdescribedabove,inthisorder.Eachoutputlinecontainsasinglepair.Aspacecharacterisputbetweentheintegersasadelimiter.Noothercharactersshouldappearintheoutput.2023/3/714lSample Input5129999999999916805161970112002411000lSample Output2231331323
8、73434337532023/3/715获取有用信息获取有用信息a.给定整数m,a,b(4m=100000and1=a=b=1000)b.需要找到两个数(不妨设为p,q)满足以下条件:lp,q均为质数;lp*q=m;la/b=p/q=1;c.输出所有满足以上条件的p,q中乘积最大的一对p,q(最大的p和最小的q,应该是相邻的两个质数)2023/3/716算法分析算法分析1.典型的搜索从所有可能的p,q中寻找满足条件的一对2.p,q的要求p,q均为质数,且p=q=100000;3.按上述思想流程应为a.从1100000中搜出质数b.两层循环,试遍所有的组合(p,q可能相等)c.每种组合去判断是否
9、符合条件,如是,将p*q与当前最大值比较,判断,保存2023/3/717面临的问题:面临的问题:超时!从1100000的质数运算约为1e+8,而这只是准备工作。因此,如不加以分析简化此题无法在规定时间内出解2023/3/718深入分析深入分析考虑大于10000的某个质数,不妨设为Q,另一个质数为P,则:l如果P10,P/Q10,P*Q100000而考虑到a,b的取值范围(1=a=b=1000)可知min(a/b)=0.001同时,要求:p*q=m=0;i-)for(j=i;jm|aj*aim|(double)ai/aj)s)2023/3/720真正的搜索题真正的搜索题迷宫搜索迷宫搜索2023/
10、3/721预备知识预备知识树的遍历树的遍历树的遍历主要有如下四种方法:1.先根/序遍历2.中根/序遍历3.后根/序遍历4.层次遍历分别有什么特点呢?分别有什么特点呢?2023/3/722(1)先根遍历对树的访问次序是:1.先访问根结点2.再访问左子树3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下:示例如下:2023/3/723以上二叉树的先根遍历序列是:?21357461、2、4、5、3、6、72023/3/724(2)中根遍历对树的访问次序是:1.先访问左子树2.再访问根结点3.最后访问右子树4.对于左右子树的访问也要满足以上规则示例如下:示例如下:2023/3/725以上
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 九宫 深度 搜索
限制150内