暴力枚举法:循环枚举(1,2,5)、排列枚举(3,4,6)、子集枚举(4,7-10)。
(1)循环枚举:一个枚举变量对应一层循环,注意变量范围和层数优化(循环执行次数在10^10以内)
(2)排列枚举:next_permutation、prev_permutation(12以内)
do{
…
}while(next_permutation(a+0,a+n));
(3)子集枚举:用二进制01表示选择和不选择(25以内)
int a[100]; // 注意:从下标0开始存放
……
for (int i = 0; i < (1<<n); i++) // 子集 i 从 0 ~ (1<<n) ,表示枚举 00...00 ~ 11...11。如果不枚举00...00,则 i = 1 开始
{
bitset<30> b(i); // 将i转换为二进制数b,即子集0…0到子集1…1
for (int j=0; j<n; j++) // 找出b中所有的1,表示a中对应元素被选入子集i
{
if (b[j]==1) // b[j]=1,表示 a[j] 入选子集 i
{
……
}
}
}
另附:质数判断函数,返回结果1表示是质数,0表示不是质数
int f(int x) {
if (x <= 1)
return 0;
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0)
return 0;
return 1;
}