找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法专题(3)-枚举

admin 2019-6-13 05:32 165人围观 C++相关

点击上面微信号关注我

关注我哟
定期推送帐号信息学新闻,竞赛自主招生,信息学专业知识,信息学疑难解答,信息学训练营信息等诸多优质内容的微信平台,欢迎分享文章给你的朋友或者朋友圈!有任何问题请联系小编!

NOI2019 夏令营课程报名中!<点击查看




摘要

    之前我们已经发布过(点击标题即可查看):

算法专题(1)-信息学基本解题流程!

算法专题(2)-模拟

三、 枚举

概述:


所谓枚举,就是将所有的可能一一遍历出来,在遍历中逐个检查答案的正确性,从而确定最终结果。

1. 知识点梳理:


Ø 一般枚举方法

一般枚举方法将所有可能情况都列举出来,理论上几乎可以解决所有问题。但是枚举算法的复杂度很高,需考虑时限问题。

Ø 枚举算法的优化

由于枚举法产生了大量的无用解,所以规模稍大的时候要进行优化。其中一类优化被称作“二分枚举”,其思路跟分治法(在后面的章节会讲)类似。在进行二分枚举时,其问题必须满足单调性。举个例子,给定单调函数f(x),计算f(x)与x轴的交点(精确到3位小数)。那么,对于区间[L,R],只需枚举中点,即可确定其子区间,最后当区间足够小时,即可确定解。设g(L,R)为f函数在区间[L,R]中与x轴的交点的横坐标值。

此类二分枚举实用性很强。有些问题直接求解比较复杂,或者难以想到时,可尝试二分枚举答案。这些问题通常具有性质:其判定型问题(给定一个解,看是否可行)比较容易求解。

2.重难点分析:


u 枚举算法的时间开销一般较大,需要在算法设计时注意。

u 枚举不是万能的,不要盲目使用枚举法。

u 采用二分枚举时,需要保证所枚举的数据具有有序性。

u 在其他算法不满足时,可用枚举法获取部分分数。

3.例题解析:

例题3-1:火柴棒等式(NOIP 2008)


【问题简述】给你n (n≤24) 根火柴棍,你可以拼出多少个形如 “A+B=C” 的等式?等式中的A、B、C是用火柴棍拼出的整数(若该数非零,则最高位不能是0),数字的形状和电子表上的一样。

注意:

1. 加号与等号各自需要两根火柴棍。

2. 如果A≠B,则A+B=C与B+A=C仍为不同的等式(A,B,C≥0)。

3. n根火柴棍必须全部用上。

【分析】本题就是一个经典的枚举题。由于题目中火柴数n≤24,A、B、C最大为3位数。首先先初始化0~9需要多少根火柴,再初始化0~999需要多少根火柴(当然,其中有一些是不可行的),接下来,枚举A和B,计算C,判断可行性。最差情况下为106次枚举。

例题3-2:关押罪犯(NOIP2010)


【问题描述】S 城现有两座监狱,一共关押着N (N≤20000) 名罪犯,编号分别为1~N。他们之间的关系自然也极不和谐。很多罪犯之间甚至积怨已久,如果客观条件具备则随时可能爆发冲突。我们用“怨气值”(一个正整数值)来表示某两名罪犯之间的仇恨程度,怨气值越大,则这两名罪犯之间的积怨越多。如果两名怨气值为c 的罪犯被关押在同一监狱,他们俩之间会发生摩擦,并造成影响力为c 的冲突事件。冲突的数目为M (M≤100000)。

每年年末,警察局会将本年内监狱中的所有冲突事件按影响力从大到小排成一个列表,然后上报到S 城Z 市长那里。公务繁忙的Z 市长只会去看列表中的第一个事件的影响力,如果影响很坏,他就会考虑撤换警察局长。

在详细考察了N 名罪犯间的矛盾关系后,警察局长觉得压力巨大。他准备将罪犯们在两座监狱内重新分配,以求产生的冲突事件影响力都较小,从而保住自己的乌纱帽。假设只要处于同一监狱内的某两个罪犯间有仇恨,那么他们一定会在每年的某个时候发生摩擦。那么,应如何分配罪犯,才能使Z 市长看到的那个冲突事件的影响力最小?这个最小值是多少?

【分析】此题最优解法是用并查集,复杂度为O(M log M)。在此我们只讲次优的二分枚举解法。

假如所有的罪犯之间的冲突只有0和1,那么题目就会变得非常简单。冲突为1的罪犯之间连一条边,直接染色即可。按照这个思路,可二分枚举冲突事件的影响力,对于小于当前枚举的影响力的冲突,不连边;对于大于当前枚举的影响力的冲突,连边。然后进行染色。时间复杂度为O(N log max(c))。在二分枚举的过程中,也可先对冲突进行排序,再二分枚举。时间复杂度变为O(N log M + M log M)。

二分枚举在近几年的NOIP中也十分常见。像2010年的“关押罪犯”和“QC”,2011年的“借教室”和“疫情控制”均可用二分枚举答案求解。






往期精选内容

(点击标题即可查看)

NOI2019 夏令营课程报名中!

2019年NOI省队选拔规定及NOI2019名额分配方案发布!

信息学竞赛入选!2019年度面向中小学生全国性竞赛活动名单公示

关于举办第34届全国青少年科技创新大赛的通知

最详细解析低分进名校三大途径:自主招生、综合评价、高校专项计划!

2018年自主招生高校对信息学奖项报考要求及优惠政策参考!报考时要注意哪些问题?


2019年保送生资格名单公示

NOIP2018复赛提高组各省中学 获一等奖人数排行榜及分析!

NOIP2018复赛提高组各省各中学获奖总数排行榜

NOIP2018各省各中学复赛普及组获奖总数分析!

CCF NOI2019冬令营报到通知及冬令营名额分配方案!

再见,OI-大牛HZW亲笔,分享OI生涯记录,不变的是坚持和热爱!

NOIP复赛知识点简述及复赛算法总结!

重磅!NOIP2018初赛普及组提高组真题及答案发布

NOIP2018提高组试题解析


根据信息学竞赛之路带你了解信息学竞赛流程

清华“姚班”2018级名单-看50名学霸到底多牛,同学们又如何能进姚班?

全国自主招生高校对各项学科竞赛奖项要求大汇总!签约路径

教育部出台高中新课标,信息学竞赛相关内容被编入必修课程!


北京大学自主招生初审通过1719人名单公布,看清华北大更青睐哪些省市中学?

IOI 2018国际信息学奥林匹克竞赛中国代表队选拔结果揭晓,看大牛们的竞赛之路!
2018年五大学科竞赛国家队名单全部出炉,各省中学大比拼!

从搜狗CEO王小川(信息学金牌),看这二十几年中国奥赛金牌的去向

揭晓高薪专业排行榜,计算机专业薪资最高!哪些专业最具潜力?

2018中国大学排行榜出炉,北大清华连续11年蝉联冠亚军


一个清华保送生妈妈对竞赛的感受,自主招生家长都要看看!

计算机科学与技术专业全国大学排行榜!


为什么这些孩子初中就能被清华北大签约

2018五大学科竞赛国家集训队成员及所在学校名单


(1)为什么有“编程思维”和数学能力强的人更优秀?
(2)清北独家录制NOIP成功者说学习视频!!!

(3)我们为什么要对孩子进行编程教育?

(4)信息学竞赛答家长问题

1.信息学竞赛,你想了解的知识都在这里

2.信息学奥赛(NOIP)初赛学习方法推荐

3.信息学奥赛(NOIP)复赛学习方法推荐

4.大牛为你推荐十本最适合信息学竞赛的书籍

5.信息学奥赛有那么重要吗?

6.参加编程竞赛对实际工作的用处

7.清北学堂独家录制NOIP考试技巧讲座

8.在线编程挑战赛第一名:我是这么学算法的

9.信息学竞赛如何学习及准备攻略!

10.凭什么我得了信息学奥赛国家一等奖

11.榜样 | 北大降200分要这个诸暨天才少年

12.OI金牌教练胡芳:爱和成长的故事

13.信息学竞赛,一个让孩子不需要再去挤独木桥的方向

14.新学期必须了解的学科竞赛与自主招生时间!

15.北大录取生陈代超:在信息学中找到“思维图谱”

16.国务院发文支持编程教育进入中小学,中国人工智能厚积薄发

(1)NOIP报名,申诉,查成绩方式介绍

(2)NOIP复赛考前需要注意的那些事儿!!!

(3)NOIP测评环境,数据提交你都了解吗?请注意这些问题!

(4)关于NOI系列赛编程语言使用限制的规定



关注「信息学竞赛」

看更多信息学趣闻与知识

↓↓↓




----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:信息学竞赛,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......