华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 1080|回复: 2
打印 上一主题 下一主题

穷举法大楼

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-6-29 16:28: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








回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

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

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
板凳
 楼主| 发表于 2018-10-18 12:44:20 | 只看该作者
枚举的规律一般有如下几种:
1、顺序枚举
2、二进制枚举
3、子集枚举
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-26 03:34 , Processed in 0.157495 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表