枚举谁都会，但是同样都是打枚举，得分就可能不一样，就比如砝码称重那道题，神仙涛枚举100分，我枚举30分,这就是枚举技巧，所以对于我这种算法基本靠枚举的蒟蒻来说学好枚举很重要了...咕咕咕
定义
枚举就是需要遍历每个解来寻找最优解/计数的问题 ，复杂度会出现指数级，此时数据范围一般较小 关键在于能否找到需要枚举的变量，以及枚举的效率，避免无用的枚举
题目链接：
思路：
这道题就是个简单的搜索或者说是枚举，主要是想用这道题来浅谈一下枚举的技巧，当然每道题都不一样。
最暴力的枚举：
来自题解
#include<stdio.h>
#include<cmath>
#include<cstdlib>
#include<iostream>
using namespace std;
int a[21];
int s,x,n,k;
bool zs(long long y)//判断是否是质数
{
if (y==1||!y) return 0;
for (int i=2;i<=sqrt(y);i++)
if (!(y%i)) return 0;
return 1;
}
void sr()
{
scanf("%d %d",&n,&k);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
x+=a[i];//求下总和
}
}
void js()
{
if (k==19||k==n-1) {for (int i=1;i<=n;i++) if (zs(x-a[i])) s++;return;}
if (k==20||n==k) {if (zs(x)) s++;return;}//两个特判
if (k==1)
{
for (int i=1;i<=n;i++)
if (zs(a[i])) s++;//计算
}
if (k==2)
{
for (int i=1;i<=n-1;i++)
for (int i1=i+1;i1<=n;i1++)
if (zs(a[i]+a[i1])) s++;//计算
return;
}
if (k==3)
{
for (int i=1;i<=n-2;i++)
for (int i1=i+1;i1<=n-1;i1++)
for (int i2=i1+1;i2<=n;i2++)
if(zs(a[i]+a[i1]+a[i2]))s++;//计算
return;
}
if (k==4)
{
for (int i=1;i<=n-3;i++)
for (int i1=i+1;i1<=n-2;i1++)
for (int i2=i1+1;i2<=n-1;i2++)
for (int i3=i2+1;i3<=n;i3++)
if(zs(a[i]+a[i1]+a[i2]+a[i3]))s++;
return;
}
if (k==5)
{
for (int i=1;i<=n-4;i++)
for (int i1=i+1;i1<=n-3;i1++)
for (int i2=i1+1;i2<=n-2;i2++)
for (int i3=i2+1;i3<=n-1;i3++)
for (int i4=i3+1;i4<=n;i4++)
if(zs(a[i]+a[i1]+a[i2]+a[i3]+a[i4]))s++;
return;
}
if (k==6)
{
for (int i=1;i<=n-5;i++)
for (int i1=i+1;i1<=n-4;i1++)
for (int i2=i1+1;i2<=n-3;i2++)
for (int i3=i2+1;i3<=n-2;i3++)
for (int i4=i3+1;i4<=n-1;i4++)
for (int i5=i4+1;i5<=n;i5++)
if(zs(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]))s++;
return;
}
if (k==7)
{
for (int i=1;i<=n-6;i++)
for (int i1=i+1;i1<=n-5;i1++)
for (int i2=i1+1;i2<=n-4;i2++)
for (int i3=i2+1;i3<=n-3;i3++)
for (int i4=i3+1;i4<=n-2;i4++)
for (int i5=i4+1;i5<=n-1;i5++)
for (int i6=i5+1;i6<=n;i6++)
if(zs(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]))s++;
return;
}
if (k==8)
{
for (int i=1;i<=n-7;i++)
for (int i1=i+1;i1<=n-6;i1++)
for (int i2=i1+1;i2<=n-5;i2++)
for (int i3=i2+1;i3<=n-4;i3++)
for (int i4=i3+1;i4<=n-3;i4++)
for (int i5=i4+1;i5<=n-2;i5++)
for (int i6=i5+1;i6<=n-1;i6++)
for (int i7=i6+1;i7<=n;i7++)
if(zs(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]+a[i7]))s++;
return;
}
if (k==9)
{
for (int i=1;i<=n-8;i++)
for (int i1=i+1;i1<=n-7;i1++)
for (int i2=i1+1;i2<=n-6;i2++)
for (int i3=i2+1;i3<=n-5;i3++)
for (int i4=i3+1;i4<=n-4;i4++)
for (int i5=i4+1;i5<=n-3;i5++)
for (int i6=i5+1;i6<=n-2;i6++)
for (int i7=i6+1;i7<=n-1;i7++)
for (int i8=i7+1;i8<=n;i8++)
if(zs(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]+a[i7]+a[i8]))s++;
return;
}
if (k==10)
{
for (int i=1;i<=n-9;i++)
for (int i1=i+1;i1<=n-8;i1++)
for (int i2=i1+1;i2<=n-7;i2++)
for (int i3=i2+1;i3<=n-6;i3++)
for (int i4=i3+1;i4<=n-5;i4++)
for (int i5=i4+1;i5<=n-4;i5++)
for (int i6=i5+1;i6<=n-3;i6++)
for (int i7=i6+1;i7<=n-2;i7++)
for (int i8=i7+1;i8<=n-1;i8++)
for (int i9=i8+1;i9<=n;i9++)
if(zs(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]+a[i7]+a[i8]+a[i9]))s++;
return;
}
if (k==11)
{
for (int i=1;i<=n-8;i++)
for (int i1=i+1;i1<=n-7;i1++)
for (int i2=i1+1;i2<=n-6;i2++)
for (int i3=i2+1;i3<=n-5;i3++)
for (int i4=i3+1;i4<=n-4;i4++)
for (int i5=i4+1;i5<=n-3;i5++)
for (int i6=i5+1;i6<=n-2;i6++)
for (int i7=i6+1;i7<=n-1;i7++)
for (int i8=i7+1;i8<=n;i8++)
if(zs(x-(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]+a[i7]+a[i8])))s++;//注意这里是用x去减
return;
}
if (k==12)
{
for (int i=1;i<=n-7;i++)
for (int i1=i+1;i1<=n-6;i1++)
for (int i2=i1+1;i2<=n-5;i2++)
for (int i3=i2+1;i3<=n-4;i3++)
for (int i4=i3+1;i4<=n-3;i4++)
for (int i5=i4+1;i5<=n-2;i5++)
for (int i6=i5+1;i6<=n-1;i6++)
for (int i7=i6+1;i7<=n;i7++)
if(zs(x-(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6]+a[i7])))s++;
return ;//以下都是用x去减，注意！
}
if (k==13)
{
for (int i=1;i<=n-6;i++)
for (int i1=i+1;i1<=n-5;i1++)
for (int i2=i1+1;i2<=n-4;i2++)
for (int i3=i2+1;i3<=n-3;i3++)
for (int i4=i3+1;i4<=n-2;i4++)
for (int i5=i4+1;i5<=n-1;i5++)
for (int i6=i5+1;i6<=n;i6++)
if(zs(x-(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5]+a[i6])))s++;
return;
}
if (k==14)
{
for (int i=1;i<=n-5;i++)
for (int i1=i+1;i1<=n-4;i1++)
for (int i2=i1+1;i2<=n-3;i2++)
for (int i3=i2+1;i3<=n-2;i3++)
for (int i4=i3+1;i4<=n-1;i4++)
for (int i5=i4+1;i5<=n;i5++)
if(zs(x-(a[i]+a[i1]+a[i2]+a[i3]+a[i4]+a[i5])))s++;
return;
}
if (k==15)
{
for (int i=1;i<=n-4;i++)
for (int i1=i+1;i1<=n-3;i1++)
for (int i2=i1+1;i2<=n-2;i2++)
for (int i3=i2+1;i3<=n-1;i3++)
for (int i4=i3+1;i4<=n;i4++)
if(zs(x-(a[i]+a[i1]+a[i2]+a[i3]+a[i4])))s++;
return;
}
if (k==16)
{
for (int i=1;i<=n-3;i++)
for (int i1=i+1;i1<=n-2;i1++)
for (int i2=i1+1;i2<=n-1;i2++)
for (int i3=i2+1;i3<=n;i3++)
if(zs(x-(a[i]+a[i1]+a[i2]+a[i3])))s++;
return;
}
if (k==17)
{
for (int i=1;i<=n-2;i++)
for (int i1=i+1;i1<=n-1;i1++)
for (int i2=i1+1;i2<=n;i2++)
if(zs(x-(a[i]+a[i1]+a[i2])))s++;
return;
}
if (k==18)
{
for (int i=1;i<=n-1;i++)
for (int i1=i+1;i1<=n;i1++)
if (zs(x-(a[i]+a[i1]))) s++;//之前没有用x去减，给大家造成了一些困扰，在这里说声抱歉
return;
}
}
int main()
{
sr();
js();
printf("%d",s);
}
这方法说实话没谁了
dfs枚举法：
依次考虑每个元素是否选取 记录当前状态选取元素个数，以及被选取的元素之和 向下一层搜索时，更新状态，搜索结束时，还原状态
/*
原始的dfs
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
#define MAXN 100000
using namespace std;
inline int read() {
char c = getchar();
int x = 0, f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int ans;
int a[MAXN];
int n, k;
int is_prime (int x)
{
if(x==1) return 0;
for(int i=2;i*i<=x;++i)
{
if(x%i==0) return 0;
}
return 1;
}
void dfs(int now, int cnt, int s) {
if (now == n) {
if (cnt == k && is_prime(s)) ans++;
} else {
dfs(now + 1, cnt, s);
dfs(now + 1, cnt + 1, s + a[now]);
}
}
dfs(0, 0, 0);
int main() {
cin>>n>>k;
for(int i=0;i<n;++i)
{
cin>>a[i];
}
dfs(0, 0, 0);
cout<<ans;
return 0;
}
观察上面的程序发现还是有问题的
它仍然会搜索一些多余状态
所以我们要剪枝
剪枝版dfs
剪枝如下，很显然是吧
if (cnt > k || cnt + n - now < k) return;
代码就不放了，太长了...只放核心：
void dfs(int now, int cnt, int s) {
if (now == n) {
if (cnt == k && is_prime(s)) ans++;
} else {
if (cnt > k || cnt + n - now < k) return;//这里****
dfs(now + 1, cnt, s);
dfs(now + 1, cnt + 1, s + a[now]);
}
}
dfs枚举排列
依次考虑每个位置选取的元素 记录当前状态已经被选取的元素 向下一层搜索时更新状态，搜索结束时，还原状态
void dfs(int now) {
if (now == n) {
if (test(p)) ans++;
} else {
for (int i = 1; i <= n; i++) {
if (!flag[i]) {
p[now] = i;
flag[i] = true;
dfs(now + 1);
flag[i] = false;
}
}
}
}
dfs(0);
高效枚举集合
这个方法就比较牛逼了
一个集合的子集个数是(2^n)个，而且，我们可以建立一个从(0)到(2^n-1)的整数到集合子集之间的一一映射 具体来说，将最低位记作第(0)位，二进制表示第i位为(1)，则表示取集合中的第(i)个元素 因此，只需枚举(0)到(2^n-1)之间的整数即可 而判断某个元素有没有被选中，就是判断第(i)位是否位(a)
for (int j = 0; j < (1 << n); j++) {
int s = 0;
for (int i = 0; i < n; i++) {
if (j & (1 << i)) {
s += a[i];
}
}
}
高效枚举排列
#include <algorithm>
std::next_permutation
std::prev_permutation
STL中的函数，接受两个参数表示数组的起止位置 会将数组变为对应的下/上一个排列 如果当前数组是最后一个排列，则变为第一个排列，并且返回false，否则返回true 时间复杂度(O(n))
int p[MAXN];
for (int i = 0; i < n; i++) p[i] = i + 1;
do {
test(p);
} while (std::next_permutation(p, p + n));
免费送一道next_permutation 的裸题
P1088 火星人
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<string>
#include<cstring>
using namespace std;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int a[100560],n,m;
signed main()
{
cin>>n>>m;
for(int i=0;i<n;++i) cin>>a[i];
for(int i=1;i<=m;++i) next_permutation(a,a+n);
for(int i=0;i<n;++i)
{
cout<<a[i]<<" ";
}
return 0;
}