五一培训 清北学堂 DAY1

今天是冯哲老师的讲授~

1.枚举

枚举也称作穷举，指的是从问题所有可能的解的集合中一一枚举各元素。

用题目中给定的检验条件判定哪些是无用的，哪些是有用的。能使命题成立的即为其解。

例一
一棵苹果树上有n个苹果，每个苹果长在高度为Ai的地方。
小明的身高为x
他想知道他最多能摘到多少苹果
数据范围： 1 ≤ n, Ai, x ≤ 100

题解
问题相当于询问有多少i满足Ai <= x
考虑用for循环枚举每一个苹果是否能被摘到即可。

例二
判断一个数X是否是素数
1 ≤ X ≤ 109
题解
考虑定义，若X为合数，则必然有：
∃1 < i < X, i|X
我们考虑直接枚举每个i，看他是否为X的因子。
时间复杂度O(N)，不符合要求；
事实上我们发现，假设X是一个合数，那么必然有:
X = a * b,必然有：
min(a, b) <= √X
因此我们枚举的范围可以从X变为√X
时间复杂度O(√N)

例三
求[l, r]这段区间中有多少素数
1 ≤ l ≤ r ≤ 10^6

题解

一个显然的想法是利用for循环枚举[l, r]中的每一个数。然后
利用例二中的知识O(√X)进行判断。
整体复杂度O(N√N),不符合要求
筛法求素数
仍然考虑枚举判断每个数是否是素数，但我们这次从2开始判断。

考虑对于任意一个数x,不论x是否为素数，都
有x*2,x*3,x*4...为合数。我们“筛”掉这些必然为合数的数。
那么当我们枚举到i，i还没有被筛掉，那么i必然为素数。
时间复杂度O(NlogN)
 

也就是埃拉托斯特尼筛法，简称埃氏筛

具体为什么不用欧拉筛（线性筛），我也不知道，老师说先不讲……

例四
T次询问，每次询问[l, r]中有多少素数
1 ≤ T ≤ 105, 1 ≤ l ≤ r ≤ 10^6

题解

有多次询问，如果每次询问我们都先找一遍，那么肯定TLE，那么咋办呢？
我们用ANSL,R来表示[l, r]中有多少素数

运用前缀和的思想（先进行预处理）：

#include<cstdio>
using namespace std;
#define MAXN  1000005
int sum[MAXN],vis[MAXN];              //sum储存1~i的质数个数，vis记录第i个数是否为质数 
int t,l,r;
void pre()                            //预处理所有1~MAXN内的质数个数 
{
    for(int i=2;i<=MAXN;i++)
    {
        sum[i]=sum[i-1];              //1到i的质数个数一定大于等于i到i-1的质数个数，所以利用前缀和求质数个数 
        if(!vis[i]) sum[i]++;         //如果i是质数，个数加一 
        for(int j=i*2;j<=MAXN;j+=i)   //埃氏筛把i所有的倍数都判为合数 
        vis[j]=1;                     //标记为合数 
    }
}
int main()
{
    pre();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&l,&r);
        printf("%d\n",sum[r]-sum[l-1]);   //直接利用前缀和求质数个数 
    }
    return 0;
}

例五
已知n个整数x1, x2, .., xn,以及一个整数k,k < n。从n个数字
中任选k 个整数相加，可分别得到一系列的和。
例如当n = 4, k = 3,四个整数分别为3,7,12,19时，可得全部
的组合与他们的和为:
3 + 7 + 12 = 22
3 + 7 + 19 = 29
7 + 12 + 19 = 38
3 + 12 + 19 = 34
现在，要求计算出和为素数的组合共有多少种。
例如上例，只有一种组合的和为素数：3 + 7 + 19 = 29
1 ≤ n ≤ 20, k < n
1 ≤ x1, x2, .., xn ≤ 5 * 106

题解
首先我们来考虑如何枚举这样的组合。
我们用ai来表示第i个数是否被选
ai = 1表示这个数被选择了
ai = 0表示这个数未被选择
枚举过程相当于枚举了一组二进制状态
比如对于五个数1,2,3,4,5
01010表示我们选择了2,4,未选择1,3,5

在不考虑k的限制的情况下，我们枚举所有组合就相当于
枚举00..00(n个0) → 11..11(n个1)
对于任意一种中间状态，0的个数+1的个数为n
我们假设这是一个长为n的二进制数，我们将它转换成十进制。因为十进制的0（每个都不选）到2^n（每个数都选）中的每个数就是对应着其中的每一情况

事实上就是枚举了一个数，范围是[0, 2^n)
判断位置i是否为1使用位运算来完成

看二进制中1的个数是否等于k，如果是就进一步判断是否和为素数。Check部分即为判断是否为素数。
考虑到最大Sum不超过20 * 500w，预处理出10000以内的素数可以加速。

例六
求[l,r]中有多少数既是回文数又是素数
1 ≤ l ≤ r ≤ 10
策略一
枚举每个数，判断他是不是回文数，判断他是不是素数
时间复杂度O(N√N + NlogN)

 策略二
预处理出区间所有素数，枚举素数判定是否是回文数
时间复杂度O(NlogN) ，判断回文数的时间复杂度可以不计。

策略三
枚举区间内所有回文数，判断是否是素数
枚举回文数即枚举一个数的前一半，再手动扩展成完整的数
另外，偶数位数的回文数都必然是11的倍数，不需要枚举。
时间复杂度O(√N * √N) = O(N)，第一个√N是只要枚举前一半就好了，第二个√N是判素数。

枚举法的优缺点：

优点：
简单明了，分析直观
能够帮助我们更好地理解问题
运用良好的枚举技巧可以使问题变得更简单

缺点：
时空间效率低
往往没有利用题目中的特殊性质
产生了大量冗余状态

五一培训 清北学堂 DAY1

原文：https://www.cnblogs.com/xcg123/p/10783602.html