算法-暴力枚举
引入
暴力枚举就是模拟问题枚举所有可能的解，找出答案；
由于运算量比较大，所有要计算时间复杂度，不能超过计算机一次能计算的运算次数大概是1e8；
1、一个简单的例子
今有鸡翁一，值钱伍；
鸡母一，值钱三；
鸡鶵三，值钱一。
凡百钱买鸡百只，
问鸡翁、母、鶵各几何？
题解：
设x，y，z分别为公鸡数，母鸡数，小鸡数；则可以得出方程如下：
3*X+5*Y+Z/3=100;
x+y+z=100;这道题目很简单，但是重要的是从这个最简单的例子中理解暴力枚举的思想。
//方法1：for for for 枚举x,y,z,然后check
//方法2：for for 枚举x，y，让z = 100 -x-y,然后check方程
//方法3：for 枚举x,以x表示 y = (200-8*x)/14; z =(1200-6*x)/14;
for(int x =0;x<=25;x++){
if((200-8*x)%14 ==0 && (1200-6*x)%14 == 0)
cout<<x<<" "<<(200-8*x)/14<<" "<<(1200-6*x)/14<<endl;
}枚举的时候尽量选择计算次数少一些的方法，以免时间复杂度过高！再来一个例子巩固一下吧！
2、又是一个简单的例子
输入正整数n【2~79】，按照从大到小的顺序输出所有如abcde/fghij=n的表达式
aj为09的一个排列（可以有0）
题解：
如果枚举0~9的所有排列，需要10！=3628800次！，可以接受，但是没有必要；
只需要枚举fghij就可以算出abcde，再判断所有数字都不相同即可这样的话枚举次数可以减少到1万以内！
#include <bits/stdc++.h>
using namespace std;
int main(){
int a[10]={0,1,2,3,4,5,6,7,8,9};
int n; cin>>n; int num=0;
do{
num++;
int x =a[0]*10000+a[1]*1000+a[2]*100+a[3]*10+a[4];
int y =a[5]*10000+a[6]*1000+a[7]*100+a[8]*10+a[9];
if(x==y*n){
cout<<a[0]<<a[1]<<a[2]<<a[3]<<a[4]<<"/"<<a[5]<<a[6]<<a[7]<<a[8]<<a[9]<<"="<<n<<endl;
}
}while(next_permutation(a,a+10));
cout<<num;
return 0;
}输入：
62
输出：
79546/01283=62
94736/01528=62
计算次数：
3628800例1：P2241 统计方形
解题思路
一、先算正方形个数
暴力枚举每个格子存在时的正方形个数加起来，固定了正方形的右下角(i,j)，此时可能的正方形个数为Min（i，j）。
假设i，j是格子的行和列，
初始1 x 1时有1个；
在2x2时，1 x 2时多一个，2 x 1时多一个，2 x 2时除开本身一个小的还有一个大的所以是多两个；
……
发现每次新增多出正方形个数都是Min（i，j）
二、算长方形个数
首先基础小学生公式（我都忘了，小学生都不如）
长方形个数 = 矩形个数 - 正方形个数
所以算矩形个数出来，减就可以了
类似求正方形个数一样，固定矩形右下角(i,j),显然此时矩形个数为i*j.
假设i，j是格子的行和列，
初始1 x 1时有1个矩形；
基于1 x 1下1 x 2时多2个，2 x 1时多2个，2 x 2时多4个；
基于上述个数下1 x 3时多3个，3 x 1时多3个，2 x 3时多6个，3 x 2时多6个，3 x 3时多9个；
…….
发现每次新增多出矩形个数都是i*j
代码如下
#include<iostream>
#include<algorithm> //函数min(I,J)返回两数中较小得那个数
using namespace std;
int main()
{
long long n,m,i,j,sum=0,sum1=0;
cin>>n>>m;
for(i=1;i<=n;i++){
for(j=1;j<=m;j++){
sum+=min(i,j);
sum1+=i*j;
}
}
cout<<sum<<" "<<sum1-sum<<endl;
return 0;
}吐血了，小学生的题解代码都看不懂，好不容易找了个看的懂得，现在这么卷了嘛。这个路还很长，慢慢填坑吧！
例2：P2089 烤鸡
解题思路
暴力枚举或者深度优先搜索；
暴力美学(歪解)
#include<iostream>
using namespace std;
int main()
{
int a,b,c,d,e,f,g,h,i,j,in,x=0;
cin>>in;
for (a=1;a<=3;a++)
{
for (b=1;b<=3;b++)
{
for (c=1;c<=3;c++)
{
for (d=1;d<=3;d++)
{
for (e=1;e<=3;e++)
{
for (f=1;f<=3;f++)
{
for (g=1;g<=3;g++)
{
for(h=1;h<=3;h++)
{
for (i=1;i<=3;i++)
{
for (j=1;j<=3;j++)
{
if (a+b+c+d+e+f+g+h+i+j==in)
{
x++;
}
}
}
}
}
}
}
}
}
}
}
cout<<x<<endl;
for (a=1;a<=3;a++)
{
for (b=1;b<=3;b++)
{
for (c=1;c<=3;c++)
{
for (d=1;d<=3;d++)
{
for (e=1;e<=3;e++)
{
for (f=1;f<=3;f++)
{
for (g=1;g<=3;g++)
{
for(h=1;h<=3;h++)
{
for (i=1;i<=3;i++)
{
for (j=1;j<=3;j++)
{
if (a+b+c+d+e+f+g+h+i+j==in)
{
cout<<a<<" ";
cout<<b<<" ";
cout<<c<<" ";
cout<<d<<" ";
cout<<e<<" ";
cout<<f<<" ";
cout<<g<<" ";
cout<<h<<" ";
cout<<i<<" ";
cout<<j<<endl;
}
}
}
}
}
}
}
}
}
}
}
}
//so beautiful!深度优先搜索（正解）
#include<bits/stdc++.h>
using namespace std;
int s,flag=0,sum=0;//flag判断是否有解,sum方案总数
int nice[11],ans[20000][11];
void dfs(int dep,int total){//dep代表当前放第几种配料，total代表当前的配料和
if(dep==11){//若放到最后一个格子
if(total==s){//若所有配料质量之和达到美味程度
flag=1;
sum++;
for(int j=1;j<=10;j++)//存储当前方案
ans[sum][j]=nice[j];
}
return;
}
else{
for(int i=1;i<=3;i++){//当前这种配料有三种放法
if(total+i>s) break;
else{
nice[dep]=i;//存储
dfs(dep+1,total+i);//搜索下一种配料 nice[dep]=0;
}
}
}
}
int main(void){
cin>>s;//输入
dfs(1,0);
if(flag==1){
cout<<sum<<endl;//输出总数
for(int i=1;i<=sum;i++){//输出全部方案
for(int j=1;j<=10;j++){
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
}
else if(flag==0){//若无解
cout<<0<<endl;
}
return 0;
}例3：P1618三连击
STL中的next_permutation和prev_permutation计算排列组合关系的算法
【用法总结】C++ STL中 next_permutation函数的用法_荷叶田田-CSDN博客_next_permutation
#include<bits/stdc++.h>
using namespace std;
int a[10]={0,1,2,3,4,5,6,7,8,9};
int main()
{
int A,B,C,h=0;
cin>>A>>B>>C;
int t=A*B*C;
A=t/A;
B=t/B;
C=t/C;
do{
if((100*a[1]+10*a[2]+a[3])*A==(100*a[4]+10*a[5]+a[6])*B&&(100*a[1]+10*a[2]+a[3])*A==(100*a[7]+10*a[8]+a[9])*C)//如果符合比例；
{
cout<<a[1]<<a[2]<<a[3]<<" "<<a[4]<<a[5]<<a[6]<<" "<<a[7]<<a[8]<<a[9]<<endl;//输出
h++;
}
}while(next_permutation(a+1,a+10));//STL中的下一个排列函数；
if(h==0) cout<<"No!!!";//没有解输出NO；
return 0;
}
