WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
算法基础简介
枚举
模拟
递归 & 分治
贪心
排序简介
选择排序
冒泡排序
插入排序
计数排序
基数排序
快速排序
归并排序
堆排序
桶排序
希尔排序
锦标赛排序
排序相关 STL
排序应用
前缀和 & 差分
二分
倍增
22 objects
本站非官方,所收集资源均来源于网络。
枚举 - 算法基础
author: frank-xjh 本页面将简要介绍枚举算法。 ## 简介 枚举(英语:Enumerate)是基于已有知识来猜测答案的一种问题求解策略。 枚举的思想是不断地猜测,从可能的集合中一一尝试,然后再判断题目的条件是否成立。 ## 要点 ### 给出解空间 建立简洁的数学模型。 枚举的时候要想清楚:可能的情况是什么?要枚举哪些要素? ### 减少枚举的空间 枚举的范围是什么?是所有的内容都需要枚举吗? 在用枚举法解决问题的时候,一定要想清楚这两件事,否则会带来不必要的时间开销。 ### 选择合适的枚举顺序 根据题目判断。比如例题中要求的是最大的符合条件的素数,那自然是从大到小枚举比较合适。 ## 例题 以下是一个使用枚举解题与优化枚举范围的例子。 !!! 例题 一个数组中的数互不相同,求其中和为 $0$ 的数对的个数 ### "解题思路" > 枚举两个数的代码很容易就可以写出来。 > ```cpp for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) if (a[i] + a[j] == 0) ++ans; ``` 来看看枚举的范围如何优化。原问题的答案由两部分构成:两个数相等的情况和不相等的情况。相等的情况只需要枚举每一个数判断一下是否合法。至于不相等的情况,由于题中没要求数对是有序的,答案就是有序的情况的两倍(考虑如果 `(a, b)` 是答案,那么 `(b, a)` 也是答案)。对于这种情况,只需统计人为要求有顺序之后的答案,最后再乘上 $2$ 就好了。 不妨要求第一个数要出现在靠前的位置。代码如下: ```cpp for (int i = 0; i < n; ++i) for (int j = 0; j < i; ++j) if (a[i] + a[j] == 0) ++ans; ``` 不难发现这里已经减少了 $j$ 的枚举范围,减少了这段代码的时间开销。 然而这并不是最优的结果。 两个数是否都一定要枚举出来呢?枚举其中一个数之后,题目的条件已经确定了其他的要素(另一个数),如果能找到一种方法直接判断题目要求的那个数是否存在,就可以省掉枚举后一个数的时间了。 ```cpp // 要求 a 数组中的数的绝对值都小于 MAXN bool met[MAXN * 2]; // 初始化 met 数组为 0; memset(met, 0, sizeof(met)); for (int i = 0; i < n; ++i) { if (met[MAXN - a[i]]) ++ans; // 为了避免负数下标 met[a[i] + MAXN] = 1; } ``` ## 习题 - [2811: 熄灯问题 - OpenJudge](http://bailian.openjudge.cn/practice/2811/)