枚举与尺取法（蓝桥杯 c++ 模板 题目 代码 注解）

目录

组合型枚举（排列组合模板（））:

排列型枚举（全排列）模板： 

题目一（公平抽签 排列组合）： 

​编辑 代码：

题目二（座次问题 全排列）：

代码： 

题目三（排列序数）：

代码： 

题目四（ 美丽的区间 尺取法）：

代码：

 题目五（奇怪的动物园 尺取法）：

代码：

组合型枚举（排列组合模板（））:

#include <iostream>//排列组合
#include <vector>
using namespace std;
int n, m;
vector<int> chosen;
void calc(int k)
{if ((chosen.size() > m) || (chosen.size() + n - k + 1) < m)//选太多了，选太少了，chosen.size()表示选了几个return;if (k == n + 1)//最后一个数都已经选完了{for (int i = 0; i < chosen.size(); i++)cout << chosen[i]<<" ";//输出第i个为几cout << endl;return;}chosen.push_back(k);//选数字kcalc(k + 1);//继续往深度遍历chosen.pop_back();//不选数字kcalc(k + 1);//继续往深度遍历
}
int main()
{cin >> n >> m;calc(1);//从一开始
}

排列型枚举（全排列）模板： 

#include <iostream>//排列型枚举，全排列
#include <vector>
using namespace std;
int n;
int chosen[20];
int book[20] = { 0 };
void calc(int k)
{if (k == n + 1)//最后一个数都已经选完了{for (int i = 1; i <= n; i++)cout << chosen[i]<<" ";//输出第i个为几cout << endl;return;}for (int i = 1; i <= n; i++){if (book[i])//标记是否用过continue;book[i] = 1;//标记为用了chosen[k] = i;//第k个为数字icalc(k + 1);//继续往深度遍历book[i] = 0;//回溯，没访问过ichosen[k] = 0;}
}
int main()
{cin >> n;calc(1);//从一开始
}

题目一（公平抽签 排列组合）： 

 代码：

#include<iostream>
#include<vector>
using namespace std;
int n, m;
vector<int> chosen;
vector<string> name;
void calc(int k)
{if (chosen.size() > m || chosen.size() + (n - k + 1) < m)//选多了或者选少了，chosen.size()表示选了几个return;if (k == n + 1)//最后一个也已经选完了{for (int i = 0; i < chosen.size(); i++)cout << name[chosen[i]-1] << " ";cout << endl;}chosen.push_back(k);//选数字kcalc(k + 1);//继续往深度遍历chosen.pop_back();//不选数字kcalc(k + 1);//继续往深度遍历
}
int main()
{cin >> n >> m;for (int i = 0; i < n; i++){string s;cin >> s;name.push_back(s);}calc(1);
}

题目二（座次问题 全排列）：

代码： 

#include<iostream>
#include<vector>
using namespace std;
int n;
int chosen[15];
int book[15];//标记是否访问过
string name[15];
void calc(int k)
{if (k == n + 1)//最后一个数都已经选完了{for (int i = 1; i <= n; i++)//输出该排列{cout << name[chosen[i] - 1] << " ";//name下标从0开始}cout << endl;return;}for (int i = 1; i <= n; i++){if (book[i])//标记是否用过continue;book[i] = 1;//标记为用了chosen[k] = i;//第k个为数字icalc(k + 1);//继续往深度遍历book[i] = 0;//回溯，没访问过ichosen[k] = 0;}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> name[i];}calc(1);//从第一个开始
}

题目三（排列序数）：

代码： 

 

#include <iostream>//用next_permutation函数进行全排列
#include <algorithm>
using namespace std;
int main()
{long long  cnt=0;//记录个数string s;string s1;cin >> s;s1 = s;sort(s.begin(), s.end());//从大到小排序do {if (s == s1)//相等的时候跳出break;cnt++;} while (next_permutation(s.begin(), s.end()));//开始遍历cout << cnt;}

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

题目四（ 美丽的区间 尺取法）：

代码：

#include <iostream>
using namespace std;
int n, s;
int ans = 1e8, sum = 0;
int a[100010];
int main()
{cin >> n >> s;for (int i = 1; i <= n; i++)cin >> a[i];for (int l = 1, r = 1; r <= n; ){if(sum<s)//不大于s，则加上，往右遍历{sum+=a[r],r++;}else{ans=min(r-l,ans);//取小的sum-=a[l];//减掉最左边l++;//往下遍历}}if (ans == 1e8)//不存在cout << 0;elsecout << ans;
}

 题目五（奇怪的动物园 尺取法）：

代码：

#include<iostream>
using namespace std;
int n, m, cnt,ans,ansl=0,ansr=0;//ans记录票价
int a[1010];
int b[1010];//记录x类动物的数量
void In(int x)
{if (b[x] == 0) cnt++;//之前没有x类动物，现在加入了，种类cnt++b[x]++;//x类动物数量加一
}
void De(int x)
{if (b[x] == 1) cnt--;//之前有一个x类动物，现在删掉，种类cnt--b[x]--;//x类动物数量减一
}
int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){cin >> a[i];}ans = n;//最大为一共有的动物数量for (int l = 1, r = 1; r <= n; r++){In(a[r]);//a[r]这类动物加入while (1){De(a[l]);//删掉最左边类动物if (cnt == m) l++;//删了，cnt等于m，所有种类都选到了，则l++else//删了这类动物，不满足cnt等于m，还是要把这类动物加入{In(a[l]);break;}}if (cnt == m && r - l + 1 < ans)//满足所有动物都能看，票价更低了，更新左区间和右区间{ans = r - l + 1;ansl = l, ansr = r;}}if (ansl != 0)cout << ansl << " " << ansr;elsecout << 1 << n;
}