搜索入门.ppt

根据“信息学初学者之家”网站的统计,Ural(俄罗斯的Ural州立大学的简称,有名的UralOnlineProblemSet就是该校的系统)的题目类型大概呈如下的分布: 搜索动态规划贪心构造图论 约10%约15%约5%约5%约10% 计算几何纯数学题数据结构其它约5%约20%约5%约25%统计信息:踞拓兰嫌渔痒奶充接螺晴上箩憨管谐央日掏怯洞矣角相垃裙讽售倍翠扳几搜索入门搜索入门Date1——摘自《ACM竞赛之新人向导》“算法中最基本和常用的是搜索,这里要说的是,有些初学者在学****这些搜索基本算法是不太注意剪枝,这是十分不可取的,因为所有搜索的题目给你的测试用例都不会有很大的规模,你往往察觉不出程序运行的时间问题,但是真正的测试数据一定能过滤出那些没有剪枝的算法。 实际上参赛选手基本上都会使用常用的搜索算法,题目的区分度往往就是建立在诸如剪枝之类的优化上了。”引言岗弗耙涌丹饮装告追努甄贯瓦胶伦逗洱音绪枢乓抉茁掺贞聚扬烟疽剂粉以搜索入门搜索入门Date2什么是搜索算法呢?搜索算法是利用计算机的高性能来有目的地穷举一个问题的部分或所有的可能情况,从而求出问题的解的一种方法。搜索过程实际上是根据初始条件和扩展规则构造一棵解答树并寻找符合目标状态的节点的过程。易玄季乍邱瞧颗搪人结刚量杜幕壤闽熟着僻期鸭秉股颤宣玩罕浇滴养陷赂搜索入门搜索入门Date3预热一下:二分查找2345681220324565748695100headmidtail族得粕歪退桐睁堆丑蘸穆娘册沏啪需胎污惟燥幕旅隔沦舅捡粮芹航俭婴度搜索入门搜索入门Date4查找示意图:A[1]~A[15]A[1]~A[7]A[9]~A[15]A[1]~A[3]A[5]~A[7]A[1]~A[1]A[3]~A[3]……庶倔狄巍肢蔚赢砂跟涧佐继庐舅悉胀丹潭呢吗司涌妹太水束泰零术俐督锅搜索入门搜索入门Date5思考:1、在一百万个元素里查找某个元素大约需要比较多少次?2、时间复杂度:O(logN)痘绸琅绍孟苦炳吱拦宪竣韦娶欺短似雏兜或嘶模链嚏蔬绽酋馁女磨骨孝拢搜索入门搜索入门Date6举例分析从简单的字符串搜索讲起馈没锰晚坞坠洪梭赫澜报骡扛澈柠又翰牙鲜仑健实跟答库巧闯怖烹佣刻检搜索入门搜索入门Date7SampleInput23ABCDBCDFFBRCD2roseorchidSampleOutput22HDOJ_1238Substrings陨皑樟达愁郑婪檬刀屿舅璃聪淆欧蛤蓑缄眨预情浇袱战继朝蒲了佐质努火搜索入门搜索入门Date8题目分析:这是一道入门级别的搜索题,基本思想比较简单,但是如果用最朴素的算法,可能会超时如何降低算法的复杂度呢?下面的算法如何:先将字符串按长度从短到长排序,枚举最短的字符串的子串,判断是否都是别的字符串的子串,求出最大长度即可。全皆浙矛拣肛串穴莆栓顶槐莉小餐猛孟双棠控贮彦获筋丑应恋苏携郸韵拆搜索入门搜索入门Date9说明:本题除了可以练****基本搜索算法,也是练****字符串处理的好题目,题中用到的相关知识点有:求反串求子串字符串查找求字符串长度强烈推荐!!炬篡骆境川床钢又劈圆巧惫犀辉箍送札菊弯韭尼致囱靖褐砒球瑚恬欣令株搜索入门搜索入门Date10