ACM蛮力(穷举)

蛮力搜索 蛮力搜索 就像宝剑不是撬棍一样 科学也很少使用蛮力 EdwardLytton 1803 1873 Leila 第二卷 第一章 蛮力搜索 定义 蛮力法 也叫穷举法 它要求设计者找出所有可能的方法 然后选择其中的一种方法 若该方法不可行则试探下一种可能的方法 蛮力搜索 定义 蛮力法是一种直接解决问题的方法 常常直接基于问题的描述和所涉及的概念定义 使用蛮力法的理由 显然蛮力法 也叫穷举法 不是一个最好的算法选择 但当我们想不出别的更好的办法时 它也是一种有效的解决问题的方法 蛮力法逻辑清晰 编写程序简洁 ACM程序设计时间紧张 使用高效的 巧妙的算法可能忽略掉一些解 而测试数据往往针对你可能忽略的情况 概述 穷举法的基本思想是不重复 不遗漏地穷举所有可能情况 问题的规模不是特别大 从中寻找满足条件的结果 穷举法充分利用了计算机处理的高速特性 避免复杂的逻辑推理过程 使问题简单化 使用穷举法的关键是要确定正确的穷举的范围和满足判断式 例1 百钱百鸡问题 公鸡5文钱1只 母鸡3文钱1只 小鸡一文钱3只 100文钱如何卖100只鸡 条件分析设买x只公鸡 y只母鸡 z只小鸡 则有 x y z 1005x 3y z 3 100且 x y z都是整数 0 x 20 0 y 33 0 z 99 z 3 0 基本算法思想 上述方程属于不定方程 解并不唯一 因此 可用穷举法对x y z的所有组合情况 测试满足条件的解 具体是 把x可能值0 20和y可能值0 33用二重循环来组合 每个x和y组合都可得到z值 即z 100 x y 若x y z值使5x 3y z 3 100成立 则该组x y z即为一组所求值 即 穷举范围 x 0 20 y 0 33 z 100 x y判断式 z 3 0 5 x 3 y z 3 100 另一方法是 把x可能值0 20 y可能值0 33和z可能值0 99用三重循环来组合 若x y z值使5x 3y z 3 100和x y z 100同时成立 则该组x y z即为一组所求值 即 穷举范围 x 0 20 y 0 33 z 0 99判断式 z 3 0 5 x 3 y z 3 100 x y z 100 main intx y z j 1 printf Possiblesolutionstobuy100fowlswhith100wen n for x 0 x 20 x for y 0 y 33 y z 100 x y if z 3 0 运行结果 Possiblesolutionstobuy100fowlswhith100wen 1 cock 0hen 25chicken 752 cock 4hen 18chicken 783 cock 8hen 11chicken 814 cock 12hen 4chicken 84 例2 打印出所有的 水仙花数 所谓 水仙花数 是指一个三位正整数 其各位数字的立方和等于该数本身 例如 153 13 53 33 穷举范围 即把所有的三位正整数100 999按题意一一进行判断 判断式 如果一个三位正整数n的百位 十位 个位上的数字分别为i j k 则判断式为 n i3 j3 k3 如何分解三位数n的百位 十位 个位 百位 i n 100 十位 j n 10 10 个位 k n 10 include stdio h main intn i j k for n 100 n 999 n i n 100 j n 10 10 k n 10 if n i i i j j j k k k printf d d 3 d 3 d 3 n n i j k 运行结果 153 1 3 5 3 3 3370 3 3 7 3 0 3371 3 3 7 3 1 3407 4 3 0 3 7 3 例3 中国余数定理 有物不知几何 三三数余一 五五数余二 七七数余三 问 物有几何 编程求1000以内所有解 穷举范围 整数m为 1 1000 判断式 m 3 1 m 5 2 m 7 3 include stdio h main intm count 0 for m 1 m 1000 m if m 3 1 运行结果 52157262367472577682787892997 常用的蛮力法 1 搜索所有的解空间 2 搜索所有的路径 3 直接进行计算 搜索所有的解空间 案例1 假金币案例2 现在的时间是多少 案例1 假金币 FalsecoinTimeLimit 3000MSMemoryLimit 10000K Description The GoldBar bankreceivedinformationfromreliablesourcesthatintheirlastgroupofNcoinsexactlyonecoinisfalseanddiffersinweightfromothercoins whileallothercoinsareequalinweight Aftertheeconomiccrisistheyhaveonlyasimplebalanceavailable likeoneinthepicture Usingthisbalance oneisabletodetermineiftheweightofobjectsintheleftpanislessthan greaterthan orequaltotheweightofobjectsintherightpan Inordertodetectthefalsecointhebankemployeesnumberedallcoinsbytheintegersfrom1toN thusassigningeachcoinauniqueintegeridentifier Afterthattheybegantoweightvariousgroupsofcoinsbyplacingequalnumbersofcoinsintheleftpanandintherightpan Theidentifiersofcoinsandtheresultsoftheweightingswerecarefullyrecorded Youaretowriteaprogramthatwillhelpthebankemployeestodeterminetheidentifierofthefalsecoinusingtheresultsoftheseweightings Input ThefirstlineoftheinputfilecontainstwointegersNandK separatedbyspaces whereNisthenumberofcoins 2 or Itrepresentstheresultoftheweighting meansthattheweightofcoinsintheleftpanisgreaterthantheweightofcoinsintherightpan meansthattheweightofcoinsintheleftpanisequaltotheweightofcoinsintherightpan Output Writetotheoutputfiletheidentifierofthefalsecoinor0 ifitcannotbefoundbytheresultsofthegivenweightings SampleInput 5321234 114 125 SampleOutput 3 假金币 时间限制 3000MS内存限制 10000K 描述 GoldBar 银行收到可靠消息 在前次的N个金币中有一枚重量不同的假金币 其他金币的重量都相同 经济危机之后他们只有一台天平可用 用这台天平 可以称量出左边托盘中的物体是轻于 重于或等于右边托盘中的物体 为了分辨出假金币 银行职员将所有的金币编为1到N号 然后用天平称量不同的金币组合 每次仔细记载称量金币的编号和结果 现在要求你编写一个程序 帮助银行职员根据称量记录来找出假金币的编号 输入 第一行输入两个空格隔开的整数N和K N是金币的总数 2 和记录称量结果 表示左边托盘中的金币比右边的重 表示左右两边托盘中的金币一样重 输出 输出假金币的编号 如果根据称量纪录无法确定假金币 输出0 输入样例 5321234 114 125 输出样例 3 解题思路 这个题可以用蛮力搜索来解决 从题目描述 数据的规模不大 而时间限制足够大 选择暴力搜索可以使程序设计简单 而且因为是完全搜索 所以不会出现漏掉解的情况 解题思路 续 思路很简单 把所有的金币都试一遍 Step1 依次假设I号金币是假的 Step2 对称量的记录进行监测 如果假设与所有的记录都不矛盾 则有可能是假的 Step3 如果有可能是假的金币只有1个 输出它的编号 否则 输出0 数据结构与算法 不需要特殊的数据结构 算法采用暴力搜索 核心代码及解释 shortjd intj int s charc 函数判断假设j号金币是假的与称量结果是否矛盾 s是称量记录 其第一个元素是砝码个数 c是称量结果 m s 0 1 for i f 1 i m 核心代码及解释 续 intmain intnum 100 1001 chars 1000 输入内容for i 1 t 0 i1 break no i t保存嫌疑对象的个数if t 1 printf 0 elseprintf d no 案例2 现在的时间是多少 Whattimeisit TimeLimit 1000MSMemoryLimit 10000K Description Anaccutronshowstimewithfourdigits from0000to2359 Everydigitisrepresentedby3 3characters including s sandblanks WhentheLCDscreenworkswell thedigitslooklikethefollowing Therearetwoaccutronsathand Oneshowstheaccuratetime andtheotheris15minuteslate Forexample at8 25am thefirstaccutronshows 0825 whilethesecondshows 0810 Unfortunately thereissomethingwrongwiththetwoLCDscreens namelysomepartsofthedigitsmissed Yourtaskistodecidetheaccuratetime accordingtothefragmentaldigitsshowedonthetwoaccutrons Input Thefirstlineoftheinputisasingleintegert 1 t 20 thenumberoftestcases Eachcasecontainsthreelines indicatingthetimeontheaccurateaccutronandthetimeontheslowaccutron separatedbyablankcolumn PleaserefertotheSampleInput Output Foreachinput printtheaccuratetimewithfourdigitsifitcanbeensured orotherwisethestring NotSure SampleInput 2 SampleOutput NotSure0825 现在的时间是多少 时间限制 1000MS内存限制 10000K 描述 电子钟用4位数字表示时间 从0000到2359 每位数字用一个3 3的字符 和空格 来表示 如果LCD显示屏正常工作 10个数字显示如下 现在有两个电子钟 一个显示正确的时间 另一个慢15分钟 如 上午8 25 第一个钟显示 0825 同时第二个显示 0810 不幸的 两个钟的LCD显示屏有些问题 也就是说 有些数字的某些部分缺失 你的任务就是通过显示的剩余部分来决定正确的时间 输入 第一行是一个整数t 1 t 20 表明测试序列数目 每个测试序列包含3行 表示正确的时间和迟后的时间 有一个空列隔开 参照输入样例 输出 如果能确定正确时间 输出该时间 否则输出 NotSure 输入样例 2 输出样例 NotSure0825 解题思路 这个题可以用蛮力搜索来解决 从题目描述 数据的规模不大 为什么 每天只有1440分钟 选择暴力搜索可以使程序设计简单 这题显示了暴力搜索的优势 解题思路 续 首先将LCD管进行编码 0 123 4560 1231 72 补码 0 51 55 将输入的内容进行编码 解题思路 续 检测某个时间是否是显示屏上的时间 只需要检测该时间与显示屏上显示的内容不冲突就可以了 如检测1时 0 1 2 4 5处就不应该有显示 如果有显示 意味显示的不可能是1 所以只需将输入的内容与对应的数字作 运算 结果非0意味不可能是该数字 数据结构与算法 不需要特殊的数据结构 算法采用暴力搜索 首先将输入的内容编码 对于全天的1440分钟 进行比对 如果只可能有一个时间 输出该时间 否则 notsure 核心代码及解释 voidstime intt int s 函数将时间t 分钟 转换为数字序列s inttt tt t 15 if tt 0 tt 1440 tt是晚15分钟s 3 t 10 s 2 t 10 6 s 1 t 60 10 s 0 t 600 s 7 tt 10 s 6 tt 10 6 s 5 tt 60 10 s 4 tt 600 如时间t 0 s 0 0 0 0 2 3 4 5 核心代码及解释 续 Intcode char s1 char s2 char s3 将读入3行数据的数据编码 intcod 0 i chars 10 Strcat s s1 strcat s s2 strcat s s3 For I 0 I 10 I if s I cod 1 I Returncod 核心代码及解释 续 shortnum 10 4 55 66 18 49 24 8 54 0 16 数字的补码intmain scanf d n 如果有且只有一个时间满足要求 输出该时间 搜索所有的路径 案例3 矩阵 案例3 矩阵 MatrixTimeLimit 2000MSMemoryLimit 30000K Description Givenann nmatrixA whoseentriesAi jareintegernumbers 0 i n 0 j n AnoperationSHIFTatrowi 0 i n willmovetheintegersintherowonepositionright andtherightmostintegerwillwraparoundtotheleftmostcolumn YoucandotheSHIFToperationatarbitraryrow andasmanytimesasyoulike Yourtaskistominimizemax0 j n Cj Cj 0 i nAi j Input Theinputconsistsofseveraltestcases Thefirstlineofeachtestcasecontainsanintegern Eachofthefollowingnlinescontainsnintegers indicatingthematrixA Theinputisterminatedbyasinglelinewithaninteger 1 Youmayassumethat1 n 7and Ai j 104 Output Foreachtestcase printalinecontainingtheminimumvalueofthemaximumofcolumnsums SampleInput 246373123456789 1 SampleOutput 1115 矩阵 时间限制 2000MS内存限制 30000K 描述 给定一个n n整数矩阵 定义对I行的SHIFT操作 0 i n 是将第I行所有元素都右移一位 最右边的移到最左边 你可以对任意行进行任意次SHIFT操作 使得 max0 j n Cj Cj 0 i nAi j 最小化 输入 第一行是一个整数t 1 t 20 表明测试序列数目 每个测试序列包含3行 表示正确的时间和迟后的时间 有一个空列隔开 参照输入样例 输出 输出最小值 输入样例 246373123456789 1 输出样例 1115 解题思路 这个题可以用蛮力搜索来解决 从题目描述 数据的规模不大 n 8 ACM程序设计竞赛时间紧张 没有充裕的时间构筑高效 巧妙的算法 解题思路 续 把所有可能的移动都移动一遍 找到最小值 数据结构与算法 不需要特殊的数据结构 算法采用暴力搜索 所有的可能情况都找出来 每一行都可能移0到n 1步 所以总的情况有nn种 对每种情况进行编号 如n 7时 7进制的0123456表示第一行不动 第二行移动一次 核心代码及解释 voidinttoseries inti int s 函数将序号化为移动的序列for k 0 j i k n 1 k s k j n j n 核心代码及解释 续 intmaxcolumn int s 函数返回在指定移动情况下的最大值 for max matrix