枚举与尺取法

（练习）更多题目：

• 枚举：题库 - 蓝桥云课 (lanqiao.cn)
• 尺取：题库 - 蓝桥云课 (lanqiao.cn)

枚举法

题目：

• 第几个幸运数字 - 蓝桥云课 (lanqiao.cn)
• 排列序数 - 蓝桥云课 (lanqiao.cn)
• 火星人 - 蓝桥云课 (lanqiao.cn)

枚举的基本概念

**枚举的思想：**将问题的所有可能成为答案的解一一列举，然后根据问题所给出的条件判断此解是否合适，如果合适就保留，反之则舍弃。

枚举解题的要素：

1.确定枚举解的范围，以及判断条件

2.选取合适枚举方法，进行逐一枚举，此时应注意能否覆盖所有的可能的解

3.在枚举时使用判断条件检验，留下所有符合要求的解。

枚举的步骤：

1.根据题目确定枚举的范围，并选取合适的枚举方式，不能遗漏任何一个真正解，同时避免重复。

2.为了提高解决问题的效率，看题目是否存在优化，将可能成为解的答案范围尽可能缩小。

3.根据问题找到合理、准确描述、易编码的验证条件。

4.枚举并判断是否符合第3步确定的的条件，并保存符合条件的解。

5.按要求输出枚举过程中留下的符合条件的解。

枚举技术：排列、组合

组合型枚举

算法模板：

#include<bits/stdc++.h>
using namespace std;

int n;//共计N个数
int m;//选m个数
vector<int> chosen;
string s[1000];

void calc(int x) {
    if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝
        return;
    if (x == n + 1) { //选够了m个数输出
        for (int i = 0; i < chosen.size(); i++)
            cout<< s[chosen[i]]<<" ";//也可以不输出，存放起来也是可以的，主要是看题目。
        puts("");
        return;
    }

    chosen.push_back(x);
    calc(x + 1);
    
    chosen.pop_back();//消除痕迹
    calc(x + 1);
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];

	}
    calc(1);
	return 0;
}

/*
- chosen.size() + (n - x + 1) < m的意思是已经选择的个数和剩下可以选的元素个数的和小于m（期望选择的个数），如果提上条件语句为true，那么就不能够实现目的，直接返回退出
- chosen.push_back(x)是指选择当前x元素；chosen.pop_back()则是不选择当前元素并直接往后面遍历
- x == n + 1的含义是x的最大取值为n，当x=n+1时表明已经遍历完所有的元素，现在需要进行结束操作
*/

排列型枚举

算法模板：

#include<bits/stdc++.h>
using namespace std;

int n; //共计N个数
int order[20];
bool chosen[20];

void calc(int x) {
	if (x == n + 1) {
		for (int i = 1; i <= n; i++)
			cout << order[i] << " ";
		puts("");// puts("")直接输出空字符然后自动换行
		return;
	}
	for (int i = 1; i <= n; i++) {
		if (chosen[i])
			continue;
		order[x] = i;
		chosen[i] = 1;// 标记被选
		calc(x + 1);
		chosen[i] = 0;// 恢复初始状态，这样方便后面的转换顺序 
		order[x] = 0;
	}
}

int main() {
	cin >> n;
	calc(1);
	return 0;
}
/*
- 分析：假设n = 5，当第一次排列时从第一层直接往下递归，直到最后输出1 2 3 4 5；之后恢复chosen[5]的状态回到第4层，当前层继续恢复chosen[4]的状态，然后继续for循环，此时i = 5，并将5选入order数组，然后进入calc(x+1)中，重新进入第5层，由于1 2 3 5都已经被选择，所以当前层的for循环只有当i = 4时才能将i加入到order数组中，由此得到1 2 3 5 4的序列，之后重复以上过程恢复状态并返回到第3层，……，最终得到1 2 4 3 5，……
*/

组合枚举——二进制法

#include<bits/stdc++.h>
using namespace std;

int a[] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14};

void print_subset(int n){// 通过二进制法的方式打印子集 
	for(int i=0;i<(1<<n);++i){ // i：0~2^n，每个i的二进制数对应一个子集。一次打印一个子集，最后得到所有子集
		for(int j=0;j<n;++j){// 打印一个子集，即打印i的二进制数中所有的1
			if(i & (1<<j))// 从i的最低位开始，逐个检查每一位，如果是1，打印
				cout<<a[j]<<" ";
		}
		cout<<endl;
	}
}

int main() {
	int n = 3;  // 打印前n个元素a[0]~a[n-1]的所有子集
	print_subset(n);
	return 0;
}

假设数组a中前3个元素是{1, 2, 3}，即n=3。下面是打印所有子集的详细过程：

1. i=0，二进制为000，表示空集，不包含任何元素。

2. i=1，二进制为001，表示只包含a[0]，即{1}。

3. i=2，二进制为010，表示只包含a[1]，即{2}。

4. i=3，二进制为011，表示包含a[0]和a[1]，即{1, 2}。

5. i=4，二进制为100，表示只包含a[2]，即{3}。

6. i=5，二进制为101，表示包含a[0]和a[2]，即{1, 3}。

7. i=6，二进制为110，表示包含a[1]和a[2]，即{2, 3}。

8. i=7，二进制为111，表示包含a[0]、a[1]和a[2]，即{1, 2, 3}。

在每次循环时，我们都检查i的二进制数中是否有某一位值为1，如果是，则输出相应的元素。例如，在第3次循环中，当j=1时，i的二进制数表示为011，它的第2位为1，因此打印出a[1]=2。

最终输出结果如下：

1 
2 
1 2 
3 
1 3 
2 3 
1 2 3 

尺取法

题目：

• 回文判定 - 蓝桥云课 (lanqiao.cn)
  • 
• 美丽的区间 - 蓝桥云课 (lanqiao.cn)
  • 

尺取法（双指针、two pointers）

• 一个常用的优化技巧

• 解决序列的区间问题

• 操作简单、容易编程

尺取法是一种线性的高效率算法。记 (L, R ) 为一个序列内以L为起点的最短合法区间，如果R随L的增大而增大的，就可以使用尺取法。具体的做法是不断的枚举 L，同时求出R。因为 R 随 L增大而增大，所以总时间复杂度为 O(n)

反向扫描：i、j方向相反，i从头到尾，j从尾到头，在中间相会。“左右指针”

同向扫描：i、j方向相同，都从头到尾，速度不同，例如让j跑在i前面。“快慢指针”