华师一附中OI组

标题: 穷举法大楼 [打印本页]

作者: admin 时间: 2018-6-29 16:28
标题: 穷举法大楼
穷举法是一种很容易想到的算法，就是将是有的可能一一列举，判断是否符合条件，它不需要DFS BFS这样的复杂控制算法，只需要列举，比较就行了，但是要想学好它，也不容易，计算功底，逻辑思维要很好才行。
第一类：水仙花数，没什么技巧，也基本上无法优化，就是列举所有的可能，判断是否符合条件。
第二类：百鸡问题，勾股数等，这里有个重要的优化就是某个参数不需要穷举，他可以根据前面的几个参数计算出来！这样减少循环的次数。第三类：回文日期，aabb的完全平方数等，按照某个规律生成数据然后按照另外一个规律判断，否则穷举量太大。

此类题有两个重点，一个是枚举的规律，第二是判断的准则。

1、P1008 三连击 http://hsyit.cn/forum.php?mod=viewthread&tid=36107
2、P1618 三连击（升级版）  http://hsyit.cn/forum.php?mod=viewthread&tid=35962
3、P1420 最长连号 http://hsyit.cn/forum.php?mod=viewthread&tid=36281
4、P1567 统计天数  http://hsyit.cn/forum.php?mod=viewthread&tid=36165
5、P1317 低洼地 http://hsyit.cn/forum.php?mod=viewthread&tid=36162
6、P2670 扫雷游戏 http://hsyit.cn/forum.php?mod=viewthread&tid=35817
7、P2356 弹球游戏  http://hsyit.cn/forum.php?mod=viewthread&tid=36425
8、P1149 火柴棒等式 http://hsyit.cn/forum.php?mod=viewthread&tid=35959
9、P1988 火炬  http://hsyit.cn/forum.php?mod=viewthread&tid=35888

有点难度的题目：
1、USACO 时钟  http://www.hsyit.cn/forum.php?mod=viewthread&tid=36156
2、P2044 打开所有的灯  http://www.hsyit.cn/forum.php?mod=viewthread&tid=35994
3、UVA253 cube  http://www.hsyit.cn/forum.php?mod=viewthread&tid=3702
4、P2010 回文日期 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36157
5、P1212 铺放矩形块 http://www.hsyit.cn/forum.php?mod=viewthread&tid=36158
6、P1217 [USACO1.5]回文质数 Prime Palindromes  http://hsyit.cn/forum.php?mod=viewthread&tid=35960
7、P1112 波浪数 http://hsyit.cn/forum.php?mod=viewthread&tid=36349

作者: admin 时间: 2018-10-16 15:39
枚举的题目有两个重要的考虑点
1、状态如何表示，
2、相互的约束关系
比如NOIP2016回文日期，要是枚举所有的八位数，判断是否合法的日期，然后判断是否回文，那么最大数据绝对会超时，所以改变枚举的状态，可以考虑枚举年份，颠倒此年份接在后面生成一个回文数，然后判断是否日期。这样状态就大大减少了。

作者: admin 时间: 2018-10-18 12:44
枚举的规律一般有如下几种：
1、顺序枚举
2、二进制枚举
3、子集枚举

欢迎光临华师一附中OI组 (http://hsyit.cn/)