关键词：

枚举

什么是枚举

枚举算法是一种经典的暴力算法，是通过遍历所有候选答案以找到正确的解的问题解决策略；

枚举的基本框架

1.给出解空间

建立数学模型，确立候选答案的范围，从数学的角度说：就是给出可能解的集合

这是最关键的一步，确立正确的解空间是应用枚举算法的前提

2.找到枚举的具体方法

在确立了正确的解空间后，还要知道怎么枚举才能找到正确的答案。

对于不同的问题，枚举的具体方法很可能是不同的。

枚举的种类

1.循环枚举

通过数层循环来达到穷举解空间里的解，找到正确的答案，是最基本的枚举算法

例：

求小于 N 的最大素数

纯暴力：

    int n,i,j;
    scanf("%d",&n);
    for(i=n-1;i>=2;i--)
    
        for(j=2;j<=i-1;j++)
        if(i%j==0) break;
        if(j==i) printf("%d",i);break;
    
    

优化版

    int n,i,j;
    scanf("%d",&n);
    for(i=n-1;i>=2;i--)
    
        for(j=2;j*j<=i;j++)
        if(i%j==0) break;
        if(j*j>i) printf("%d",i);break;
    

2.子集枚举

解决可化归为集合的子集问题的题目；

原理分析：

当题目中出现的数据体现出子集的性质后，我们将子集中的中出现的元素用(1)代替，补集中的元素用(0)代替；

举个栗子：给定一个集合(A1,2,3,4,5),其中子集(A_11,3,4,5),(A_21,4,5),(A_33),(A_42,3)就可以这样表示

A中元素	1(*^(1))	2	3	4	5	二进制(*^(2))	十进制
在(A_1)中的情况	1	0	1	1	1	11101	29
在(A_2)中的情况	1	0	0	1	1	11001	25
在(A_3)中的情况	0	0	1	0	0	00100	4
在(A_4)中的情况	0	1	1	0	0	00110	6

(*^(1))其实集合是有无序性的,但是按顺序来“编码”,不会破坏一般性；

(*^(2))这里的“编码”规则是，二进制第(n)位与(array[n])对应，尽管顺序相反程序也会“不重复”，“不遗漏”遍历解答树，但是会破坏二进制原有的顺序。

集合与二进制：

1.并集：

从元素选择角度，(A_2)和(A_3)包含的元素合并起来就能得到(A_1)。而分析(A_1)的二进制值就是(A_2)(和A_3)的二进制，对应的每一位都按(Or)运算计算就得到的——这不就是C++中的按位或运算吗？即(A_1=A_2cupA_3)等价于(a_1=a_2|a_3)。

2.交集：

交集就是两个集合共有的元素组成的。在逻辑上交集上就含有"与"的意思。类比并集，求交集就等价于按位与运算，(A_1=A_2capA_3iffa_1=a_2&a_3)。

3.包含：

集合(A_2)的元素都在(A_1)中出现，说明(A_1)包含(A_2)。而在高中阶段我们知A_1道了，若(A_2subsetA_1)，则有(A_1cupA_2=A_1)以及(A_1capA_2=A_2)，所以判断(A_2是否subsetA_1)，可以构造表达式((a_1|a_2==a_1)&&(a_1&a_2==a_2))，值为真，命题成立。

4.属于：

属于是指某个元素是否在集合内，可以看作包含的特殊情况——只需检查单独某项元素构成的集合是否是另一个集合的子集，则先用左移位运算构造出只有某一个元素的集合，然后和原集合取交，如果是空集则命题为真，在这个例子里，如果要判断第三个元素是否属于(A_1),就可以构造表达式(1<<(3-1)&a_1),表达式值为真，则命题为真。

5.补集：

补集是指全集去除某个集合后剩下的元素组成的集合。由上启发，我们可以使用按位异或运算来表示一个集合对于全集的补集，在这个例子里(A_2)的补集(A_3=AoplusA_2),即(a_3=a)^(a_2)。而根据二进制的运算规则也可以这么计算(a_3=a-a_2)。

总结：1.从上可以发现二进制和集合的密切关系。2.但是如果要用二进制来模拟集合运算，一定要确定一个全集，在子集间做运算，而全集一般可以从题目中提炼出。

例:

已知 (n)个整数 (x_1,x_2,…,x_n)，以及1个整数(k(k<n))。从(n)个整数中任选(k)个整数相加，可分别得到一系列的和。例如当 (n=4,k=3)，4个整数分别为(3,7,12,19)时，可得全部的组合与它们的和为：
[ 3+7+12=223+7+19=297+12+19=383+12+19=34\]
现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：(3+7+19=29。)

#include <iostream>
#include <cstdio>
#include <cmath>//pow函数的所属头文件
using namespace std;
typedef long long LL;
const int N = 1000001;
int sum2[N],ans2=0;
LL powme(LL sum)
    LL res=1,a=2;
    while(sum>0)
        if(sum&1)
        res*=a;a*=a;
        sum>>=1;
    
    return res;
//手打的快速幂，这段代码其实可以直接用pow(2,n)或(1<<n)代替;
bool pd(int sum)
    if(sum==1) return 0;
    if(sum==2) return 1;
    int i,s=sqrt(double(sum));
    for(i=2;i<=s;i++)
        if(sum%i==0) break;
    
    if(i>s) return 1;
    else return 0;
//判断是否为素数函数
void tobarr (int n,int k)
    for(int i=1;i<=powme(n)-1;i++)
        int b=i,m=1,ans=0,f=0;
        while(b>0)
            if(b&1) ans+=sum2[m];f++;//转换进制的同时,计算和,并且统计子集中的数有几个
            b>>=1;m++;
        
        if(f==k&&pd(ans)) ans2++;
    

int main()
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    scanf("%d",&sum2[i]);
    tobarr(n,k);
    printf("%d",ans2);
    return 0;

例2：

排列与组合是常用的数学方法，其中组合就是从(n)个元素中抽出(r)个元素(不分顺序且(r ≤n))，我们可以简单地将(n)个元素理解为自然数(1,2,…,n)从中任取(r)个数。

现要求你输出所有组合。

例如(n=5,r=3),所有组合为：

(123,124,125,134,135,145,234,235,245,345)

分析：

这种题目背景我称之为全组合问题，这一题的难点就是字典序输出，

比如，从(0)枚举到(2^5-1)的二进制，有三个(1)的二进制所对应的组合按照出现顺序，则是如下：

(1 2 3,1 2 4,1 3 4,2 3 4,1 2 5,1 3 5,2 3 5,1 4 5,2 4 5,3 4 5)

并没有按照字典序。

但将样例数据和样例答案的二进制分别列举出来：

(00111，01011，01101，01110，10011，10101，10110，11001，11010，11100)

(00111，01011，10011，01101，10101，11001，01110，10110，11010，11100)

就惊喜地发现这两组数刚好左右对称相反。而要将上面的数变为下面的数可以分两步进行：

1.将二进制从小到大枚举变为从大到小枚举。

2.将每个二进制都左右对称翻转。

//翻译成代码则如下
   for(int S=(1<<n)-1;S>=0;S--)//二进制从大到小枚举
   
    int cnt = 0;
    for(int i=n-1;i>=0;i--)//顺序点1
        if(S & (1<<i))
            a[cnt++]=n-i;//顺序点2
    if(cnt==r)
    
        for(int i=0;i<r;i++)//顺序点3
            printf("%3d",a[i]);
        puts("");
    
  

*而这到题的程序实现也很有趣，根据顺序点的不同组合会出现(6)种实现。

时间复杂度 (O(2^n))，很大，已经不属于多项式复杂度了，(1)秒的(timelimit)，(n)的范围大概 (20 - 30)。

3.排列枚举

在这里只介绍STL的简便方法，使用algorithm标准库中的内建函数 next_permutation(start,end) ，它可以生成在([start,end))内存的数组中产生严格的下一个字典序排列,并返回true，如果没有下一个排列，就返回 flase。

例

题目描述：

将 (1, 2,ldots ,9) 共 (9) 个数分成三组，分别组成三个三位数，且使这三个三位数的比例是 (A:B:C)，试求出所有满足条件的三个三位数，若无解，输出 No!!!。

分析：循环next_permutation(start,end)，直至生成 (1-9) 的全排列，每次构造数的时候，将排列切割成三段就行。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

typedef long long LL;
int a[10];

int main()
    for(int i=1;i<=9;i++)
        a[i] = i;
    LL A,B,C,x,y,z,cnt=0;
    scanf("%lld%lld%lld",&A,&B,&C);
    do
        x = a[1]*100 + a[2]*10 + a[3];
        y = a[4]*100 + a[5]*10 + a[6];
        z = a[7]*100 + a[8]*10 + a[9];
        if (x*B == y*A && y*C == z*B) printf("%lld %lld %lld
",x,y,z),cnt++;
    while (next_permutation(a+1,a+10));
    if(!cnt) puts("No!!!");
    return 0;

时间复杂度：是(O(n!))，比(O(2^n))更大，在(1)秒的(timelimit)下，n的范围大概是(11)以下。

枚举的优化

例1:

一个数组中的数互不相同，求其中和为(0)的有序数对的个数

1.纯暴力：

  int n,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&sum[i]);
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(sum[i]+sum[j]==0 && i!=j) ans++;
    printf("%d",ans);

2.优化一：

在算法一中中用(for(i))和(for(j))枚举了数对,如果数据中有((a_i,a_j))符合答案，那么((a_j,a_i))也是答案，总答案个数就是((a_i,a_j))个数的两倍，所以在枚举的过程中只要确定((a_i,a_j))的个数，乘2就行了,

    int i,j,n,ans=0;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&sum[i]);
    for(i=1;i<=n;i++)
    for(j=i+1;j<=n;j++)//j>i,确保(sum[i],sum[j])是正序的
       if(sum[i]+sum[j]==0)
       ans++;
    printf("%d",ans*2);

3.优化二

再进一步挖解题目内部的条件，可以继续优化：

1.题目中说互不相同的数相加为零，那么只有可能为互为相反数了。

2.根据1的推断，进一步的就是想到用桶来标记：

先是想到如果sum出现，那么就将a[-sum]标记上。当-sum出现时，判定a[-sum],发现-sum有配对，那么计数器就可以加1了。

但是C++中数组不能有负数下标，那么就将桶的大小扩大为a[MAXN*2]（MAXN为数的绝对值上界），那么原来的0就映射为MAXN。

程序实现就如下：

bool a[MAXN*2]//乘2是为了避免负数下标
memset(a,0,sizeof(a));    
    for(int i=1;i<=n;i++)
    
        if(a[MAXN+sum[i]]) ans++;
        a[MAXN-sum[i]]=1;
    

方法的核心原理就是利用问题的对称性，使用标记的方法，减少了不必要的枚举。

例2：

给定(N)个整数的序列，(A_1,A_2,A_3,A_4,···),求函数(Maxf(i,j)=Max(0,sum_k=i^ja_k))

1.简单暴力法：

    int i,j,k,MAXsum=-9999999,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(i=1;i<=n;++i)
    for(j=i;j<=n;++j)
    int Thissum=0;
    for(k=i;k<=j;k++)
    Thissum+=a[k];
    if(MAXsum<Thissum) MAXsum=Thissum;
    
    printf("%d",MAXsum);

2.优化一：

在这里，我们可以发现原算法的第二重循环的下面，用了一重循环计算(f(i,j)=sum_k=i^ja_k)，但其实计算序列是同一个的，那么当(i)都是一样的话，(f(i,j)=f(i,j-1)+a_j,f(i,j-1))的部分就不用重复计算了，直接用上一层循环的结果加上(a_j)就行，可以自己举个栗子看看。

    int i,j,k,Thissum=0,MAXsum=-9999999,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(i=1;i<=n;++i)
    Thissum=0;
    for(j=i;j<=n;++j)
        Thissum+=a[j];
        if(MAXsum<Thissum) MAXsum=Thissum;
    
    
    printf("%d",MAXsum);

这种算法的核心其实是一维前缀和，更常见形式是

    int i,j,MAXsum=-9999999,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    scanf("%d",&a[i]);per[i]=per[i-1]+a[i];
    for(i=1;i<=n;++i)
    for(j=i;j<=n;++j)
        if(MAXsum<per[j]-per[i-1]) MAXsum=per[j]-per[i-1];
    
    printf("%d",MAXsum);

这两者“看上去”大不相同，但其是仔细一想关键之处是一样的。

一维前缀和就是预处理，将一部分原来枚举循环中重复的操作提到循环外面来，减少枚举量，达到优化效果。

3.其实更优秀的算法的时间复杂度(O(nlogn))算法(3)的核心思想是分而治之，即分治法,在分治法章节会详细讲解这个例子。

枚举总结

我们常说的枚举指的是枚举算法，但是算法体现的思想，更加影响深远。

有很多算法本质上其实就是枚举的思想，或者是在枚举的基础上通过改进演变出来。

而很多解题策略也将枚举作为基本的操作出现。

《算法零基础》第10讲：因子分解和枚举（部分）(代码片段)

前言原文章出处专栏为：算法零基础100讲若你也想学好算法与数据结构，请跟着他的脚步:英雄哪里出来目录前言LeetCode1492.n的第k个因子分析代码LeetCode1362.最接近的因数分析代码LeetCode1492.n的第k个因子原题链接：1492.n... 查看详情

《算法零基础》第18讲：线性枚举-统计法入门(代码片段)

前言原文章：线性枚举(二)-统计法入门目录前言概念LeetCode1295.统计位数为偶数的数字代码540.有序数组中的单一元素分析方法1方法二剑指Offer21.调整数组顺序使奇数位于偶数前面方法1：首尾双指针方法2：快慢指针1991.... 查看详情

noip基础算法（未完成）(代码片段)

...小的相似问题。 补充nextpermutation/prevpermutation(全排列算法)STL提供了两个用来计算 查看详情

题解《算法零基础100讲》(第17讲)线性枚举-最值算法（java版）(代码片段)

😁算法小白欢迎加入此社区：https://bbs.csdn.net/forums/hero?category=0由英雄大佬带领的抱团学算法队伍，从0开始，期待你的加入🥳本博文是对此文章习题所作的题解，如有不足，请多指教：https://blog... 查看详情

题解《算法零基础100讲》(第10讲)因子分解和枚举（java版）(代码片段)

😁算法小白欢迎加入此社区：https://bbs.csdn.net/forums/hero?category=0由英雄大佬带领的抱团学算法队伍，从0开始，期待你的加入🥳本博文是对此文章习题所作的题解，如有不足，请多指教：https://blog... 查看详情

题解《算法零基础100讲》(第18讲)线性枚举-统计法入门（java版）(代码片段)

😁算法小白欢迎加入此社区：https://bbs.csdn.net/forums/hero?category=0由英雄大佬带领的抱团学算法队伍，从0开始，期待你的加入🥳本博文是对此文章习题所作的题解，如有不足，请多指教：https://blog... 查看详情

⭐算法入门⭐《线性枚举》简单09——leetcode66.加一(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述  给定一个由整数组成的非空数组所表示的非负整数，在该数的... 查看详情

算法基础模板整理（基础搜索篇）(代码片段)

递归实现枚举递归实现指数型枚举void dfs(int k)    if(k > n)         for(auto &x : res) cout << x << \' \';     &... 查看详情

⭐算法入门⭐《二分枚举》中等03——leetcode1539.第k个缺失的正整数(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述  给你一个严格升序排列的正整数数组arr和一个整数kkk。请你找到... 查看详情

基础算法（数据结构笔试复测leecode牛客）(代码片段)

基础算法查找二分查找递归枚举分治排序贪心双指针查找二分查找又叫折半查找classSolutionpublic:/***代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可***@paramnumsint整型vector*@paramtargetint... 查看详情

⭐算法入门⭐《二分枚举》简单14——leetcodelcp28.采购方案(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述  小力将nnn个零件的报价存于数组numsnumsnums。小力预算为targettargetta... 查看详情

比较“笨”的枚举算法(代码片段)

枚举即一一列举。一、枚举算法的思想　　将问题所有的可能答案一一列举，然后根据实际情况选择合适而丢弃不合适的。在c语言中，枚举算法一般使用while循环实现。二、实例演练（1）“百钱买百鸡”问题：鸡翁一，值钱五... 查看详情

⭐算法入门⭐《二分枚举》简单15——leetcodelcp18.早餐组合(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述  小扣在秋日市集选择了一家早餐摊位，一维整型数组staple中记... 查看详情

⭐算法入门⭐《二分枚举》中等05——leetcode1201.丑数iii(代码片段)

...述  给你四个整数：n、a、b、c，请你设计一个算法来找出第n个丑数。丑数是可以被a或b或c整除的正整数。  样例输入：n=5,a=2,b=11,c=13  样例输出： 查看详情

⭐算法入门⭐《二分枚举》中等02——leetcode面试题10.09.排序矩阵查找(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述  给定m×nm\\timesnm×n矩阵，每一行、每一列都按升序排列，... 查看详情

《算法零基础》第9讲：算术基本定理(代码片段)

目录LeetCode507:完美数分析代码偷鸡法LeetCode263:丑数|分析代码LeetCode507:完美数原题链接:LeetCode507:完美数分析怎么求出一个数的因子，从1到sqrt(n)开始枚举，因为如果因子大于sqrt（n）的话另一个因子就会小于sqrt࿰... 查看详情

⭐算法入门⭐《二分枚举》简单12——leetcode374.猜数字大小(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述  猜数字游戏的规则如下：每轮游戏，我都会从1到n随机选... 查看详情

⭐算法入门⭐《二分枚举》中等06——leetcode275.h指数ii(代码片段)

文章目录一、题目1、题目描述2、基础框架3、原题链接二、解题报告1、思路分析2、时间复杂度3、代码详解三、本题小知识四、加群须知一、题目1、题目描述  给你一个整数数组citations，其中citations[i]表示研究者的第i篇... 查看详情